マルチデポ配送計画問題（MDVRP）は、物流やサプライチェーン管理における中心的な最適化問題であり、配送ネットワークの設計や貨物輸送計画などの実用的な場面で広く応用されている。複数のデポ（倉庫）から車両を同時に調整し、経路を決定する必要があるため、MDVRPの計算複雑性は極めて高く、NP困難問題に分類される。従来の解法では大規模なインスタンスに対して効率が悪く、妥当な時間内に高品質な解を得ることが困難であった。
この課題に対し、コンピュータ科学の研究者であるZhenyu Lei氏とJin-Kao Hao氏は、あるクラスのマルチデポ配送計画問題を効率的に解くための新しいハイブリッドアルゴリズムを提案した。このアルゴリズムは複数のインテリジェント最適化技術を融合している。まず、学習駆動型で多様性を制御する経路交換交叉を採用し、解空間を効果的に探索するとともに早期収束を防ぐ。次に、マルチペナルティ評価関数によって導かれる、デポ対応の実行可能・非実行可能探索フレームワークを構築する。これにより、探索中に一時的に実行不可能な解を受け入れ、局所最適から柔軟に脱出できる。さらに、マルチデポ設定に特化した2つのデポ関連局所探索演算子を組み込み、構造的な微調整を行う。
計算効率とスケーラビリティをさらに向上させるため、研究チームはアルゴリズムの拡張版を開発した。この拡張版では、テンソルベースのGPU加速と新しいマルチムーブ更新戦略を組み合わせることで、並列計算能力を最大限に活用する。GPU加速により求解時間が大幅に短縮され、より大規模な問題インスタンスを扱えるようになる。マルチムーブ更新戦略は、一度に複数の解の移動を更新することで反復オーバーヘッドを削減し、収束速度をさらに高める。
研究チームは、時間枠付きMDVRPや容量制約付きMDVRPを含む3つの標準的なMDVRP変種のベンチマークインスタンスに対して広範な計算実験を実施した。実験結果は、提案されたハイブリッドアルゴリズムがほとんどのインスタンスで最新の手法と同等以上の結果を達成し、特に大規模インスタンスにおいて顕著な競争優位性を示すことを明らかにした。この成果は、機械学習、数理計画法、並列計算を巧みに組み合わせることで、マルチデポ経路問題の求解可能性を大幅に拡張できることを示している。
本研究は2026年2月にarXivに提出され、ロボティクス、分散並列計算、最適化制御などの分野に分類される。将来的には、このアルゴリズムが実際の物流管理システムに統合され、輸送コストの削減や配送効率の向上に貢献し、自動運転車両の経路計画などの新興アプリケーションに理論的基盤を提供することが期待される。