Overview
This research addresses the challenges of solving the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) using quantum annealing, specifically focusing on managing large Quadratic Unconstrained Binary Optimization (QUBO) formulations. The study investigates two primary strategies: adaptive penalty calibration for QUBO formulations and the application of a graph neural network (GNN) for guiding graph coarsening. These methods were evaluated using simulated annealing and a D-Wave Advantage2 processor, with the Solomon benchmark serving as the primary testbed.
Research Context
Solving vehicle-routing problems via quantum annealing typically generates large QUBO formulations. A common technique to manage this complexity is graph coarsening, which involves merging nearby customers with compatible time windows into 'super-nodes'. The reduced problem is then solved, and its solution subsequently expanded back to the original graph. For the CVRPTW, existing coarsening heuristics often necessitate family-specific tuning and have demonstrated unreliable performance on random instances.
Approach
The research pursued two distinct methodological improvements. First, an adaptive penalty calibration method was introduced. This approach moves beyond uniform penalty scaling, instead focusing on controlling the internal coefficient range within the QUBO formulation. The calibration process involved removing non-binding constraints, normalizing binding constraints, and then scaling the remaining penalties. A variable-count-preserving control was implemented to attribute observed gains specifically to the conditioning process rather than changes in problem size. Second, the study replaced hand-tuned merge scores, typically used in graph coarsening heuristics, with a graph neural network (GNN). This GNN was designed to operate with a single configuration across all problem families, aiming to overcome the family-specific tuning requirement of prior methods.
Findings
Adaptive Penalty Calibration
- Controlling the internal coefficient range of penalties substantially improved raw samples, contrasting with the limited effect of uniform penalty scaling.
- The combined steps of removing non-binding constraints, normalizing binding ones, and scaling penalties reduced the mean raw constraint violations from 33.0 to 0.06. This reduction was observed at the same solver budget ($p=3.7e-11$, $n=56$).
- A variable-count-preserving control indicated that this gain was attributable to the conditioning process itself rather than problem size reduction.
- Hardware experiments on a D-Wave Advantage2 processor reproduced the conditioning effect at a fixed logical variable count, showing an increase in feasible samples from 0.02% to 39% across 13 instances.
GNN-Guided Graph Coarsening
- The GNN, using one configuration across all families, achieved 100% feasibility across all Solomon families at N=10. This included R-type instances, where the GNN achieved 100% feasibility compared to 80% for the tuned heuristic.
- Across problem sizes N=10 to N=100, the GNN achieved 83% feasibility compared to 69% for the baseline. The GNN performed better or equivalently on 85 out of 90 instance-size pairs.
- For N=80 and N=100, the difference in feasibility was statistically significant ($p=0.002$), observed across 25 out of 25 pairs.
- Despite these improvements, the QUBO formulation remained approximately 5-6 times smaller with the GNN-guided coarsening.
Overall Solution Cost
- Classical repair methods, specifically those incorporating local search, remain a reference bound for the end-to-end solution cost.
Why This Matters
Existing coarsening heuristics for the CVRPTW often demand family-specific tuning and exhibit unreliability on random instances. The findings introduce approaches that mitigate these limitations: adaptive penalty calibration significantly reduces constraint violations, and a GNN-guided coarsening method improves solution feasibility across diverse problem instances without requiring manual tuning.