論文の概要: Solving the capacitated vehicle routing problem with timing windows using rollouts and MAX-SAT

• arxiv url: http://arxiv.org/abs/2206.06618v1
• Date: Tue, 14 Jun 2022 06:27:09 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-15 14:37:39.586591
• Title: Solving the capacitated vehicle routing problem with timing windows using rollouts and MAX-SAT
• Title（参考訳）: ロールアウトとMAX-SATを用いたタイミング窓による静電容量化車両経路問題の解法
• Authors: Harshad Khadilkar
• Abstract要約: 車両ルーティングはNPハード最適化問題のよく知られたクラスである。 最近の強化学習の取り組みは有望な代替手段である。 本稿では,強化学習,政策展開,満足度を組み合わせたハイブリッドアプローチを提案する。
• 参考スコア（独自算出の注目度）: 4.873362301533824
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The vehicle routing problem is a well known class of NP-hard combinatorial optimisation problems in literature. Traditional solution methods involve either carefully designed heuristics, or time-consuming metaheuristics. Recent work in reinforcement learning has been a promising alternative approach, but has found it difficult to compete with traditional methods in terms of solution quality. This paper proposes a hybrid approach that combines reinforcement learning, policy rollouts, and a satisfiability solver to enable a tunable tradeoff between computation times and solution quality. Results on a popular public data set show that the algorithm is able to produce solutions closer to optimal levels than existing learning based approaches, and with shorter computation times than meta-heuristics. The approach requires minimal design effort and is able to solve unseen problems of arbitrary scale without additional training. Furthermore, the methodology is generalisable to other combinatorial optimisation problems.
• Abstract（参考訳）: 車両ルーティング問題は、文学におけるNPハード組合せ最適化問題のよく知られたクラスである。 伝統的な解法は、慎重に設計されたヒューリスティックまたは時間を要するメタヒューリスティックである。 強化学習における最近の研究は有望な代替手法であるが、ソリューションの品質の観点から従来の手法と競合することは困難である。 本稿では,強化学習とポリシーロールアウト,満足度解決を組み合わせることで,計算時間と解品質の調整可能なトレードオフを実現するハイブリッド手法を提案する。 一般的な公開データセットでは、アルゴリズムは既存の学習ベースアプローチよりも最適レベルに近い解を生成でき、メタヒューリスティックスよりも計算時間が短いことが示されている。 このアプローチには最小限の設計労力が必要であり、追加のトレーニングなしで任意の規模の未発見の問題を解決することができる。 さらに、この手法は他の組合せ最適化問題にも一般化可能である。

関連論文リスト

• Learn to Solve Vehicle Routing Problems ASAP: A Neural Optimization Approach for Time-Constrained Vehicle Routing Problems with Finite Vehicle Fleet [0.0]
  車両の車両サイズが有限である時間制約付静電容量VRPを解くためのNCO手法を提案する。 この手法は、柔軟性と堅牢な一般化の両方を示す、適切で費用効率のよい解を見つけることができる。
  論文  参考訳（メタデータ） (2024-11-07T15:16:36Z)
• Learning Joint Models of Prediction and Optimization [56.04498536842065]
  Predict-Then-Thenフレームワークは、機械学習モデルを使用して、最適化問題の未知のパラメータを、解決前の機能から予測する。 本稿では,共同予測モデルを用いて観測可能特徴から最適解を直接学習する手法を提案する。
  論文  参考訳（メタデータ） (2024-09-07T19:52:14Z)
• Socio-cognitive Optimization of Time-delay Control Problems using Evolutionary Metaheuristics [89.24951036534168]
  メタヒューリスティックス(Metaheuristics)は、古典的なアプローチでは解決できない難解な問題を解くために使用される普遍的な最適化アルゴリズムである。 本稿では,キャストに基づく新しい社会認知メタヒューリスティックの構築を目標とし,このアルゴリズムのいくつかのバージョンを時間遅延システムモデルの最適化に適用する。
  論文  参考訳（メタデータ） (2022-10-23T22:21:10Z)
• Sample-Efficient, Exploration-Based Policy Optimisation for Routing Problems [2.6782615615913348]
  本稿では,エントロピーに基づく新しい強化学習手法を提案する。 さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。 我々のモデルは様々な経路問題に一般化可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-31T09:51:48Z)
• Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem [18.735056206844202]
  我々は,従来の自己回帰的アプローチよりもはるかに高速に,監督や推論なしに学習できるモデルを構築することができることを示す。 また、ディープラーニングモデルに最適なトランスポートアルゴリズムを組み込むことで、エンドツーエンドのトレーニング中に割り当て制約を強制する利点を実証的に評価する。
  論文  参考訳（メタデータ） (2022-03-02T07:21:56Z)
• An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem [49.04543375851723]
  車両ルーティング問題(VRP)は典型的な離散最適化問題である。 多くの研究は、VRPを解決するための学習に基づく最適化アルゴリズムについて検討している。 本稿では、最近のこの分野の進歩を概観し、関連するアプローチをエンドツーエンドアプローチとステップバイステップアプローチに分割する。
  論文  参考訳（メタデータ） (2021-07-15T02:13:03Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• SOLO: Search Online, Learn Offline for Combinatorial Optimization Problems [4.777801093677586]
  我々は,機械スケジューリングやルーティング,割当てといった実世界のアプリケーションで問題を研究する。 RL(Reinforcement Learning)とプランニングを組み合わせた手法を提案する。 この方法は、オフラインでも、オンラインでも、問題のコンポーネントが事前に分かっておらず、むしろ意思決定プロセス中に現れるような、問題の変種にも等しく適用することができる。
  論文  参考訳（メタデータ） (2021-04-04T17:12:24Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning [0.0]
  本稿では,Juliaで実装された新しい制約プログラミング問題であるSeaPearlの概念実証について述べる。 seapearlは強化学習を使用して分岐決定を学ぶために機械学習ルーチンをサポートする。 産業用ソリューションとはまだ競合していないが、seapearlは柔軟でオープンソースなフレームワークを提供することを目指している。
  論文  参考訳（メタデータ） (2021-02-18T07:34:38Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。