論文の概要: Optimization of Multi-Agent Flying Sidekick Traveling Salesman Problem over Road Networks
- arxiv url: http://arxiv.org/abs/2408.11187v1
- Date: Tue, 20 Aug 2024 20:44:18 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-22 21:06:50.025307
- Title: Optimization of Multi-Agent Flying Sidekick Traveling Salesman Problem over Road Networks
- Title（参考訳）: 道路ネットワーク上でのマルチエージェントフライングサイドキックトラベリングセールスマン問題の最適化
- Authors: Ruixiao Yang, Chuchu Fan,
- Abstract要約: 道路ネットワーク上でのマルチエージェント飛行サイドキック走行セールスマン問題(MA-FSTSP)について紹介する。
このNPハード問題に対して,混合整数線形計画モデルと効率的な3相アルゴリズムを提案する。
当社のアプローチは5分間の時間制限内で300以上の顧客にスケールし、大規模な実世界のロジスティクスアプリケーションの可能性を示している。
- 参考スコア（独自算出の注目度）: 10.18252143035175
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The mixed truck-drone delivery systems have attracted increasing attention for last-mile logistics, but real-world complexities demand a shift from single-agent, fully connected graph models to multi-agent systems operating on actual road networks. We introduce the multi-agent flying sidekick traveling salesman problem (MA-FSTSP) on road networks, extending the single truck-drone model to multiple trucks, each carrying multiple drones while considering full road networks for truck restrictions and flexible drone routes. We propose a mixed-integer linear programming model and an efficient three-phase heuristic algorithm for this NP-hard problem. Our approach decomposes MA-FSTSP into manageable subproblems of one truck with multiple drones. Then, it computes the routes for trucks without drones in subproblems, which are used in the final phase as heuristics to help optimize drone and truck routes simultaneously. Extensive numerical experiments on Manhattan and Boston road networks demonstrate our algorithm's superior effectiveness and efficiency, significantly outperforming both column generation and variable neighborhood search baselines in solution quality and computation time. Notably, our approach scales to more than 300 customers within a 5-minute time limit, showcasing its potential for large-scale, real-world logistics applications.
- Abstract（参考訳）: トラックとドローンの混合配送システムは、ラストマイルのロジスティクスに注目が集まっているが、現実の複雑さは、単一のエージェントで完全に接続されたグラフモデルから、実際のロードネットワークで動作するマルチエージェントシステムへの移行を要求する。
道路ネットワーク上でのマルチエージェント飛行サイドキック走行セールスマン問題 (MA-FSTSP) を導入し, トラックの規制やフレキシブルなルートを考慮しつつ, 複数のドローンを積載する単一トラックドローンモデルを複数トラックに拡張した。
このNPハード問題に対する混合整数線形計画モデルと効率的な3相ヒューリスティックアルゴリズムを提案する。
提案手法は,MA-FSTSPを1台のトラックと複数のドローンの制御可能なサブプロブレムに分解する。
そして、最終フェーズでドローンとトラックのルートを同時に最適化するためのヒューリスティックとして使用される、サブプロブレムのドローンのないトラックのルートを計算する。
マンハッタンとボストンの道路網における大規模な数値実験により,提案アルゴリズムの有効性と効率が向上し,解の質と計算時間において,カラム生成および可変近傍探索ベースラインを著しく上回った。
特に、当社のアプローチは5分間の時間制限内で300以上の顧客に拡張されており、大規模な実世界のロジスティクスアプリケーションの可能性を示している。
関連論文リスト
- Robotic warehousing operations: a learn-then-optimize approach to large-scale neighborhood search [84.39855372157616]
本稿では,ワークステーションの注文処理,アイテムポッドの割り当て,ワークステーションでの注文処理のスケジュールを最適化することで,ウェアハウジングにおけるロボット部品対ピッカー操作を支援する。
そこで我々は, 大規模近傍探索を用いて, サブプロブレム生成に対する学習を最適化する手法を提案する。
Amazon Roboticsと共同で、我々のモデルとアルゴリズムは、最先端のアプローチよりも、実用的な問題に対するより強力なソリューションを生み出していることを示す。
論文 参考訳（メタデータ） (2024-08-29T20:22:22Z) - Deep Reinforcement Learning for Multi-Truck Vehicle Routing Problems with Multi-Leg Demand Routes [0.9423257767158634]
既存のエンコーダ・デコーダのアテンションモデルに新たな拡張を加えて,複数のトラックとマルチレグルーティング要求を処理できるようにした。
私たちのモデルには、少数のトラックやノードに対してトレーニングを行い、大きなサプライチェーンに組み込んで、多数のトラックやノードに対するソリューションを提供するという利点があります。
論文 参考訳（メタデータ） (2024-01-08T21:13:07Z) - Coordinated Multi-Agent Pathfinding for Drones and Trucks over Road
Networks [31.52357826598224]
我々は、大規模な都市道路ネットワーク上でドローンとトラックのチームをルーティングする問題に対処する。
ドローンは、目的地に向かう途中の一時的な移動モードとしてトラックを使用することができる。
しかし、どのトラックとドローンを連携させるべきかを判断する計算コストは、潜在的に禁じられている。
論文 参考訳（メタデータ） (2021-10-17T12:00:30Z) - Road Network Guided Fine-Grained Urban Traffic Flow Inference [108.64631590347352]
粗いトラフィックからのきめ細かなトラフィックフローの正確な推測は、新たな重要な問題である。
本稿では,道路ネットワークの知識を活かした新しい道路対応交通流磁化器(RATFM)を提案する。
提案手法は,高品質なトラフィックフローマップを作成できる。
論文 参考訳（メタデータ） (2021-09-29T07:51:49Z) - Exact and Heuristic Approaches to Drone Delivery Problems [0.0]
FSTSP(Flying Sidekick Traveling Salesman Problem)は、トラックとドローンによる配送システムである。
それぞれのドローンはトラックに戻り、バッテリーを充電し、別の荷物を拾い、また新しい顧客場所に打ち上げなければならない。
この研究は、新しい混合プログラミング(MIP)の定式化と、この問題に対処するためのアプローチを提案する。
論文 参考訳（メタデータ） (2021-07-29T21:31:50Z) - Dynamic Bicycle Dispatching of Dockless Public Bicycle-sharing Systems
using Multi-objective Reinforcement Learning [79.61517670541863]
ドッキングレスPBS(DL-PBS)に欠かせない動的自転車レンタル需要に基づく効率的な自転車配車ソリューションを実現するためのAIの活用
DL-PBSに最適な自転車ディスパッチソリューションを提供するために、マルチオブジェクト強化学習(MORL-BD)に基づく動的自転車ディスパッチアルゴリズムを提案します。
論文 参考訳（メタデータ） (2021-01-19T03:09:51Z) - Multi-Agent Reinforcement Learning in NOMA-aided UAV Networks for
Cellular Offloading [59.32570888309133]
複数の無人航空機(UAV)によるセルローディングのための新しい枠組みの提案
非直交多重アクセス(NOMA)技術は、無線ネットワークのスペクトル効率をさらに向上するために、各UAVに採用されている。
相互深いQ-network (MDQN) アルゴリズムは,UAVの最適3次元軌道と電力配分を共同で決定するために提案される。
論文 参考訳（メタデータ） (2020-10-18T20:22:05Z) - NOMA in UAV-aided cellular offloading: A machine learning approach [59.32570888309133]
複数の無人航空機(UAV)によるセルローディングのための新しい枠組みの提案
非直交多重アクセス(NOMA)技術は、無線ネットワークのスペクトル効率をさらに向上するために、各UAVに採用されている。
相互深いQ-network (MDQN) アルゴリズムは,UAVの最適3次元軌道と電力配分を共同で決定するために提案される。
論文 参考訳（メタデータ） (2020-10-18T17:38:48Z) - Multi-Agent Routing Value Iteration Network [88.38796921838203]
疎結合グラフの学習値に基づいてマルチエージェントルーティングを行うことができるグラフニューラルネットワークに基づくモデルを提案する。
最大25ノードのグラフ上で2つのエージェントでトレーニングしたモデルでは,より多くのエージェントやノードを持つ状況に容易に一般化できることが示されている。
論文 参考訳（メタデータ） (2020-07-09T22:16:45Z) - Extending the Multiple Traveling Salesman Problem for Scheduling a Fleet
of Drones Performing Monitoring Missions [4.477547027158141]
事前に定義された地点でノードを複数回訪問する必要があるグラフ上で、一連のドローンの走行経路をスケジュールする方法を示す。
提案した定式化は,交通ネットワークにおける交通流のモニタリングや遠隔地からの探索・救助活動の監視など,いくつかの領域に適用することができる。
詳細な評価では、グリーディアルゴリズムは最適の92.06%でほぼ最適性能を示し、数百台のドローンや位置で設定できる可能性がある。
論文 参考訳（メタデータ） (2020-06-02T09:17:18Z) - The two-echelon routing problem with truck and drones [0.0]
我々は、トラックが最初のエケロンでパーセルとドローンの群を中間補給所へ輸送する、よく知られた2エケロン車両ルーティング問題の新しい変種について研究する。
目的は、古典的な2エケロン車両の経路問題のように、輸送コストの代わりに完成時間を最小化することである。
論文 参考訳（メタデータ） (2020-04-05T18:33:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。