論文の概要: DeepMDV: Learning Global Matching for Multi-depot Vehicle Routing Problems
- arxiv url: http://arxiv.org/abs/2411.17080v1
- Date: Tue, 26 Nov 2024 03:41:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-04 17:41:51.459792
- Title: DeepMDV: Learning Global Matching for Multi-depot Vehicle Routing Problems
- Title（参考訳）: DeepMDV: マルチデポッド車両ルーティング問題に対するグローバルマッチング学習
- Authors: Saeed Nasehi, Farhana Choudhury, Egemen Tanin,
- Abstract要約: 近年、企業はより多くの補給所を追加する戦略を採用してきた。
複数の補給所の存在は、既存のVRPソリューションを最適にするために、さらなる複雑さをもたらす。
従来のMDVRPの解法は時間を要することが多く、大規模なインスタンスには適さない。
本稿では,2つの鍵層を持つデコーダを特徴とするアテンション機構を用いたMDVRPの新しい解を提案する。
- 参考スコア（独自算出の注目度）: 1.0104586293349587
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Due to the substantial rise in online retail and e-commerce in recent years, the demand for efficient and fast solutions to Vehicle Routing Problems (VRP) has become critical. To manage the increasing demand, companies have adopted the strategy of adding more depots. However, the presence of multiple depots introduces additional complexities, making existing VRP solutions suboptimal for addressing the Multi-depot Vehicle Routing Problem (MDVRP). Traditional methods for solving the MDVRP often require significant computation time, making them unsuitable for large-scale instances. Additionally, existing learning-based solutions for the MDVRP struggle with generalizability and fail to deliver high-quality results for scenarios involving a large number of customers. In this paper, we propose a novel solution for MDVRP. Our approach employs an attention mechanism, featuring a decoder with two key layers: one layer to consider the states of all vehicles and learn to select the most suitable vehicle based on the proximity of unassigned customers, and another layer to focus on assigning a customer to the selected vehicle. This approach delivers high-quality solutions for large-scale MDVRP instances and demonstrates remarkable generalizability across varying numbers of customers and depots. Its adaptability and performance make it a practical and deployable solution for real-world logistics challenges.
- Abstract（参考訳）: 近年のオンライン小売・電子商取引の大幅な増加により、車両ルーティング問題(VRP)に対する効率的かつ迅速なソリューションの需要が重要になっている。
需要の増加を管理するため、企業はより多くの補給所を追加する戦略を採用した。
しかし、複数の補給所が存在するため、既存のVRPソリューションはMDVRP(Multi-depot Vehicle Routing Problem)に対処するのに最適である。
従来のMDVRPの解法は計算時間を要することが多く、大規模なインスタンスには適さない。
さらに、MDVRPの既存の学習ベースのソリューションは、汎用性に苦しむと同時に、多数の顧客が関与するシナリオに対して高品質な結果の提供に失敗している。
本稿では,MDVRPの新しい解法を提案する。
提案手法では,全車両の状態を考慮し,未指定の顧客に近接して最適な車両を選択するためのレイヤと,選択した車両に顧客を割り当てることに焦点を当てるレイヤという,2つの重要なレイヤを持つデコーダを特徴とするアテンションメカニズムを採用している。
このアプローチは、大規模なMDVRPインスタンスに対して高品質なソリューションを提供し、さまざまな顧客やデポにまたがる顕著な一般化性を示す。
その適応性とパフォーマンスは、現実の物流の課題に対して実用的でデプロイ可能なソリューションになります。
関連論文リスト
- Deep Reinforcement Learning for Solving the Fleet Size and Mix Vehicle Routing Problem [8.127336287332783]
FSMVRP(Fleet Size and Mix Vehicle Routing Problem)は、VRP(Fleet Size and Mix Vehicle Routing Problem)の変種である。
本稿では,FSMVRPを解くための深層強化学習(DRL)に基づく手法を提案する。
本手法は,特に大規模かつ時間制約のあるシナリオにおいて,計算効率とスケーラビリティにおいて顕著な優位性を示す。
論文 参考訳（メタデータ） (2025-12-30T14:26:33Z) - Multi-Agent Pointer Transformer: Seq-to-Seq Reinforcement Learning for Multi-Vehicle Dynamic Pickup-Delivery Problems [17.3780399150554]
本稿では,シーケンス・ツー・シーケンスに基づくエンドツーエンドの集中型意思決定フレームワークであるMulti-Agent Pointer Transformer(MAPT)を提案する。
MAPTは、古典的な操作研究手法と比較して、性能と計算時間の優位性という点で、既存のベースライン手法を著しく上回っている。
論文 参考訳（メタデータ） (2025-11-21T17:32:10Z) - An End-to-End Learning Approach for Solving Capacitated Location-Routing Problems [8.616895584914579]
CLRP(capacitated location-routing problem)に対するエンドツーエンド学習手法を提案する。
特に、CLRPを様々な決定に合わせたマルコフ決定プロセスとして再構成する。
また、様々な意思決定段階に動的に適応するように設計された、新しい異種クエリアテンション機構も導入する。
論文 参考訳（メタデータ） (2025-11-04T12:23:17Z) - Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP [57.28979643999352]
本稿では,VRPの変種間で共有成分の性質を認識可能な統合解法フレームワークを提案する。
状態空間を基底状態空間のカルテアン積として表現することにより、VRPを再構成する状態分解型MDP(SDMDP)を導入する。
The Latent Space-based SDMDP extension is developed by the both the optimal basis policy and a learnable mix function。
論文 参考訳（メタデータ） (2025-10-24T13:31:31Z) - An Agentic Framework with LLMs for Solving Complex Vehicle Routing Problems [66.60904891478687]
複雑な車両ルーティング問題を解決するために,LLM (AFL) を用いたエージェントフレームワークを提案する。
AFLは生の入力から知識を直接抽出し、自己完結型コード生成を可能にする。
AFLは、コード信頼性とソリューション実現性の両方において、既存のLCMベースのベースラインを大幅に上回っていることを示す。
論文 参考訳（メタデータ） (2025-10-19T03:59:25Z) - Rich Vehicle Routing Problem in Disaster Management enabling Temporally-causal Transhipments across Multi-Modal Transportation Network [1.1470070927586018]
地理的に分散した車両基地に複数台の異種車両を配置し、異なる交通手段を利用できるような、豊富な車両経路問題も検討されている。
この問題は、車両経路の等間隔を最小化することで災害応答時間を最適化する現実的な要件から生じる。
提案手法の優位性は,Mixed-Integer Linear Programmingの定式化によって実証された。
論文 参考訳（メタデータ） (2025-09-16T16:37:18Z) - Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [55.78505925402658]
車両ルーティング問題(VRP)は、トラベリングセールスパーソン問題の延長であり、進化的最適化における基本的なNPハードチャレンジである。
遺伝的アルゴリズムによってさらに最適化された初期解を迅速に生成するために、強化学習エージェント(事前インスタンスで訓練された)を使用した新しい最適化フレームワークを導入する。
例えば、EARLIは1秒以内に500カ所の車両ルーティングを処理し、同じソリューション品質の現在のソルバよりも10倍高速で、リアルタイムやインタラクティブなルーティングのようなアプリケーションを可能にする。
論文 参考訳（メタデータ） (2025-04-08T15:21:01Z) - Agent-Oriented Planning in Multi-Agent Systems [54.429028104022066]
マルチエージェントシステムにおけるエージェント指向計画のための新しいフレームワークであるAOPを提案する。
本研究では, エージェント指向計画の3つの重要な設計原則, 可解性, 完全性, 非冗長性を明らかにする。
大規模実験は,マルチエージェントシステムにおける単一エージェントシステムと既存の計画戦略と比較して,現実の問題を解決する上でのAOPの進歩を実証している。
論文 参考訳（メタデータ） (2024-10-03T04:07:51Z) - Deep Reinforcement Learning for Traveling Purchaser Problems [63.37136587778153]
旅行購入問題(TPP)は幅広いアプリケーションにおいて重要な最適化問題である。
本稿では,ルート構築と購入計画を個別に扱う,深層強化学習(DRL)に基づく新しいアプローチを提案する。
様々な合成TPPインスタンスとTPPLIBベンチマークの実験により、我々のDRLベースのアプローチは、確立されたTPPを著しく上回ることを示した。
論文 参考訳（メタデータ） (2024-04-03T05:32:10Z) - Multimodal Instruction Tuning with Conditional Mixture of LoRA [54.65520214291653]
本稿では,Low-Rank Adaption (LoRA) とマルチモーダル命令チューニングを統合した新しい手法を提案する。
各入力インスタンスのユニークな要求に合わせた低ランク適応行列を動的に構築することで、LoRAを革新する。
様々なマルチモーダル評価データセットの実験結果から、MixLoRAは従来のLoRAを同等以上のランクで上回るだけでなく、性能も向上していることが示された。
論文 参考訳（メタデータ） (2024-02-24T20:15:31Z) - Deep Reinforcement Learning for Multi-Truck Vehicle Routing Problems with Multi-Leg Demand Routes [0.9423257767158634]
既存のエンコーダ・デコーダのアテンションモデルに新たな拡張を加えて,複数のトラックとマルチレグルーティング要求を処理できるようにした。
私たちのモデルには、少数のトラックやノードに対してトレーニングを行い、大きなサプライチェーンに組み込んで、多数のトラックやノードに対するソリューションを提供するという利点があります。
論文 参考訳（メタデータ） (2024-01-08T21:13:07Z) - TOP-Former: A Multi-Agent Transformer Approach for the Team Orienteering Problem [47.40841984849682]
車両群のためのルートプランニングは、荷物の配送、監視、輸送といった応用において重要な課題である。
ToP-Formerは、チームのオリエンテーリング問題を効率的に正確に解くために設計されたマルチエージェント経路計画ニューラルネットワークである。
論文 参考訳（メタデータ） (2023-11-30T16:10:35Z) - Safe Model-Based Multi-Agent Mean-Field Reinforcement Learning [48.667697255912614]
平均場強化学習は、同一エージェントの無限集団と相互作用する代表エージェントのポリシーに対処する。
モデルベースの平均場強化学習アルゴリズムであるSafe-M$3$-UCRLを提案する。
本アルゴリズムは,低需要領域におけるサービスアクセシビリティを確保しつつ,重要な領域における需要を効果的に満たす。
論文 参考訳（メタデータ） (2023-06-29T15:57:07Z) - Flexible Job Shop Scheduling via Dual Attention Network Based
Reinforcement Learning [73.19312285906891]
フレキシブルなジョブショップスケジューリング問題(FJSP)では、複数のマシンで操作を処理でき、操作とマシンの間の複雑な関係が生じる。
近年, 深層強化学習(DRL)を用いて, FJSP解決のための優先派遣規則(PDR)を学習している。
本稿では,Deep機能抽出のための自己注意モデルと,スケーラブルな意思決定のためのDRLの利点を生かした,エンドツーエンド学習フレームワークを提案する。
論文 参考訳（メタデータ） (2023-05-09T01:35:48Z) - Modeling routing problems in QUBO with application to ride-hailing [0.0]
このようなルーティング問題のひとつ,RPP(Ride Pooling Problem)に注力しています。
このタスクは、小規模な柔軟なバスルートに似た、限られた車両セットを使用して顧客の要求を最適にプールすることである。
論文 参考訳（メタデータ） (2022-12-09T14:55:34Z) - Learning Collaborative Policies to Solve NP-hard Routing Problems [13.13675711285772]
本稿では,学習協調政策(LCP)と呼ばれる新しい階層的問題解決戦略を提案する。
2つの反復DRLポリシー(シードとリバイザ)を使って、ほぼ最適解を効果的に見つけることができる。
広汎な実験により,提案した2都市連携方式は,NP-ハードルーティング問題に対する単都市DRLフレームワークよりも改善されることが示された。
論文 参考訳（メタデータ） (2021-10-26T19:46:21Z) - Off-line approximate dynamic programming for the vehicle routing problem
with stochastic customers and demands via decentralized decision-making [0.0]
本稿では,顧客の位置と需要が不確実な車両経路問題(VRP)の変種について検討する。
目的は、車両の容量と時間制限を満たしながら、提供された要求を最大化することである。
本稿では,Replay MemoryやDouble Q Networkといった最先端のアクセラレーション技術を用いたQラーニングアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-09-21T14:28:09Z) - Value Function is All You Need: A Unified Learning Framework for Ride
Hailing Platforms [57.21078336887961]
DiDi、Uber、Lyftなどの大型配車プラットフォームは、都市内の数万台の車両を1日中数百万の乗車要求に接続している。
両課題に対処するための統合価値に基づく動的学習フレームワーク(V1D3)を提案する。
論文 参考訳（メタデータ） (2021-05-18T19:22:24Z) - Flatland Competition 2020: MAPF and MARL for Efficient Train
Coordination on a Grid World [49.80905654161763]
車両再スケジュール問題(vrsp)の解法開発を目的としたフラットランドコンペティション
VRSPは、交通ネットワークにおける旅行のスケジュールと、故障が発生した場合の車両の再スケジュールに関するものである。
現代の鉄道網の複雑化は、交通の動的リアルタイムスケジューリングを事実上不可能にします。
論文 参考訳（メタデータ） (2021-03-30T17:13:29Z) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳（メタデータ） (2021-02-23T15:33:57Z) - A Three-Stage Algorithm for the Large Scale Dynamic Vehicle Routing
Problem with an Industry 4.0 Approach [3.6317403990273402]
業界 4.0 はモビリティとリアルタイム統合に焦点を当てたコンセプトである。
本研究の目的は,大規模DVRP(LSDVRP)の解決である。
論文 参考訳（メタデータ） (2020-08-26T10:39:36Z) - Learning What to Defer for Maximum Independent Sets [84.00112106334655]
本稿では,各段階における解の要素的決定を学習することにより,エージェントが適応的に段階数を縮小あるいは拡張する,新たなDRL方式を提案する。
提案手法を最大独立集合(MIS)問題に適用し、現状のDRL方式よりも大幅に改善したことを示す。
論文 参考訳（メタデータ） (2020-06-17T02:19:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。