# Graph-Coarsening Approach for the Capacitated Vehicle Routing Problem with Time Windows

arXiv: https://arxiv.org/abs/2510.22329 · HTML: https://mlsanity.com/paper/2510.22329/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 23 references that are in the map.
- First posted on arXiv 25 Oct 2025.

## Builds on (most cited first, 1 of 1)

- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)

## Built on by (most cited first, 1 of 1)

- [GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer](https://mlsanity.com/paper/2609.04593/) (2026)

## Abstract (arXiv)

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 paper introduces a multilevel graph coarsening and refinement strategy that aggregates customers into meta-nodes based on a spatio-temporal distance metric. The reduced problem is solved using both classical heuristics and quantum annealing hardware, then expanded back into the original space with arrival times recomputed and constraint violations recorded. Comprehensive experiments on Solomon benchmarks demonstrate that our method significantly reduces computation time while preserving solution quality for classical heuristics. For quantum solvers, experiments across all 56 Solomon instances at N=5 and N=10 customers show that coarsening consistently reduces computation time and, on clustered (C-type) instances, simultaneously reduces vehicle count and route duration with no feasibility loss. Coarsening effectiveness is strongly instance-structure dependent: C-type instances achieve %100 post-coarsening feasibility with measurable quality improvements, while narrow-window random (R-type) instances present structural constraints that limit achievable coarsening depth.