Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency

技術要約：動的な複数車両ルーティングのための報酬密度ヒューリスティック

問題定義
本論文は、オリエンテーリング問題（OP）の要素を統合した、動的かつオンラインな車両ルーティング問題（VRP）の変種を取り扱っている。この定式化では、一定のタイムホライゾン内で累積報酬を最大化するために、艦隊（フリート）が運用される。静的なVRPの変種とは異なり、タスクは動的（オンライン）に発生するため、継続的な再計画が必要となる。この問題は車両ごとのタイムバジェットによって制約されており、車両は「移動時間とサービス時間の合計が残りの予算を超えない」場合にのみタスクを割り当てることができる。この構造は、新しいリクエストが発生するたびにミリ秒単位で割り当て決定を行う必要がある、自律型ドローンのタスク割り当てや都市部のタクシー配車といった実世界のシナリオをモデル化している。

手法
著者らは、「報酬密度ヒューリスティック」（効率性ヒューリスティックと呼称）を、4つの構成ヒューリスティックおよび3つのメタヒューリスティック・アルゴリズムと比較して提案し、評価している。

1. 提案手法（効率性ヒューリスティック）:
   本手法の核となるのは、報酬密度に基づくスコアリング関数であり、これはタスクの報酬（$R$）と総時間コスト（移動時間 $d$ + サービス時間 $s$）の比として定義される：
   $$\eta(\tau) = \frac{R(\tau)}{d(v, \tau) + s(\tau)}$$
   2つの実装がテストされている：

   • Greedy-Efficiency（強欲型効率性）: 利用可能な各車両に対し、未確保の実現可能なターゲットの中からスコアが最も高いものを逐次的に割り当てる。
   • Hungarian-Efficiency（ハンガリー法による効率性）: 負の報酬密度（$-\eta$）をコスト行列として用いて、割り当てを線形割当問題（LAP）として定式化し、ハンガリー法を用いて最適に解く。

2. 比較対象のベースライン:

   • 構成ヒューリスティック: Greedy-Nearest（距離を最小化）、Greedy-Reward（生の報酬を最大化）、Hungarian-Time（移動時間を最小化）、および Hungarian-Reward（LAPを介して生の報酬を最大化）。
   • メタヒューリスティック: 適応的大規模近傍探索（ALNS）、遺伝的アルゴリズム（GA）、および焼きなまし法（SA）。これらは、変化する環境に適応するために、毎回の再計画イベント時に再初期化される。

3. 実験設定:
   研究では、タスク完了時に再計画がトリガーされるイベント駆動型シミュレータを使用している。評価は以下の2つのドメインで行われた：

   • 合成ドローン環境: $5000 \times 5000$ のマップ上で動作する12、20、50機のドローンと、50〜200個のターゲット。
   • 実世界のタクシー配車: NYC TLC Yellow Cab 2024データセットから派生した約7,600のタスクに対し、120分間動作する50台および200台のタクシー。
     パフォーマンスは、累積報酬（または収益）および計画時間（計算コスト）によって測定される。

主要な結果
実験の結果、効率性ヒューリスティックがすべての競合手法に対して明確なパレート優位性を示すことが実証された：

• 解の質: 効率性ヒューリスティック（GreedyおよびHungarianの両方の変種）は、すべての艦隊規模およびドメインにおいて、最高の性能を示すメタヒューリスティック（ALNS、GA、SA）と統計的に区別がつかない解の質を達成した。対照的に、単純なヒューリスティック（Greedy-Nearest、Greedy-Reward、Hungarian-Time、Hungarian-Reward）は、報酬/収益において統計的に有意な不足を伴い、一貫して下回った。
• 計算効率: 効率性ヒューリスティックは、メタヒューリスティックよりも2桁から3桁少ない計画時間しか必要としない。
  • 50ドローンのシナリオでは、Hungarian-Efficiencyは約128 msを要したのに対し、GAは約110万 ms、ALNSは約42,654 ms、SAは約5,247 msを要した。
  • 200タクシーのシナリオでは、Hungarian-Efficiencyは約363 msを要したのに対し、GAは約458万 msを要した。
• Greedy vs. 全域最適性: 本研究では、計算コストの低いGreedy-Efficiencyのアプローチが、グローバルに最適なHungarian-Efficiencyと統計的に同等の結果をもたらすことが判明した。これは、ハンガリー法によるグローバルな最適性の保証が、このような動的で高頻度な設定においては限定的な実用的利益しか提供しないことを示唆している。

意義と主張
本論文は、最適化基準の選択（報酬密度/効率性）は、割り当てメカニズムの精緻化よりも重要であると主張している。

• 構造的優位性: 効率性ヒューリスティックの成功は、動的な報酬最大化ルーティングにおいて、報酬とコストの比（効率性）が、生の報酬や移動時間のみを最適化することよりも、艦隊レベルの価値創出の優れたプロキシ（代理指標）であることを示唆している。
• 実用的な生存可能性: メタヒューリスティックは同等の解の質の上限に到達できる能力を持つ一方で、リアルタイムの配車には不向きな計画時間を要する。数分間の計画サイクルは、ソリューションが生成される前に環境が実質的に変化してしまうため、ライブ運用においては「積極的に有害である」と記述されている。
• パレート優位性: 効率性ヒューリスティックは、報酬と計算量のフロント（境界）においてパレート優位性を確立しており、最小限の計算オーバーヘッドで準最適なパフォーマンスを提供している。

著者らは、リアルタイムの艦隊配車においては、目的関数の設計（具体的には報酬密度スコアリング）がアルゴリズムの複雑さよりも重要であり、効率性ヒューリスティックが、計画時間が制約条件となる運用システムにおいて堅牢な候補となることを結論づけている。研究では、実験がシミュレーションベースであることや、収益を単一の目的関数としている点に限界があることを認め、今後の研究では多目的制約や非定常な需要を探索すべきであるとしている。