A two-stage stochastic optimization model for synchronized two-echelon routing problems

技術要約：同期型2階層ルーティング問題のための2段階確率最適化モデル

問題定義
本研究は、都市物流における不確実性の複雑さ、特に統合型水陸両用輸送（IWLT）システムに焦点を当てて取り組んでいる。核心となる問題は、**衛星同期型2階層マルチトリップ車両ルーティング問題（2E-MVRP-SS）**である。このシステムでは、第1階層（道路）において、軽量電気貨物車両（LEFV）が顧客から物品を回収し、衛星ノードで船舶（第2階層）へと転送する。このシステムは衛星における保管オプションを持たないため、LEFVと船舶との間の厳格な時空間的同期を必要とする。

本研究が対処する主な課題は、衛星における転送リードタイムの不確実性によって引き起こされる遅延の伝播である。これらの不確実性は、交通渋滞や運用の変動といった地域的な要因に起因し、同期された運用を妨げ、顧客への遅延、運用コストの増加、および信頼性の低下を招く可能性がある。本研究は、タイミングの良いサービスが在庫コストや顧客の不便を最小限に抑えるために極めて重要となる、リバース・ロジスティクス（例：廃棄物回収、返品）のシナリオを具体的に対象としている。

手法
著者らは、これらの不確 अनcertainty（不確実性）を管理するために、混合整数リカバリー問題を用いた2段階確率最適化フレームワークを提案している。

1. 2段階定式化:

   • 第1段階（マスター問題）: 遅延が顕在化する前に、LEFVのルート決定および衛星への転送タスクの割り当てを行う。この段階では、ピックアップに関する信頼性の高いサービス時間を優先する。モデルは、初期近似としてLEFVが最も近い衛星を訪問することを仮定している。
   • 第2段階（リカバリー／サブ問題）: 特定の遅延シナリオが顕在化した後、是正措置が取られる。これには、遅延の影響を軽減するための、異なる衛星への転送作業の再割り当て、および船舶の再ルーティングが含まれる。LEFVの顧客サービススケジュールは、約束された時間を遵守するために固定されるが、水上物流は再最適化される。

2. アルゴリズム的アプローチ:

   • 第2段階のコスト関数の非凸性と混合整数の性質を扱うため、著者らは**組合せ的ベンダー・カット（combinatorial Benders cuts）を適用したL字法（L-shaped method）**を採用している。
   • アルゴリズムは、緩和されたマスター問題と各シナリオに対するサブ問題との間で反復を行う。
   • **実行可能カット（Feasibility cuts）**は、第1段階の決定が第2段階の実行可能な解を許容することを保証する。
   • **最適性カット（Optimality cuts）**は、期待される第2段階のコストを近似する。
   • 地域的な不確実性を表現するために、シナリオベースのサンプリング手法が使用されている。衛星での遅延は正規分布変数としてモデル化され、計算の実行可能性を維持しつつ安定性を確保するために、有限のシナリオ集合（$N$）に離散化されている。

3. 実験設定:

   • モデルは、修正されたSolomon VRPTWインスタンスから派生した小規模ネットワークインスタンス（ピックアップノード10、衛星4）でテストされた。
   • 2つのシステム設計が比較された：2E-Flexible（船舶が移動式デポとして機能し、LEFVと同期する）および2E-Stationary（固定された船舶位置）。
   • 性能は、決定論的（遅延なし）なベースラインおよび2段階確率的アプローチに対して評価された。

主な貢献

• 同期の新規モデリング: 本研究は、保管容量を持たない2階層システムにおいて、衛星の遅延が車両の同期に与える影響に対処した初めての研究であり、高度な時空間的調整を必要とするシナリオを扱っている。
• 確率的リカバリー・フレームワーク: 2E-MVRP-SSのために、混合整数リカバリーを用いた2段階確率計画モデルを提案している。第2段階の非凸性を処理するために、列挙法内で組合せ的ベンダー・カットを利用している。
• 柔軟性の比較分析: 柔軟な輸送システム（移動式船舶）と固定システム（固定式船舶）の間の定量的な比較を提供し、不確実性下における柔軟性の価値を実証している。

結果

• コスト削減: 提案された確率計画モデルは、遅延を想定しない決定論的アプローチと比較して、すべてのインスタンスにおいて期待総コストを37%削減した。
• シナリオの安定性: シナリオ生成手法は安定性を示した。サンプル内のシナリオの分散は、シナリオ数が増えるにつれて減少し、約30シナリオで安定した。
• ネットワーク・トポロジーの影響:
  • **クラスター型（C）**需要ネットワークでは、統合システムは不確実性下でも効率性を維持し、コスト増加は最小限（ほぼ0%）であった。
  • **ランダム型（R）**ネットワークでは、確率的アプローチは決定論的戦略と比較して最も大きな節減を実現し、遅延に敏感なピックアップ場所をより適切に配置することで、特定のインスタンスにおいて期待コストを最大43%削減した。
• システム性能（Flexible vs. Stationary）:
  • 2E-Flexibleシステムは、信頼性とモーダルシェアの両面で2E-Stationaryシステムを大幅に上回った。
  • 不確実性下において、固定式システムは道路走行時間の急増と遅延（例：RCインスタンスにおいて遅延が26時間単位に増加）を経験したが、柔軟なシステムは遅延を低く抑え（9時間単位）、道路と水上のモーダルシェアをよりバランスよく維持した。
  • 柔軟なシステムは、道路走行コストの増加リスクを効果的に軽減しており、保管ユニット（この場合は転送地点）の再配置では、混雑と信頼性の観点から柔軟な航行サービスによる性能には及ばないことを示している。

意義と主張
本論文は、都市空間の競争が保管オプションを制限する文脈において、オフライン計画に不確実性を組み込むことが、マルチモーダル都市物流の信頼性と費用対効果のために不可 Zeit（不可欠）であることを主張している。研究は、船舶がLEFVと同期する移動式デポとして機能する柔軟なシステムが、固定位置システムと比較して、転送遅延に対する優れたレジリエンス（回復力）を提供することを実証している。

著者らは、提案されたモデルは計算負荷が高いものの、小規模なインスタンスで見られた利点は、確率的最適化が都市物流におけるサービスの信頼性を大幅に向上させ、「グリーン」なモーダルシェア（道路利用）を減少させ得ることを示唆していると結論付けている。彼らは、今後の研究において、提案された列挙およびプライシングの枠組みを利用して大規模問題のためのヒューリスティックを開発できる可能性があると述べているが、現在の研究は理論的枠組みの検証と、小規模で解可能なネットワークにおける柔軟性の恩恵に焦点を当てている。