車両ルーティング問題のための新しいコンパクトフォーミュレーションクラス

この論文では、時間ウィンドウを伴う車両ルーティング問題（VRPTW）のための新しいコンパクト混合整数線形プログラミング（MILP）フォーミュレーションと、離散化発見に基づく解法アプローチを紹介します。私たちは、線形プログラミング（LP）ソリューションを、時間および容量に適したローカルな基本ルートに対応するフローのみを使用するように制約することで、最適化問題を効率的に解決することを目指しています（空間内に局所化された顧客のサイクルを禁止）。私たちは、LP緩和を反復的に洗練させるために、離散化発見アルゴリズムを使用します。この反復プロセスは、2つのステップ間を交互に繰り返します：（1）LP目的を増加させるために時間/容量/基本性の強制を増加させるが、複雑性が増す（変数や制約が増える）代償を伴います、（2）複雑性を減少させるためにLP目的を減少させずに強制を減少させます。この反復アプローチにより、最小限の複雑性で最適なMILP目的に密接に近似するLP緩和を生成できることが保証され、既製のMILPソルバーを介して効率的な解決が促進されます。私たちの方法の有効性は、古典的なVRPTWインスタンスに関する実証評価を通じて示されます。最終的なMILPの解決および複数のLP緩和のイテレーションの効率を示し、最終LP緩和の整数ギャップが減少したことを強調します。私たちは、このアプローチがVRPTWドメイン内外の幅広いルーティング問題に対処する可能性を秘めていると考えています。