論文の概要: Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency
- arxiv url: http://arxiv.org/abs/2607.06066v1
- Date: Tue, 07 Jul 2026 09:37:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-08 21:24:51.47156
- Title: Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency
- Title（参考訳）: 動的マルチサイクルルーティングのための逆密度ヒューリスティック:性能と計算効率
- Abstract要約: 車両問題(VRP)とオリエンテーリング問題(OP)の要素を組み合わせた動的オンライン変種に対処する。
本稿では,効率ルーティングと呼ばれる動的多車割当に対する報酬密度を提案し,評価する。
テストされたすべての構成の中で、効率は最高のメタヒューリスティックアルゴリズムの解の質と一致し、2～3桁の計画時間を必要とする。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Vehicle Routing Problem (VRP) and its variants represent some of the most practically consequential optimization challenges in modern logistics and urban mobility. In this study, we address a dynamic, online variant combining elements of the VRP and the Orienteering Problem (OP), in which a fleet of vehicles must maximise cumulative reward collected within a fixed time horizon while continuously replanning as new tasks arrive. We propose and evaluate a reward-density heuristic for dynamic multi-vehicle assignment, referred to as the Efficiency heuristic. We evaluate this formulation across two application domains: autonomous drone task allocation and urban taxi dispatch, across multiple fleet sizes and task scales. The proposed method is compared with four classical construction heuristics and three metaheuristic algorithms (Adaptive Large Neighbourhood Search, Genetic Algorithm, and Simulated Annealing), all evaluated under identical conditions. Across all tested configurations, the Efficiency heuristic matches the solution quality of the best metaheuristic algorithms while requiring two to three orders of magnitude less planning time, establishing Pareto dominance over all competing methods on the reward-versus-compute frontier. These findings suggest a practical design principle for real-time allocation and dispatch systems: in dynamic, time-constrained routing environments, carefully designed greedy heuristics can match the output of sophisticated search procedures at a fraction of the computational cost, making them preferable for online deployment.
- Abstract（参考訳）: 車両ルーティング問題(VRP)とその変種は、現代の物流と都市移動における最も実用的な最適化課題の1つである。
本研究では,VRP と Orienteering Problem (OP) の要素を組み合わせた動的オンライン変種に対処し,車両群が一定時間内に収集した累積報酬を最大化しつつ,新たなタスクが到着するたびに継続的に計画する。
本稿では,動的多車割当のための報酬密度ヒューリスティックを提案・評価し,効率ヒューリスティックと呼ぶ。
この定式化は、自律ドローンタスクアロケーションと都市タクシーディスパッチの2つのアプリケーション領域で、複数の車両サイズとタスクスケールで評価する。
提案手法は,4つの古典的構成ヒューリスティックと3つのメタヒューリスティックアルゴリズム(適応大近傍探索,遺伝的アルゴリズム,シミュレーテッドアニーリング)を同一条件で評価した。
すべてのテストされた構成の中で、効率ヒューリスティックは最高のメタヒューリスティックアルゴリズムの解の質と一致し、プランニング時間を大幅に短縮し、報酬計算フロンティア上の競合するすべてのメソッドに対してパレート優位を確立した。
動的で時間に制約のあるルーティング環境において、慎重に設計された欲求的ヒューリスティックスは、高度な探索手順の出力を計算コストのごく一部で一致させることができるため、オンライン展開に好適である。
関連論文リスト
- HAD: Combining Hierarchical Diffusion with Metric-Decoupled RL for End-to-End Driving [51.268878540511054]
我々は階層的拡散政策を備えたエンドツーエンドの計画フレームワークであるHADを提案する。
我々は,NAVSIMとHUGSIMの両方でHADが新たな最先端性能を実現することを示す。
論文 参考訳（メタデータ） (2026-04-04T04:12:47Z) - Experience-Guided Reflective Co-Evolution of Prompts and Heuristics for Automatic Algorithm Design [124.54166764570972]
組合せ最適化問題は伝統的に手作りのアルゴリズムで取り組まれている。
最近の進歩は、大規模言語モデルによる自動設計の可能性を強調している。
本稿では,自動アルゴリズム設計のためのPmpt and Heuristics (EvoPH) を用いた経験進化的リフレクティブ・ガイドを提案する。
論文 参考訳（メタデータ） (2025-09-29T09:24:09Z) - Dynamic Location Search for Identifying Maximum Weighted Independent Sets in Complex Networks [0.47248250311484113]
本稿では,最大重み付き独立集合(MWIS)問題を解くための,新しい,効率的なアルゴリズムを提案する。
MWIS問題のNPハード性を考えると,提案アルゴリズムであるDynLSには3つの重要なイノベーションが組み込まれている。
我々の実験結果はDynLSの優れた性能を示し、1000秒以内の高品質なソリューションを一貫して提供した。
論文 参考訳（メタデータ） (2025-05-07T10:35:53Z) - Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
車両ルーティング問題 (VRP) は進化的最適化における基本的なNPハード問題である。
本稿では、強化学習エージェントを事前のインスタンスで訓練し、初期解を迅速に生成する最適化フレームワークを提案する。
このフレームワークは、様々な時間予算において、現在の最先端のソルバよりも一貫して優れています。
論文 参考訳（メタデータ） (2025-04-08T15:21:01Z) - A Coalition Game for On-demand Multi-modal 3D Automated Delivery System [4.378407481656902]
都市環境におけるラストマイル配送に対処するため、2つのオーバーレイネットワークで運用するUAVとADRの連合ゲームを導入する。
戦略的協調が全体のルーティング効率をいかに向上させるかを把握するためのモード間の協調構造について検討する。
ミシサガ市におけるケーススタディの結果から,ラストマイル配送の応用に関するいくつかの数値実験が実施されている。
論文 参考訳（メタデータ） (2024-12-23T03:50:29Z) - 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) - 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) - Controllable Dynamic Multi-Task Architectures [92.74372912009127]
本稿では,そのアーキテクチャと重みを動的に調整し,所望のタスク選択とリソース制約に適合させる制御可能なマルチタスクネットワークを提案する。
本稿では,タスク親和性と分岐正規化損失を利用した2つのハイパーネットの非交互トレーニングを提案し,入力の嗜好を取り入れ,適応重み付き木構造モデルを予測する。
論文 参考訳（メタデータ） (2022-03-28T17:56:40Z) - 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) - Integrated Decision and Control: Towards Interpretable and Efficient
Driving Intelligence [13.589285628074542]
自動走行車のための解釈可能かつ効率的な意思決定・制御フレームワークを提案する。
駆動タスクを階層的に構造化されたマルチパス計画と最適追跡に分解する。
その結果,オンライン計算の効率性や交通効率,安全性などの運転性能が向上した。
論文 参考訳（メタデータ） (2021-03-18T14:43:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。