A Metaheuristic Solution for the Capacitated Vehicle Routing Problem: Empirical Evaluation of Flexible Capacity Constraints via Ant Colony Optimisation

技術要約：容量制車両配送問題（CVRP）に対するメタヒューリスティック・ソリューション

1. 問題の定義と背景
本研究は、コロンビアにおける原材料の集荷オペレーションから生じる、現実世界の容量制車両配送問題（CVRP）を扱う。物流ネットワークは、グアダラ・デ・ブガ（バジェ・デル・カウカ）にある中央デポを拠点とし、コロンビアの多様な地域（海岸部、アンデス高地、工業地帯）に位置する30箇所の配送センターにサービスを提供する。このオペレーションは、変動する需要サイクル（1サイクルあたり643〜1,192個のパッケージ）に直面しており、10台のFoton FRR Cumminsトラックからなる同質的なフリートを利用している。

重要な運用上の制約は、柔軟な容量ポリシーである。車両の公称容量は $Q = 150$ 個であるが、企業ポリシーにより5%の過積載が管理下で許可されており、実効的な計画容量は $Q_{eff} = 157.5$ 個に設定されている。ルーティングは、OpenStreetMap（OSMnx経由）から派生した非ユークリッド的な道路ネットワーク上で実行されなければならない。地形的な複雑さ（山岳回廊、一方通行の街路）により、ユークリッド距離と実際の走行コストとの間には顕著な非対称性が存在する。

現行の計画システムである「Rout Now」は、「クラスタリング・ファースト、ルーティング・セカンド」型のアーキテクチャを採用している。これは、k-means法を用いてノードを10の地理的クラスターに分割し、その後、各クラスターを独立してSimulated Annealing（SA）を用いてシーケンス化するものである。この手法は、不均一なフリート利用率（35%〜90%）をもたらし、理論的な下限値が6〜8台で十分であることを示唆している場合でも、常に10台すべての車両を配備してしまうという課題がある。

2. 手法
本研究は、事前の地理的分割を行わずに、アクティブなノードの完全グラフ上で動作するように設計された**アントコロニー最適化（ACO）**メタヒューリスティックを提案し、評価する。

• 数学的定式化: 問題は、部分巡回除去のためのMiller–Tucker–Zemlin（MTZ）定式化を用いた混合整数線形計画法（MILP）としてモデル化される。容量制約は、過積載ポリシーを最適化ロジック内に組み込むため、$Q_{eff} = 157.5$ として明示的に緩和されている。
• ACOアーキテクチャ:
  • 構築: アントは、複数の車両によるルートを反復的に構築する。主要な差別化要因は、動的マスキングメカニズムである。累積負荷が $Q_{eff}$ を超えないように、実行可能な次ノードの集合（$F_k$）がリアルタイムでフィルタリングされる。これにより、アルゴリズムは新しいルートを開設することを避けるためにのみ5%の余剰を活用し、ノードを効率的に「パッキング」することが可能となる。
  • 遷移確率: ノードを選択する確率は、フェロモン・トレイル（$\tau$）とヒューリスティックな可視性（$\eta = 1/C_{ij}$）に依存する。コロンビアの道路コストの分散が高いため（平均に対して標準偏差47%）、ヒューリスティックの重み（$\beta = 2.0$）は、即時的なコスト効率を優先するためにフェロモン重量（$\alpha = 1.0$）を支配するように調整された。
  • 更新メカニズム: 標準的な蒸発および堆積ルールが適用され、低コストかつ高集約な解に寄与する弧（アーク）を強化する。
• 実験設計:
  • シナリオ: 実企業のデータから抽出された、1ヶ月間の計画サイクルを表す10の異なる運用シナリオ（S-1からS-10）を用いた。
  • 反復: 統計的な分散を分離するため、各シナリオは異なる乱数シードを用いて20回独立して実行された。
  • ベースライン比較: 内部妥当性を確保するため、同一のOSMnx距離行列を使用して、ACOの結果をベースライン（k-means + SA）と比較した。
  • 統計的検証: 20回の実行の平均総距離に対して、非パラメトリック検定であるウィルコクソンの符号付順位検定を適用し、統計的有意性を検証した。

3. 主な結果
ACOアプローチは、すべての10シナリオにおいて、ベースラインに対して系統的かつ統計的に有意な改善を示した。

• フリート削減: 最も需要の高いシナリオ（S-3; 1,192個のパッケージ）において、ACOはアクティブなフリートをベースラインの10台から、理論的な下限値（$\lceil 1192/157.5 \rceil = 8$）に一致する8台へと削減した。全シナリオを通じて、アクティブなフリートは約20%削減された。
• 距離とコスト:
  • 総距離: 平均で20.05%（19.97%〜20.25%の範囲）減少した。S-3では、距離が11,023 kmから8,790.5 kmへと減少した。
  • 燃料コスト: 重要なシナリオにおいて、推定**16.05%**の節減（1サイクルあたり約941,340 COP）を実現した。
  • 稼働時間: 20.02%短縮された。
• 容量利用率: ACOは優れた集約を実現し、S-3における平均容量利用率をベースラインの約79.47%から**99.50%**へと向上させた。ACOの解におけるルートは、公称容量の96%から101%の間で稼働しており、特定のルートは第9の車両を必要としないように、5%の過積ロード・マージンを戦略的に活用していた。
• 統計的有意性: ウィルコクソンの符号付順位検定の結果、$W=0$（すべての差がACOに有利）となり、p値は $< 0.01$ であった。これにより、中央値の等価性に関する帰無仮説は棄却され、改善の堅牢性が確認された。

4. 意義と貢献
本論文は、主に3つの科学的貢献を主張している。

1. 柔軟な制約の経験的評価: 構成的メタヒューリスティック内で柔軟な容量制約（$Q_{eff}$）を明示的にモデル化することで、事前の地理的分割アーキテクチャでは構造的に不可能な、協調的な負荷集約が可能になることを文書化している。本研究は、5%の許容範囲が単なる安全バッファではなく、動的に管理されることでフリート削減のための戦略的レバーとなることを示している。
2. 現実世界のトポロジーにおける堅牢性: バイオインスパイアード・メタヒューリスティック（特にACO）が、複雑で非ユークリッド的な道路ネットワークにおいて、古典的な「クラスタリング・ファースト、ルーティング・セカンド」型のヒューリスティックよりも優れているという証拠を提示している。本研究は、地理的な事前分割（k-means）が道路ネットワークの非対称性を考慮できない一方で、ACOが真のコスト空間上で動作することを強調している。
3. 因果メカニズムの特定: ルート構築時における実行不可能なノードの「動的マスキング」が、成功の因果メカニズムであることを特定した。これにより、アルゴリズムは需要の「効率的なパッキング」を実行し、ルート数を最小化するために過積ロード・マージンを自然に活用できる。これは、固定された地理的クラスターを持つベースラインには欠けている能力である。

5. 限界と今後の課題
著者らは、本研究が時間枠（VRPTW）やドライバーの労働時間制約を含まない特定の産業コンテキストに限定されていることを指摘している。提案されている今後の研究方向には以下が含まれる。

• 受理スケジュールを組み込むためのVRPTWへの拡張。
• 需要の不確実性に対処するための確率的VRP（SVRP）。
• 進化的アルゴリズムを用いた多目的定式化（例：CO₂排出量の最小化）の開発。
• 既存の物流システム内での制御されたA/Bテストのための、マイクロサービスとしてのACOコアの統合。