論文の概要: Deep Reinforcement Learning for Solving the Heterogeneous Capacitated
Vehicle Routing Problem
- arxiv url: http://arxiv.org/abs/2110.02629v1
- Date: Wed, 6 Oct 2021 10:05:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-07 14:12:38.190047
- Title: Deep Reinforcement Learning for Solving the Heterogeneous Capacitated
Vehicle Routing Problem
- Title(参考訳): 不均一容量車両経路問題を解決するための深層強化学習
- Authors: Jingwen Li, Yining Ma, Ruize Gao, Zhiguang Cao, Andrew Lim, Wen Song,
Jie Zhang
- Abstract要約: 現実のシナリオにおける車両は、その能力(または走行速度)に影響を与える異なる特徴を持つ異種である可能性が高い
異種艦隊制約を考慮した車両選択デコーダと経路構成を考慮したノード選択デコーダとを併用した注意機構に基づくDRL手法を提案し,各ステップで車両とノードの両方を自動的に選択して解を構築することを学習する。
- 参考スコア(独自算出の注目度): 13.389057146418056
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Existing deep reinforcement learning (DRL) based methods for solving the
capacitated vehicle routing problem (CVRP) intrinsically cope with homogeneous
vehicle fleet, in which the fleet is assumed as repetitions of a single
vehicle. Hence, their key to construct a solution solely lies in the selection
of the next node (customer) to visit excluding the selection of vehicle.
However, vehicles in real-world scenarios are likely to be heterogeneous with
different characteristics that affect their capacity (or travel speed),
rendering existing DRL methods less effective. In this paper, we tackle
heterogeneous CVRP (HCVRP), where vehicles are mainly characterized by
different capacities. We consider both min-max and min-sum objectives for
HCVRP, which aim to minimize the longest or total travel time of the vehicle(s)
in the fleet. To solve those problems, we propose a DRL method based on the
attention mechanism with a vehicle selection decoder accounting for the
heterogeneous fleet constraint and a node selection decoder accounting for the
route construction, which learns to construct a solution by automatically
selecting both a vehicle and a node for this vehicle at each step. Experimental
results based on randomly generated instances show that, with desirable
generalization to various problem sizes, our method outperforms the
state-of-the-art DRL method and most of the conventional heuristics, and also
delivers competitive performance against the state-of-the-art heuristic method,
i.e., SISR. Additionally, the results of extended experiments demonstrate that
our method is also able to solve CVRPLib instances with satisfactory
performance.
- Abstract(参考訳): 既存の深層強化学習 (drl) に基づくキャパシタ付き車両ルーティング問題 (cvrp) の解法では、一台の車両の繰り返しとして艦隊が想定される均質な車両群に対応している。
したがって、ソリューションを構築するための鍵は、車両の選択を除いて、訪問する次のノード(顧客)の選択にある。
しかし、現実のシナリオにおける車両は、キャパシティ(または走行速度)に影響を与える異なる特徴を持つ異種である可能性が高いため、既存のDRLメソッドの効率は低下する。
本稿では,車種ごとに異なるキャパシティを特徴とする異種CVRP(HCVRP)について検討する。
我々は、車両の最長走行時間または総走行時間を最小化することを目的とした、hcvrpのmin-maxとmin-sumの両方の目的を考える。
これらの問題を解決するために,異種艦隊制約を考慮した車両選択デコーダと経路構成を考慮したノード選択デコーダとを用いた注意機構に基づくDRL手法を提案する。
ランダムに生成した実例に基づく実験結果から,本手法は現状のDRL法や従来のヒューリスティックスよりも優れた性能を示し,また,最先端のヒューリスティック法,すなわちSISRと競合する性能を示した。
さらに,拡張実験の結果から,本手法はCVRPLibインスタンスを良好な性能で解くことができることを示した。
関連論文リスト
- Fair collaborative vehicle routing: A deep multi-agent reinforcement
learning approach [49.00137468773683]
協力的な車両ルーティングは、キャリアがそれぞれの輸送要求を共有し、互いに代表して輸送要求を実行することで協力するときに発生する。
従来のゲーム理論解の概念は、特性関数がエージェントの数とともに指数関数的にスケールするので、計算に費用がかかる。
我々は,この問題を,深層マルチエージェント強化学習を用いて解決した連立交渉ゲームとしてモデル化することを提案する。
論文 参考訳(メタデータ) (2023-10-26T15:42:29Z) - A Feasibility-Preserved Quantum Approximate Solver for the Capacitated
Vehicle Routing Problem [3.2389284835171415]
CVRP(Capacitated Vehicle Routing Problem)は、輸送や物流など様々な分野で発生するNP最適化問題である。
本稿では,CVRPの車載容量制約を回避できる最短経路を最小化する目的関数として,CVRPの新しいバイナリエンコーディングを提案する。
論文 参考訳(メタデータ) (2023-08-17T05:14:43Z) - Unlocking Carbon Reduction Potential with Reinforcement Learning for the
Three-Dimensional Loading Capacitated Vehicle Routing Problem [54.43397200631224]
効率を上げるためのソリューションとして、協調車両ルーティングが提案されている。
現在の運用研究手法は、問題の大きさを増大させる非線形スケーリングに悩まされている。
約線形時間で3次元負荷容量化車両ルーティング問題を解くための強化学習モデルを開発した。
論文 参考訳(メタデータ) (2023-07-22T18:05:28Z) - FastRLAP: A System for Learning High-Speed Driving via Deep RL and
Autonomous Practicing [71.76084256567599]
本稿では、自律型小型RCカーを強化学習(RL)を用いた視覚的観察から積極的に駆動するシステムを提案する。
我々のシステムであるFastRLAP (faster lap)は、人間の介入なしに、シミュレーションや専門家によるデモンストレーションを必要とせず、現実世界で自律的に訓練する。
結果として得られたポリシーは、タイミングブレーキや回転の加速度などの突発的な運転スキルを示し、ロボットの動きを妨げる領域を避け、トレーニングの途中で同様の1対1のインタフェースを使用して人間のドライバーのパフォーマンスにアプローチする。
論文 参考訳(メタデータ) (2023-04-19T17:33:47Z) - Unified Automatic Control of Vehicular Systems with Reinforcement
Learning [64.63619662693068]
本稿では,車載マイクロシミュレーションの合理化手法について述べる。
最小限の手動設計で高性能な制御戦略を発見する。
この研究は、波動緩和、交通信号、ランプ計測に類似した多くの創発的挙動を明らかにしている。
論文 参考訳(メタデータ) (2022-07-30T16:23:45Z) - Supervised Permutation Invariant Networks for Solving the CVRP with
Bounded Fleet Size [3.5235974685889397]
車両ルーティング問題などの最適化問題を解くための学習は、大きな計算上の利点をもたらす。
本研究では,アプリオリ固定数の車両を尊重しながら,スクラッチから完全なツアー計画を構築する強力な教師付きディープラーニングフレームワークを提案する。
効率的な後処理方式と組み合わせることで,教師付きアプローチはより高速かつ容易にトレーニングできるだけでなく,競争力のある結果が得られる。
論文 参考訳(メタデータ) (2022-01-05T10:32:18Z) - Learning Vehicle Routing Problems using Policy Optimisation [4.093722933440819]
最先端のアプローチは強化学習を使ってポリシーを学習し、学習ポリシーは擬似解法として機能する。
これらのアプローチは、あるケースでは優れた性能を示しているが、ルーティング問題に典型的な大きな検索空間を考えると、ポリシーの貧弱さに早すぎる可能性がある。
より多くのポリシーを提供することで探索を支援するエントロピー正規化強化学習(ERRL)を提案する。
論文 参考訳(メタデータ) (2020-12-24T14:18:56Z) - Vehicular Cooperative Perception Through Action Branching and Federated
Reinforcement Learning [101.64598586454571]
強化学習に基づく車両関連、リソースブロック(RB)割り当て、協調認識メッセージ(CPM)のコンテンツ選択を可能にする新しいフレームワークが提案されている。
車両全体のトレーニングプロセスをスピードアップするために、フェデレーションRLアプローチが導入されます。
その結果、フェデレーションRLはトレーニングプロセスを改善し、非フェデレーションアプローチと同じ時間内により良いポリシーを達成できることが示された。
論文 参考訳(メタデータ) (2020-12-07T02:09:15Z) - Decision-making for Autonomous Vehicles on Highway: Deep Reinforcement
Learning with Continuous Action Horizon [14.059728921828938]
本稿では,高速道路における連続水平決定問題に対処するために,深部強化学習(DRL)手法を用いる。
エゴ自動車両の走行目標は、衝突することなく効率的でスムーズなポリシーを実行することである。
PPO-DRLに基づく意思決定戦略は、最適性、学習効率、適応性など、複数の観点から推定される。
論文 参考訳(メタデータ) (2020-08-26T22:49:27Z) - A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle
Routing Problem [5.057312718525522]
本稿では,AQC(Adiabatic Quantum Computation)の原理に基づく量子コンピューティングアルゴリズムを提案する。
従来のアルゴリズムと比較して、車両ルーティング問題(VRP)のような最適化問題の解法において、計算上の利点が顕著に示された。
これは、輸送、物流、サプライチェーン管理の分野における実世界の応用におけるNPハード最適化問題である。
論文 参考訳(メタデータ) (2020-05-26T01:47:39Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳(メタデータ) (2020-01-22T08:51:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。