技術要約：MODEMS – キャンパス内旅客モビリティ促進のためのカスタマイズされたソリューション

1. 問題の定義

本論文は、ミュンヘン連邦軍大学向けのライドプーリング・システムであるMODEMS（Munich On-Demand Electric Mobility Service）の運用上の課題を取り扱う。核心となる問題は、**電気式自律走行ダイアルアライド問題（e-ADARP）**の変種として定式化されている。本システムは、キャンパス内の固定された物理的サービスステーション間を輸送するために、小規模で異種混合な自律走行電気シャトル艦隊を管理する必要がある。

この問題の主な制約と特性は以下の通りである：

• 動的な環境： リクエストは動的に発生するか、事前に登録されるため、継続的な再最適化が必要となる。
• 異種混合艦隊： 車両は、乗客の容量、初期充電状態（SoC）、および最小運用SoC閾値において異なる。
• 負荷依存型のエネルギー消費： エネルギー使用量は、一定の割合ではなく、車両の総重量（無負荷質量 + 乗客数）の関数としてモデル化される。
• デカップルされた充電： 走行時間に対して充電時間が長いため、充電の決定はルーティングモデルの外側にある決定論的な運用ワークフローによって処理される。ルーティングモデルは、エージェントがトリップ完了後にデポに戻れることを保証するために、最小SoC制約のみを強制する。
• サービス制約： システムは、ハードまたはソフトの時間枠（TW）、最大乗車時間、ピックアップ／デリバリーの前後関係、および容量制限を扱う必要がある。
• 目的： ミッション期間、サービス開始時刻、TW違反、およびリクエスト拒否を最小化しつつ、エネルギーの実現可能性を確保することを目指す。

2. 手法

2.1 数理モデル (MILP)

著者らは、ルーティング問題の静的なスナップショットを解くために、3つの混合整数線形計画法（MILP）モデルを開発した：

• MILP1 (ソフトTW、初歩的なSoC): すべてのリクエストの受理を義務付ける非選択的モデル。TW違反を許容し（目的関数内でペナルティ化）、負荷依存のSoCではなく、保守的な走行時間の推定に基づく簡略化されたエネルギーモデルを使用する。
• MILP2 (ハードTW、拡張されたSoC): リクエストの拒否を許容する選択的モデル。ハードTWを強制し、負荷依存のSoC伝播をモデル化するために拡張されたエージェント・タプルを利用する。このモデルは、新しいリクエストが拒否された場合でも、スケジュールされたリクエストに対する実現可能性を保証する。
• MILP3 (ソフトTW、拡張されたSoC): リクエストの選択性、ソフトTW、および負荷依存のSoC伝播を組み合わせた包括的なモデル。これは、運用上の制約を最も現実的に表現している。

すべてのモデルは、クローズドVRP（エージェントはデポに戻らなければならない）とオープンVRP（エージェントは任意の停留所でルートを終了できる）の両方の目的をサポートしており、両方のケースにおいて帰路のエネルギー実現可能性を維持する。

2.2 解法戦略

問題のNP困難な性質と動的な運用における厳格な時間要件を考慮し、本論文ではローリングホライゾン・フレームワークを採用している。10分ごと、または新しいリクエストの到着時に、静的なスナップショットが作成され、解決される。

• 構成的ヒューリスティック： 厳密解法の加速およびウォームスタートの提供のために、著者らは貪欲な構成アルゴリズムを実装している。これらは、最も早い期限と需要に基づいて、リクエストをエージェントのルートに挿入することで、実行可能な初期解を生成する。
• 適応的大規模近傍探索 (ALNS): MILPを補完するためにALNSメタヒューリスティックが開発された。これは以下を利用する：
  • 実現可能性駆動型挿入： エージェントの状態をキャッシュし、単調な枝刈りと遅延サフィックス伝播を用いることで、実行可能な挿入を迅速に特定する特化した手順（アルゴリズム3）。これにより、修復フェーズの計算コストが大幅に削減される。
  • 破壊オペレータ： 現在の解からリクエストを削除するための6つの戦略（ランダム、ランダムゾーン、最低需要、最悪コスト、最悪待ち時間、最悪エネルギー）。
  • 修復オペレータ： リクエストを再挿入するための5つの戦略（ランダム、貪欲、Regret-2、最長トリップ、最も制約の強いもの）。
  • 適応的選択： オペレータは、その履歴パフォーマンスに基づいたルーレット選択メカニズムによって選択される。

2.3 システムアーキテクチャ

