Scheduling and Routing with Degradation-Triggered Job Arrivals: An Application to Forest Firefighting with an Unmanned Aerial Vehicle Fleet

技術要約：劣化に起因するジョブ発生を伴うスケジューリングとルーティング

問題定義
本論文は、「劣化に起因するジョブ発生（Degradation-Triggered Job Arrivals）」と名付けられた、車両ルーティング問題（VRP）とジョブスケジューリング問題（JSP）を統合した新しい変種について扱っている。核心となる課題は、潜在的なジョブ発生場所のネットワークにおいて、新しいジョブがランダムに出現するのではなく、既存のジョブの劣化によって動的にトリガーされるという点にある。

無人航空機（UAV）を用いた空中森林火災消火という特定の文脈において、問題は以下のように定義される：

• ネットワーク構造： 火災が発生しやすいノード、防火ノード（障壁）、水源、およびUAV基地を含む森林地域を表す、グリッドベースのグラフ。
• ジョブのダイナミクス： 各発火エリア（ジョブ）には、指定されたタイムウィンドウがある。このウィンドウの間、火災は成長（規模が劣化）し、ノードの価値が減少（劣化）する。
• 劣化に起因する到着： もし火災が臨界サイズ閾値（$t_m$）に達する前に鎮火されない場合、火災は隣接するノードへと広がり、新たなジョブの到着をトリガーする。これにより、ルーティングとスケジューリングの決定が火災の拡大（およびそれに伴う新ジョブの到着）を決定し、一方で新ジョブの到着がその後のルーティング決定に影響を与えるという、双方向の相互作用が生じる。
• 目的： 地域全体の残存価値を最大化すること。これには、火災が完全な価値喪失を引き起こす前に火災を抑制すること、および高価値の隣接ノードへの火災の拡大を防ぐことが含まれる。モデルは、タスク間でタンクを満たすために水資源を訪れる必要性や、火災の規模に関わらず満水の水量を放出する必要性といった、UAVの制約を考慮している。

手法
著者らは、主に2つのモデルからなる数学的最適化フレームワークを開発した：

1. 厳密な混合整数計画法（MIP）モデル (EM):

   • EMは、車両ルーティング、ジョブ選択、および火災拡大ロジックのためのバイナリ変数、ならびに時間と価値のための連続変数を用いて問題を定式化している。
   • 現実性と計算の実行可能性のバランスを取るため、火災規模の成長と価値の劣化に対して線形近似を取り入れている。
   • モデルは、スケジューリングの決定（到着時刻）と火災進行ロジックを明示的に連結させている。火災の有無、車両の到着、および火災の臨界成長フェーズに対する当該到着のタイミングに基づいた、4つの異なる火災拡大ケースをモデリングするために「Big-M」制約を使用している。
   • 目的関数は、収集されたノード価値の合計を最大化し、基地への帰還に要した時間をペナルティとして課す。

2. ハイブリッドモデル：厳密モデル誘導型リフィル遅延モデル (E-RDM):

   • EMが、弱い線形計画（LP）緩和および水のリフィル制約の複雑さによってスケーラビリティに苦慮することを認識し、著者らはハイブリッドアプローチを提案している。
   • リフィル遅延EM (RDM): 連続するタスク間の水資源への訪問と、それに伴う時間結合制約を省略した、EMの緩和版である。
   • 分岐限定法（Branch-and-Cut）と遅延制約： E-RDMアルゴリズムは、まずRDMを解いて高品質な実行可能解を生成する。その後、遅延制約コールバックを備えた分岐限定フレームワークを採用する。もし解が省略された水のリフィルまたは時間結合制約に違反する場合、対応する制約がカットとして動的に追加される。
   • 二段階戦略： アルゴリズムは、全計算時間制限の一部を完全なEMの解決に（可能な限り迅速に最適解を見つけるため）、残りの時間を動的な制約生成を伴うRDMに（境界を改善し、より大きなインスタンスを扱うため）割り当てる。

主な貢献
本論文は、主に以下の3つの貢献を特定している：

1. 理論的進展： スケジューリングとルーティングの文献に、劣化に起因するジョブ到着の概念を導入した。決定とは独立しているか確率的な標準的な動的VRPとは異なり、本モデルは決定が直接的に新しいジョブの到着に影響を与えるという双方向の相互作用を特徴としている。
2. 災害管理への応用： 空中森林火災消火のための処方的意思決定モデルを提供している。このモデルは、物流（ルーティング、リフィル）と運用計画（火災抑制のタイミング）を統合し、野火シナリオにおける「資産保護問題（APP）」に対処する。
3. 再現性とツール化： 著者らは、Python/Gurobiコードベースと連携したソフトウェアインターフェース（スプレッドシートベース）を開発しており、実務者が生のコードを操作することなく、問題インスタンスを生成し最適解を見つけることを可能にしている。再現性を促進するため、コードベースはGitHubを通じて共有されている。

結果
計算実験は、Gurobi Optimizer 10.0.1を使用し、2コア、28スレッドのワークステーションで実施された。

• 性能比較： ハイブリッドE-RDMモデルは、厳密なEMを大幅に上回った。EMは、ジョブの到着数が多い場合やフリート容量が限られている場合に、制限時間（3,600秒）内に最適性を証明できないことが多かったが、E-RDMは1,260回の実行にわたって一貫して3%未満の最適性ギャップを達成した。
• スケーラビリティ： E-RDMは、変動するフリートサイズ（2対4のUAV）および速度（60対120 km/h）に対して堅牢性を示した。平均実行時間47秒でインスタンスを解決した。
• ジョブ到着の影響： 研究により、ジョブの到着数が増加するにつれて（初期火災と拡大率によって駆動される）、EMの計算難易度が急激に上昇することが確認された。E-RDMは、緩和された定式化を活用して探索を導くことで、この問題を効果的に軽減した。
• ケーススタディ： カリフォルニアの野火特性（SILVIS土地分類データを使用）に基づいたケーススタディは、高密度な都市境界部から無人の植生エリアまで、多様な景観を扱うモデルの能力を実証した。モデルは、7つの異なるシナリオタイプ全体で、価値の保持を最大化する抑制計画を正常に生成した。

意義と主張
本論文は、「急がば回れ（a stitch in time saves nine）」という格言の実践的な適用として位置づけられており、早期かつ協調のとれた介入が不釣り合いな被害を防ぐことを強調している。著者らは、抑制の遅れと新しい火災タスク（スポットファイア）の発生との間の因果関係を明示的にモデル化することで、既存のアプローチよりも大幅な改善を提供できると主張している。

本研究は、火災挙動の連続的な物理現象を解明することを目的としているのではなく、火災の拡大と価値の減少に対して線形近似を用いることで、現実性と計算の実行可能性のバランスを取っている。その意義は、単一のタスクの遅延が作業量を指数関数的に増加させ、保護領域の総価値を減少させるという、動的で相互依存的な性質を持つ野火抑制を扱える意思決定支援システムを提供することにある。著者らは、ハイブリッドアプローチが、これまで計算的に困難であった複雑な現実世界の災害対応ロジスティクス問題に対して、実行可能な道筋を提供すると結論付けている。