論文の概要: Learning Vehicle Routing Problems using Policy Optimisation
- arxiv url: http://arxiv.org/abs/2012.13269v1
- Date: Thu, 24 Dec 2020 14:18:56 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-25 14:12:53.361446
- Title: Learning Vehicle Routing Problems using Policy Optimisation
- Title(参考訳): ポリシー最適化による車両経路問題の学習
- Authors: Nasrin Sultana, Jeffrey Chan, A. K. Qin, Tabinda Sarwar
- Abstract要約: 最先端のアプローチは強化学習を使ってポリシーを学習し、学習ポリシーは擬似解法として機能する。
これらのアプローチは、あるケースでは優れた性能を示しているが、ルーティング問題に典型的な大きな検索空間を考えると、ポリシーの貧弱さに早すぎる可能性がある。
より多くのポリシーを提供することで探索を支援するエントロピー正規化強化学習(ERRL)を提案する。
- 参考スコア(独自算出の注目度): 4.093722933440819
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Deep reinforcement learning (DRL) has been used to learn effective heuristics
for solving complex combinatorial optimisation problem via policy networks and
have demonstrated promising performance. Existing works have focused on solving
(vehicle) routing problems as they have a nice balance between non-triviality
and difficulty. State-of-the-art approaches learn a policy using reinforcement
learning, and the learnt policy acts as a pseudo solver. These approaches have
demonstrated good performance in some cases, but given the large search space
typical combinatorial/routing problem, they can converge too quickly to poor
policy. To prevent this, in this paper, we propose an approach name entropy
regularised reinforcement learning (ERRL) that supports exploration by
providing more stochastic policies, which tends to improve optimisation.
Empirically, the low variance ERRL offers RL training fast and stable. We also
introduce a combination of local search operators during test time, which
significantly improves solution and complement ERRL. We qualitatively
demonstrate that for vehicle routing problems, a policy with higher entropy can
make the optimisation landscape smooth which makes it easier to optimise. The
quantitative evaluation shows that the performance of the model is comparable
with the state-of-the-art variants. In our evaluation, we experimentally
illustrate that the model produces state-of-the-art performance on variants of
Vehicle Routing problems such as Capacitated Vehicle Routing Problem (CVRP),
Multiple Routing with Fixed Fleet Problems (MRPFF) and Travelling Salesman
problem.
- Abstract(参考訳): 深部強化学習(DRL)は、ポリシーネットワークを介して複雑な組合せ最適化問題を解くための効果的なヒューリスティックスを学ぶために用いられ、有望な性能を示した。
既存の作業では、非自明さと困難さのバランスがよいため、ルーティング問題の解決(車両)に注力しています。
最先端のアプローチは強化学習を使ってポリシーを学習し、学習ポリシーは擬似解法として機能する。
これらのアプローチは、あるケースでは優れた性能を示しているが、大きな探索空間の典型的な組合せ/ルーティング問題を考えると、それらはあまりに早く貧弱なポリシーに収束する可能性がある。
そこで本稿では,より確率的なポリシを提供することにより,探索を支援するアプローチ名 Entropy regularized reinforcement learning (ERRL) を提案する。
経験的に、低分散ERRLはRLトレーニングを高速かつ安定に行う。
また、テスト期間中にローカル検索演算子の組み合わせを導入し、解法を大幅に改善し、ERRLを補完する。
車両ルーティング問題に対して,高エントロピーのポリシーは,最適化環境を円滑にすることで,最適化が容易になることを示す。
定量的評価の結果,モデルの性能は最先端の変種に匹敵することがわかった。
本評価では, キャパシタント車両ルーティング問題 (CVRP) , 固定フリート問題 (MRPFF) , トラベリングセールスマン問題 (Travelling Salesman problem) などの車両ルーティング問題に対して, モデルが最先端の性能を示すことを実験的に示す。
関連論文リスト
- Reinforcement Learning for Solving Stochastic Vehicle Routing Problem [0.09831489366502298]
本研究では、車両ルーティング問題(SVRP)解決における強化学習(RL)と機械学習(ML)技術の利用のギャップを解消する。
本稿では,SVRPのキーソースを包括的に扱う新しいエンドツーエンドフレームワークを提案する。
提案モデルでは,広く採用されている最先端のメユーリスティックよりも優れた性能を示し,旅行コストの3.43%削減を実現している。
論文 参考訳(メタデータ) (2023-11-13T19:46:22Z) - Unlocking Carbon Reduction Potential with Reinforcement Learning for the
Three-Dimensional Loading Capacitated Vehicle Routing Problem [54.43397200631224]
効率を上げるためのソリューションとして、協調車両ルーティングが提案されている。
現在の運用研究手法は、問題の大きさを増大させる非線形スケーリングに悩まされている。
約線形時間で3次元負荷容量化車両ルーティング問題を解くための強化学習モデルを開発した。
論文 参考訳(メタデータ) (2023-07-22T18:05:28Z) - Combinatorial Optimization enriched Machine Learning to solve the
Dynamic Vehicle Routing Problem with Time Windows [5.4807970361321585]
最適化層を組み込んだ新しい機械学習パイプラインを提案する。
最近,EURO Meets NeurIPS Competition at NeurIPS 2022において,このパイプラインを波による動的車両ルーティング問題に適用した。
提案手法は,提案した動的車両経路問題の解法において,他の全ての手法よりも優れていた。
論文 参考訳(メタデータ) (2023-04-03T08:23:09Z) - MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion
Control in Real Networks [63.24965775030673]
そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。
我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。
我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
論文 参考訳(メタデータ) (2023-02-02T18:27:20Z) - Solving the capacitated vehicle routing problem with timing windows
using rollouts and MAX-SAT [4.873362301533824]
車両ルーティングはNPハード最適化問題のよく知られたクラスである。
最近の強化学習の取り組みは有望な代替手段である。
本稿では,強化学習,政策展開,満足度を組み合わせたハイブリッドアプローチを提案する。
論文 参考訳(メタデータ) (2022-06-14T06:27:09Z) - Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems [2.6782615615913348]
本稿では,エントロピーに基づく新しい強化学習手法を提案する。
さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。
我々のモデルは様々な経路問題に一般化可能であることを示す。
論文 参考訳(メタデータ) (2022-05-31T09:51:48Z) - Supervised Permutation Invariant Networks for Solving the CVRP with
Bounded Fleet Size [3.5235974685889397]
車両ルーティング問題などの最適化問題を解くための学習は、大きな計算上の利点をもたらす。
本研究では,アプリオリ固定数の車両を尊重しながら,スクラッチから完全なツアー計画を構築する強力な教師付きディープラーニングフレームワークを提案する。
効率的な後処理方式と組み合わせることで,教師付きアプローチはより高速かつ容易にトレーニングできるだけでなく,競争力のある結果が得られる。
論文 参考訳(メタデータ) (2022-01-05T10:32:18Z) - An Overview and Experimental Study of Learning-based Optimization
Algorithms for Vehicle Routing Problem [49.04543375851723]
車両ルーティング問題(VRP)は典型的な離散最適化問題である。
多くの研究は、VRPを解決するための学習に基づく最適化アルゴリズムについて検討している。
本稿では、最近のこの分野の進歩を概観し、関連するアプローチをエンドツーエンドアプローチとステップバイステップアプローチに分割する。
論文 参考訳(メタデータ) (2021-07-15T02:13:03Z) - Combining Pessimism with Optimism for Robust and Efficient Model-Based
Deep Reinforcement Learning [56.17667147101263]
実世界のタスクでは、強化学習エージェントはトレーニング中に存在しない状況に遭遇する。
信頼性を確保するため、RLエージェントは最悪の状況に対して堅牢性を示す必要がある。
本稿では,Robust Hallucinated Upper-Confidence RL (RH-UCRL)アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-03-18T16:50:17Z) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳(メタデータ) (2021-02-23T15:33:57Z) - Guided Constrained Policy Optimization for Dynamic Quadrupedal Robot
Locomotion [78.46388769788405]
我々は,制約付きポリシー最適化(CPPO)の実装に基づくRLフレームワークであるGCPOを紹介する。
誘導制約付きRLは所望の最適値に近い高速収束を実現し,正確な報酬関数チューニングを必要とせず,最適かつ物理的に実現可能なロボット制御動作を実現することを示す。
論文 参考訳(メタデータ) (2020-02-22T10:15:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。