ルーティング層は、ROS 2を用いた通信による、より広範なサービスアーキテクチャ（概念実証）に統合されている。システムには以下が含まれる：

• フロントエンド／バックエンド： リクエスト管理およびデータオーケストレーション用。
• オプティマイザ： ルーティング戦略（MILPs または ALNS）を実行する。
• エージェントインターフェース： ルーティングの解を物理的なシャトルへのコマンドに変換する。
• 動的状態管理： エージェントの状態（利用可能、充電中、走行中、待機中）を処理し、次の計画エポックに向けた艦隊の可用性を更新する。

3. 主な貢献

本論文は、主に2つの貢献を行っている：

1. アプリケーション指向のサービスアーキテクチャ： 固定サービスステーション、小規模な異種混合艦隊、動的または拒否可能なリクエスト、負荷依存の放電、およびユーザー満足度指標を統合した概念的フレームワーク。充電ロジスティクスをルーティング最適化から明示的に切り離すことで、長い充電時間を処理している。
2. 比較アルゴリズム研究： 同一の目的関数と運用モードの下で、3つの異なるMILP定式化とALNSアプローチを厳密に評価した。
   • 本研究は、標準的な列挙と比較して探索プロセスを数桁加速させる、ALNSのための実現可能性駆動型挿入手順を導入している。
   • 厳密解法（MILP）は小規模なインスタンスに対して最適性の保証を提供する一方で、問題の規模とともに性能が急速に低下することを実証した。対照的に、ALNSはテストされたすべてのスケールにおいて、一貫した解の質と実現可能性を維持した。

4. 実験結果

デジタル化されたキャンパスネットワーク上の54の静的インスタンスと12の動的なワークデー・シミュレーションを用いて、数値実験が行われた。

• アブレーションスタディ： 提案された実現可能性駆動型挿入手順（V3）は、ルートの長さや制約の厳格性が増すにつれて、標準的な列挙（V0）と比較して最大898倍の高速化を達成した。
• 静的ソルバー比較：
  • MILP1およびMILP3は、概して最良の目的関数に近い解を生成した。
  • MILP2は、弱い構成的ベースラインを用いてハードTWを満たすことが困難であったため、高い変動性を示した。
  • ALNSは、より狭く予測可能な実行時間分布を提供し、MILPが制限時間内に最適解を見つけられなかった大規模なインスタンスにおいても、最良の解との競争力のある差を維持した。
• 動的ワークデー評価：
  • ソルバーの性能： 動的な設定において、ALNSはMILP3を一貫して上回り、提供されたリクエストに対する移動時間およびエネルギー消費量を大幅に抑えつつ、ほぼ完全なリクエスト受理を実現した。MILP3は、累積的なスケジューリングの非効率性とエージェントの同時充電により、需要が高い期間中にサービス停止（受理ゼロ）に頻繁に遭遇した。
  • 展開戦略： 段階的な艦隊展開（エージェントを間隔を空けて放出する）は、同時的なバッテリー枯渇を防ぐことでMILP3の堅牢性を大幅に向上させたが、ALNSはこの展開戦略に対する感度が低かった。
  • ルーティング目的： オープンVRPの目的（エージェントがどこでもルートを終了できることを許可する）は、リクエストあたりのリソース消費を減少させたが、遅延および乗車時間への影響については決定的な結論には至らなかった。

5. 重要性と主張

本論文の主な重要性は、実用的かつアプリケーション駆動型のモビリティサービスに特化して設計された、補完的な手法（厳密なMILPとメタヒューリスティックALNS）の統合と評価にあると主張している。

• ギャップの解消： 著者らは、既存の文献では、固定サービスステーション、小規模な異種混合艦隊、TWを伴う動的／拒否可能なリクエスト、限定的な充電能力、および短い応答時間という独自の組み合わせを共同で扱っていないと指摘している。
• 運用の堅牢性： 研究は、動的なリアルタイムサービスにおいては、ソルバーの選択と艦隊展開戦略が極めて重要であることを強調している。結果は、ALNSと段階的な艦隊展開の組み合わせが、サービス停止とリソースの浪費を最小限に抑える、最も堅牢な運用パフォーマンスを提供することを示唆している。
• スケーラビリティ： 実現可能性駆動型の挿入ヒューリスティックは、従来の挿入法が計算量的に不可能になる複雑な実世界のルーティング問題に対して、ALNSをスケールさせるための鍵となる要素として提示されている。

本研究は、完全なソフトウェアスタックの概念実証を提示して締めくくられており、今後の課題として、実際の大学キャンパスでの展開と実験を予定している。