A Joint Learning and Optimization Approach for the Two-Stage Stochastic Service Network Design Problem

技術要約：2段階確率的サービスネットワーク設計問題に対する学習と最適化の統合アプローチ

問題の定義
本論文は、貨物集約キャリア（LTL、小口配送、インターモーダルキャリアなど）にとって極めて重要な戦術的計画課題である「2段階確率的サービスネットワーク設計（SSND）」問題を取り扱う。この文脈において、キャリアは不確実な需要の下で、来るべきシーズンに向けてターミナル間で運用するサービスの容量（車両数）を決定する必要がある。問題は以下の通り2段階の確率計画法として定式化される：

• 第1段階： 需要が判明する前に、ネットワークの弧（アーク）上で運用する車両数を選択する決定（設計変数）。これらは一般整数変数である。
• 第2段階： 需要が明らかになった後、キャリアは選択されたネットワークを通じて貨物をルーティングする。計画された容量が不足している場合、追加の「スポット市場」車両をより高いコストで購入する（リカースト決定）。
  目的は、第1段階の設計コストと期待される第2段階のリカストコストの合計を最小化することである。この問題は、大規模な混合整数性質を持つモデルと、不確実性を表現するために必要なシナリオの指数関数的な増加により、現実的なネットワーク規模では計算量的に手に負えない（intractable）ものである。

手法
著者は、計算負荷の高い第2段階のリカストコスト部分問題を学習されたサロゲートモデルに置き換える、ニューラルネットワーク拡張型最適化フレームワークを提案している。コアとなる手法は以下の通りである：

1. サロゲートモデリング： 第1段階の設計ベクトル $r$ が与えられたときの期待リカストコスト $E_\omega[Q(r, \omega)]$ を近似するように、ReLU活性化関数を持つフィードフォワードニューラルネットワーク（NN）を訓練する。
2. MIPへの埋め込み： ReLU関数は混合整数線形制約を用いて正確に表現できるため、訓練されたNNを混合整数計画法（MIP）の定式化に直接埋め込む。これにより、「サロゲートMIP」が作成される。このサロゲートMIPでは、第2段階の部分問題の制約と目的関数がNNの数学的表現に置き換えられ、問題全体を単一の決定論的MIPとして解くことが可能になる。
3. データ生成戦略： 本手法の重要な部分は、ラベル付き訓練データ（設計ベクトル $r$ とその真の期待リカストコストのペア）を生成することに焦点を当てている。第1段階の変数は一般整数（非限定的）であるため、ランダムサンプリングでは不十分である。著者は以下の3つの戦略を導入し、比較している：
   • ランダム（Random）： 全体の容量制限を満たすようにスケール調整された上で、アークに対して一様に車両数を生成する。
     easily
   • 摂動（Perturbation）： 単一シナリオの決定論的部分問題の厳密解から訓練サンプルをシード（種）とする。その後、これらのベースとなる解に対して小さな整数摂動を加えることで、高品質な設計の局所的な近傍を探索し、追加のサンプルを生成する。
   • ハイブリッド（Hybrid）： 摂動アプローチとランダムアプローチを組み合わせたもので、パラメータ $\alpha$（摂動によって生成されるサンプルの割合）によって制御される。
4. ベンチマーク： 提案手法は、有限のシナリオセットを用いて期待コストを近似する標準的な手法であるサンプル平均近似法（SAA）と比較検証される。

主な貢献
本論文は、文献に対して主に4つの貢献を行っている：

1. 一般整数に対する新しいフレームワーク： 第1段階の変数がバイナリ変数に限定されていた従来の研究を拡張し、一般整数変数を扱うSSND問題に対する初の学習ベースのアプローチを提示している。
2. 高度なデータ生成： ランダムサンプリングよりも効果的に、整数設計変数の非限定的な実行可能解空間をカバーするために設計された、新しいデータ生成技術（摂幅およびハイブリッド）を提案し、検証している。
3. 実証的検証： 18の異なるネットワークインスタンスを用いた実験を通じて、データ生成手法の選択が解の質に大きく影響することを実証している。摂動およびハイブリッドのアプローチは、予測精度（MAE、MSE）および結果として得られるネットワーク設計の実現コストの両方において、ランダムアプローチを一貫して上回っている。
4. SAAとの比較分析： 学習ベースのアプローチをSAAと比較した。結果は、摂動およびハイブリッド法が、SAAと同等の解の質（最良解への平均ギャップはそれぞれ0.94%および1.02%）を実現しつつ、計算量やスケーラビリティに関して異なるトレードオフを提供することを示している。

結果

• 予測精度： 摂動ベースのアプローチは、テストセットにおいて最も低い平均絶対誤差（MAE = 9.11）および平均二乗誤差（MSE = 161.95）を達成し、ランダムおよびハイブリッド法を上回った。
• 解の質： 摂幅およびハイブリッドのデータ戦略を用いて生成された設計は、ランダム戦略を用いて生成されたものよりも実際の総コストが低かった。摂動アプローチは、推定コストと実際のコストの間で最も高い一致（平均偏差1.33%）を示したが、ランダムアプローチは大幅に高い偏差（10.81%）を示した。
• データセットサイズへの感度： 訓練データセットのサイズを大きくすると、一般にエラー指標は減少し、約4,000サンプルで性能が安定した。
• ハイブリッド・パラメータ（$\alpha$）： ハイブリッド・パラメータ（摂動とランダムのサンプルの比率）を変化させると、$\alpha = 0.75$ が最良のバランスを提供し、特に大規模なネットワーク構成において、最も低い実際のコストをもたらすことが示された。
• SAAとの比較： SAAは大規模なインスタンスにおいて時としてわずかに優れた解を見つけることもあるが、学習ベースのアプローチは、単一のサロゲートモデルを解くことで、複数のシナリオベースのMIPを解く必要があるSAAとは対照的に、競争力のある結果を達成した。

意義と主張
本論文は、提案されたフレームワークが、SSND問題に直面している貨物集約キャリアにとって、実行可能なヘリスティックな代替案を提供すると主張している。計算困難な第2段階の部分問題をニューラルネットワークのサロゲートに置き換えることで、最適化プロセスを簡素化できる。著者は、一般整数変数を取り扱う際に、提案された特定のデータ生成戦略（摂動およびハイブリッド）が、訓練データが関連する解空間の領域を適切にカバーすることを保証するため、極めて重要であることを強調している。本研究は、訓練フェーズにおいてラベル生成のための計算コストが必要となる一方で、その後の最適化は効率的であり、伝統的な手法であるSAAに対する補完的なトレードオフを提供するものであることを示唆している。著者は、これを既存の学習支援型最適化の拡張として控えめに位置づけており、将来的には、異なるネットワークインスタンス間で単一の汎用モデルを訓練したり、ネットワーク構造をより良く活用するためにグラフニューラルネットワークを利用したりする可能性についても言及している。