FiLMMeD: Feature-wise Linear Modulation for Cross-Problem Multi-Depot Vehicle Routing

以下は、論文「FiLMMeD: Feature-wise Linear Modulation for Cross-Problem Multi-Depot Vehicle Routing」の詳細な技術的サマリーです。

1. 問題定義

本論文は、現代の物流、特に電子商取引において中核をなす複雑な組み合わせ最適化（CO）問題である**多配送拠点車両経路問題（MDVRP）**を取り扱っています。従来の単一拠点 VRP と異なり、MDVRP は複数の拠点から車両を派遣して顧客にサービスを提供する問題です。

本論文が取り組む具体的な課題は問題横断的な汎化です。現実世界の物流には、時間制約、バックホール、経路長制限、オープンルート、拠点間転送など、動的に変化する多様な制約が含まれています。従来のニューラルベースのソルバーは通常、特定の問題バリエーションで訓練されるため、新しい制約の組み合わせに直面すると脆弱になります。マルチタスク学習（MTL）は単一拠点 VRP に適用されてきましたが、MDVRP バリエーションの複雑さに対処するには至らず、以下のような問題にしばしば陥っています：

• 勾配の競合： 多様な制約セットを同時に訓練する際、更新が競合すること。
• 低い汎化性能： 再訓練なしには、制約間の複雑な相互作用（例：バックホール＋時間制約）を処理できないこと。
• 静的な条件付け： 既存のモデルは制約を高レベルの文脈として扱うだけであり、内部表現を動的に変調させていないこと。

2. 手法：FiLMMeD

著者らは、24 種類の MDVRP バリエーション（拠点間経路を含む 8 つの新しい定式化を含む）と16 種類の単一拠点 VRP バリエーションを解決するために設計された、統合されたニューラルベースのモデルFiLMMeDを提案します。このアーキテクチャは、Transformer ベースのエンコーダ - デコーダフレームワーク（具体的には MTPOMO、MVMoE、CaDA を拡張したもの）に基づいています。

コアコンポーネント：

1. 特徴量ごとの線形変調（FiLM）：

   • メカニズム： 制約特徴量の単純な連結の代わりに、FiLMMeD はアクティブな制約を示すブーリアンベクトルである条件付けベクトル $z$ を導入し、ノード埋め込みを動的に変調します。
   • 実装： モデルは、学習可能な線形投影を通じて $z$ に基づいてスケーリング（$\gamma$）とシフト（$\beta$）のパラメータを計算します。これらのパラメータは、アフィン変換として顧客埋め込みに適用されます：$FiLM(h|\gamma, \beta) = \gamma \cdot h + \beta$。
   • 効果： これにより、モデルはインスタンスのアクティブな制約に特化して内部表現を適応させることができ、潜在的空間を効果的に分離し、タスク間の勾配競合を軽減します。

2. カリキュラム学習（CL）戦略：

   • 動機： 単一拠点 MTL で一般的であるすべてのバリエーションの均一サンプリングは、制約間の複雑な相互作用により MDVRP では収束が不良になります。
   • 戦略： 訓練カリキュラムは、複雑さを段階的に増加させるように構成されています：
     • フェーズ 1（0-30%）： 単一制約バリエーション＋困難であることが知られている特定の 2 制約バリエーション（例：バックホール＋時間制約）。
     • フェーズ 2（30-60%）： すべての 2 制約バリエーションの導入。
     • フェーズ 3（60-90%）： 3 制約バリエーションの導入。
     • フェーズ 4（90-100%）： 4 制約バリエーションを含む完全なセット。
   • 目的： 孤立した制約効果の学習から、それらの複雑な相互作用の習得へとモデルを導くこと。

3. 選好最適化（PO）：

   • 革新： 本論文は、標準的な強化学習（RL）損失（REINFORCE）に代わる MTL 用の訓練パラダイムとして PO を導入します。
   • メカニズム： スカラー報酬を最適化する代わりに、モデルは同じインスタンスに対して生成された軌跡間のペアごとの選好から学習します。軌跡 $A$ のコストが $B$ よりも良好である場合、モデルは $B$ に対して $A$ の確率を高めるように最適化されます。
   • 利点： PO は勾配分散を低減し、スケール不変（コストの絶対値の影響を受けない）であるため、MTL 設定で一般的に見られる不安定性と勾配干渉に対処します。

