Assigning and optimising airport ground-handling operations: an rVNS metaheuristic

技術要約：rVNSによる空港地上ハンドリング業務の割り当てと最適化

問題定義
本研究は、空港の地上ハンドリング業務、特にケータリングサービスにおける複雑な組合せ最適化に対処するものである。核心となる問題は、多様な資格や積載パターンを持つ異種混合のトラック車両およびドライバーに対応するために拡張された、**マルチトリップ容量制車両経路およびスケジューリング問題（MTCVRSPTW-MB）**としてモデル化されている。

目的は二重である：

1. 主目的： 利用可能なドライバーおよびトラックに割り当てられるケータリング・タスク（航空機の積み込み／荷降ろし）の数を最大化すること。
2. 副次的目的： これらのタスクを実行するために必要な総走行距離を最小化すること。

この問題は、以下の厳格な運用ルールによって制約されている：

• ドライバーの制約： シフトスケジュール、義務付けられた30分間の食事休憩（シフト開始から4〜5時間後）、および特定の航空機タイプや航空会社に対する資格要件。
• トラックの制約： 容量制限、特定のトラックタイプ（14FT、16FT、22FT）、および限られた一日の利用可能性。
• タスクの制約： 実行のためのタイムウィンドウ、トラック／ドライバーと特定のフライト／航空会社との互換性、および容量要件。
• ミッションの制約： 同一ミッション内での国内線荷降ろし後の国際線積み込みの禁止、タスク間の十分な移動時間の確保、およびすべてのミッションがメイン・ケータリング・ユニットで開始および終了する必要があるというルールなどの、マルチタスク・ミッションを管理する規則。

本研究では、2023年3月のサンフランシスコ国際空港（SFO）の実データを使用しており、これには約350件の日常タスク、80名のドライバー、および40台のトラックが含まれる。重要な要件として、運用上有効であるためには、解を1分以内に生成しなければならない。

手法
著者らは、**協調型縮小変数近傍探索（cooperative reduced Variable Neighborhood Search: rVNS）**メタヒューリスティックを提案している。このアプローチは、計算効率と解の品質のバランスを取るために、従来の変数近傍探索（VNS）および適応的大近傍探索（ALNS）と比較して選択された。

手法の主要な構成要素は以下の通りである：

1. 縮小VNS（rVNS）フレームワーク：

   • 古典的なVNSがステップサイズを変化させるのに対し、rVNSは固定された小さなステップサイズを採用する。
   • アルゴリズムは、現在の解から固定数（$n$）のタスクを解除し、それらをランダムに再割り当てを試みる**「解体と再構築」**のサイクルを通じて動作する。
   • 固定ステップサイズを補うため、アルゴリズムはスケジューリング問題の高い対称性を活用する。ランダムなスワップを通じて「等価な」解（同一のスコアを持つ異なるスケジュール）を探索することで、大規模で計算コストの高いステップを必要とせずに探索を多様化させる。

2. アルゴリズム構造：

   • 分解（問題の二分法）： 日次のスケジュールを、ドライバーのシフト重複に基づいた2つのサブ問題（午前と午後）に分割し、並列処理を可能にする。
   • ウォームスタート・ヒューリスティック： rVNSは、資格を持つドライバーが少なく、かつ義務的な食事休憩を伴うタスクを優先する貪欲法ヒューリスティックによって生成された解で初期化される。これにより、探索が質の低い局所最適解から始まるのを防ぐ。
   • 二重目的のランダム化： アルゴリズムは、目的関数の収束に基づいて2つのランダム化戦略を交互に切り替える：
     • 主焦点： 未割り当てのタスクのためのスペースを作るために、類似の時系列位置を持つタスクを解除する。
     • 副次的焦点： 総走行距離に最も大きく寄与するタスクを解除する。
   • シーケンシング・ヒューリスティック： 高速なヒューリスティック（アルゴリズム3）は、制約に違反することなくタスクをドライバーのシーケンスに挿入できるかどうかをチェックし、再構築フェーズ中の速度維持に不可欠な役割を果たす。
   • 協調的並列化： マルチスタート戦略は、8個のコア（各サブ問題につき4個）で実行される。10秒ごとに、並列ユニットは結果を共有し、現在の最良の解から再スタートして、分散を抑え局所最適解を回避する。

3. 目的関数：
   総目的関数 $F$ は、タスク割り当てを優先し、次いで走行距離の削減、最後にミッション効率を優先する、加重和である：
   $$F = 10^6 \sum a_i + 10^3 \sum (x_i + y_i) + \sum e_i$$
   ここで、$a_i$ は未割り当てのタスク、$x_i$ と $y_i$ は移動距離、$e_i$ はミッションの開始回数を表す。

主な結果
本研究では、提案されたrVNSを、2つのデータセット（S1：タスクが少なく制約が多い、S2：タスクが多く制約が少ない）を用いて、貪欲法ヒューリスティックおよびメタヒューリスティック（[1]で開発されたもの）と比較している。

• タスク割り当て： rVNSは、以前の手法を大幅に上回る成果を上げた。貪欲法およびメタヒューリスティックによる割り当て率が約80〜89%であったのに対し、rVNSは両方のデータセットにおいて**99.0%から99.8%**の割り当て率を達成した。
• 走行距離の削減： rVNSは、メタヒューリスティックと比較して、S1データセットでは総車両走行距離を約30%、S2データセットでは約**20%**削減した。
• 安定性と収束性：
  • 並列化されたrVNSは、逐次型バージョンよりも高い一貫性を示し、走行距離の標準偏差は、逐次型が4〜6%であったのに対し、並列型では2〜3%であった。
  • 収束速度： 小規模なデータセット（S1）では、主要な目的（タスク数）は急速に（約1秒以内に）収束したが、走行距離の最適化は1分間まで改善し続けた。大規模なデータセット（S2）では、主要な目的は収束に約10秒を要し、1分以降は収穫逓減が見られた。
• 実行時間： すべての解は、要求された1分間のウィンドウ内に生成された（オーバーヘッドを含めて具体的には約55〜60秒）。

意義と主張
本論文は、rVNSメタヒューリスティックが、既存の厳密解法およびヒューリスティックのベースラインを凌駕する、空港の地上ハンドリングに対する堅牢で柔軟なソリューションを提供すると主張している。その主な意義は以下の通りである：

1. 運用の実現可能性： リアルタイムの配車に必要な厳格な1分間の時間枠内で、高度に制約された多目的問題を解決する。
2. 二重の最適化： タスク完了の最大化と運用コスト（走行距離）の最小化をうまくバランスさせており、これは従来の研究では十分に最適化されていなかった機能である。
3. 柔軟性： 電気自動車の充電管理やマルチデポ運用など、新しい制約や目的を統合できるアルゴリズム構造を持っている。
4. 実世界への適用： 本研究は、アルゴリズムが（スライディング・タイムウィンドウや異種混合フリートを含む）実世界のデータの複雑さを、従来のモデルよりも適切に扱えることを示しており、数百の日常タスクを自動的に割り当てるためのツールを地上ハンドラーに提供する。

著者らは、アルゴリズムがグローバルな最適解を保証するものではないことを認めつつも、一貫して既存の手法よりも優れた品質と速度で収束することを示しており、絶対的な最適性については控えめな姿勢をとっている。また、遅延したタスクを動的に再スケジューリングする必要があるリアルタイムの再割り当てシナリオへの将来的な応用の可能性についても強調している。