Graph-Coarsening Approach for the Capacitated Vehicle Routing Problem with Time Windows
This work addresses a fundamental NP-hard optimization problem in logistics, offering a method to handle large-scale instances more efficiently.
The paper tackles the computationally challenging Capacitated Vehicle Routing Problem with Time Windows by introducing a multilevel graph coarsening and refinement framework, which reduces computation time while preserving or improving solution quality on Solomon benchmark instances.
The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) is a fundamental NP-hard optimization problem in logistics. Solving large-scale instances remains computationally challenging for exact solvers. This work introduces a multilevel graph coarsening and refinement framework that aggregates customers into meta-nodes using a spatio-temporal distance metric. The reduced problem is solved with classical heuristics and subsequently expanded back into the original space with feasibility corrections. Preliminary experiments on Solomon benchmark instances show that the proposed method reduces computation time while preserving or improving solution quality, particularly with respect to capacity and time window constraints. The paper also explores the integration of quantum-inspired optimization techniques, highlighting their potential to further accelerate large-scale vehicle routing tasks.