3. 主な貢献

1. MDVRP 向けの最初の統合 MTL モデル： FiLMMeD は、新しい拠点間経路定式化を含む広範な MDVRP バリエーション（合計 24 種類）を明示的に処理するように設計された最初のモデルです。
2. 制約条件付けのための FiLM メカニズム： 制約属性に基づいて埋め込みを動的に変調することが、静的な特徴量連結と比較して汎化を大幅に改善し、潜在的空間を分離することを示しました。
3. MTL における選好最適化： MTL 設定における PO の最初の実証を提供し、収束の安定性と解の品質の面で従来の RL よりも優れていることを示しました。
4. ターゲット型カリキュラム学習： 単一拠点問題には均一サンプリングで十分であるのに対し、MDVRP には制約複雑性への段階的な曝露を伴うガイド付きカリキュラムが必要であることを確立しました。

4. 実験結果

著者らは、24 種類の MDVRP バリエーションと 16 種類の単一拠点 VRP において広範な実験を行いました。

• MDVRP での性能：

  • FiLMMeD は、解の品質（ギャップ）の面で、最先端のベースライン（MTPOMO、MVMoE）および従来のヒューリスティック（PyVRP）を一貫して上回りました。
  • 50 ノードのインスタンスにおいて、FiLMMeD-MTPOMO はベースラインと比較して平均ギャップを**2.888%**削減しました。
  • 100 ノードのインスタンスでは改善がさらに顕著で、FiLMMeD-MVMoE はベースラインを**5.288%**上回りました。
  • このモデルは、未見の制約組み合わせに対して優れたゼロショット汎化を達成しました。

• 単一拠点 VRP での性能：

  • 単一拠点バリエーションで微調整した場合、FiLMMeD（PO を使用）は、大規模なデータセット（例：1 億インスタンス）で訓練されたベースラインと比較して、競合する、あるいは優れた結果を達成しました（3000 万インスタンスで訓練されたにもかかわらず）。
  • FiLMMeD-CaDA†（FiLM、PO、ReLD を組み合わせる）は、50 ノードのインスタンスで平均ギャップ**1.46%**という、全体的に最高の性能を達成しました。

• アブレーション研究：

  • FiLM： FiLM を除去すると、未見バリエーションでの性能が著しく低下しました（例：MVMoE の場合、ギャップが 5.297% から 5.716% に増加）。
  • カリキュラム： 均一サンプリングまたは「統合」訓練戦略は、MDVRP において収束不良を招き、提案された CL 戦略の必要性を裏付けました。
  • PO vs RL： 全アーキテクチャにおいて、REINFORCE で訓練されたモデルと比較して、PO で訓練されたモデルはより速い収束と低い平均ギャップを示しました。

• 複雑性： FiLM メカニズムは、パラメータ数を無視できるほど少量に増加させます（<0.01M、<1% の増加）が、GPU メモリオーバーヘッドは最小限です。エポックあたりの訓練時間はベースラインとほぼ同一のままです。

5. 意義

本論文は、物流におけるニューラル組み合わせ最適化において重要な前進を表しています：

• 実用性： 単一の統合モデルで 24 種類のバリエーションを解決することで、FiLMMeD は、企業が異なる制約セットに対して個別のソルバーを必要とする物流における「分断」問題に対処します。
• 理論的進展： 選好最適化がマルチタスク学習にとってより安定した効果的な訓練パラダイムであることを実証することで、CO における強化学習の支配的な地位に挑戦します。
• アーキテクチャ的洞察： 多様な制約を処理するには、静的な文脈埋め込みよりも動的な条件付け（FiLM）が優れていることを証明し、将来の問題横断学習モデルのための青写真を提供します。
• 汎化： カリキュラム学習戦略の成功は、多拠点設定における制約相互作用の複雑さが構造化された学習パスを必要とすることを浮き彫りにしており、この知見は他の複雑な CO 問題にも適用される可能性があります。

要約すると、FiLMMeD は車両経路問題における統合ニューラルソルバーの新しい最先端を確立し、現代的で動的な物流課題に対するスケーラブルで柔軟かつ非常に汎用性の高いソリューションを提供します。