Life sciences · Preprint

GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer

arXiv · September 4, 2026

Preliminary Why this matters to you Expert discussion

Early or partial results. Treat as a signal, not a conclusion.

AI Summary

This preprint presents algorithmic advances for reducing QUBO formulations of the CVRPTW via adaptive penalty calibration and a GNN-based coarsening heuristic, tested on the Solomon benchmark using simulated annealing and D-Wave hardware. The work demonstrates improved feasibility rates and constraint satisfaction over hand-tuned baselines, but does not establish superiority in solution quality or provide evidence of practical advantage over classical methods.

What was studied

Uncontrolled comparative algorithm evaluation on fixed benchmark using simulated annealing and quantum hardware.. Solomon CVRPTW benchmark instances (R-type, C-type, RC-type families) with problem sizes ranging from N=10 to N=100 customers.. Intervention: Adaptive penalty calibration (removing non-binding constraints, normalizing binding constraints, scaling penalties) and GNN-guided graph coarsening heuristic.. Compared with: Hand-tuned merge-score coarsening heuristic; simulated annealing; classical repair with local search (mentioned but not quantified).. Not stated..

Key findings

Adaptive penalty calibration reduced mean raw constraint violations from 33.0 to 0.06 at fixed solver budget (p=3.7e-11, n=56). GNN-guided coarsening achieved 100% feasibility at N=10 across all Solomon families, compared to 80% for tuned heuristic. Across N=10 to 100, GNN feasibility was 83% vs. 69% for tuned heuristic, with GNN better or tied on 85/90 instance-size pairs.

Safety

Safety was not reported in the material analysed. Check the source before drawing any conclusion about harm.

Who this may help

The source did not state who this applies to in practice.

Plain-language summary

Early-stage algorithmic work combining GNN-guided heuristics with quantum annealing on a benchmark set; no peer review, no comparison to established classical baselines for solution quality, and limited to proof-of-concept feasibility metrics.

Study design

As stated by the source record.

MethodsPenalty calibration tested on Solomon benchmark instances (n=56) by varying constraint coefficient ranges and removal strategies, measured by constraint violation rate under fixed solver budget. GNN-guided coarsening heuristic trained and evaluated on Solomon families (N=10 to 100, total 90 instance-size pairs) by comparing feasibility and QUBO size against hand-tuned merge-score baseline. Hardware validation on D-Wave Advantage2 processor repeated on 13 instances with and without conditioning. No cross-validation or held-out test set described.

DesignUncontrolled comparative algorithm evaluation on fixed benchmark using simulated annealing and quantum hardware.

PopulationSolomon CVRPTW benchmark instances (R-type, C-type, RC-type families) with problem sizes ranging from N=10 to N=100 customers.

InterventionAdaptive penalty calibration (removing non-binding constraints, normalizing binding constraints, scaling penalties) and GNN-guided graph coarsening heuristic.

ComparatorHand-tuned merge-score coarsening heuristic; simulated annealing; classical repair with local search (mentioned but not quantified).

SettingNot stated.

Reported figures

Quoted from the source exactly as published.

Mean raw constraint violations (penalty calibration)33.0 to 0.06

p-value (penalty calibration improvement)3.7e-11

Sample size (penalty calibration)56

Feasibility at N=10, GNN vs. tuned heuristic100% vs. 80%

Feasibility across N=10–100, GNN vs. tuned heuristic83% vs. 69%

Instance-size pairs GNN better or tied (N=10–100)85/90

p-value (N=80,100 feasibility difference)0.002

Instance-size pairs significant at N=80,10025/25

Caveats

Not peer reviewed; preprint on arXiv.
No end-to-end solution cost reported; comparison to classical solvers (e.g., branch-and-bound, local search) absent.
GNN trained and evaluated on same benchmark family; generalization to unseen problem distributions not demonstrated.
Hardware results limited to 13 instances; statistical power and reproducibility not established.

Evidence assessment

Graded across the dimensions that decide whether you should act, each from what the source actually supports. There is no single score, and where a dimension was not assessed it says so.

Study design

limited

Uncontrolled comparative evaluation on fixed benchmark; no randomization or blinding.

Directness

moderate

Addresses CVRPTW directly but emphasizes feasibility and constraint satisfaction, not end-to-end solution cost.

Consistency

limited

GNN tested only on Solomon benchmark; generalization beyond this family not demonstrated.

Risk of bias

limited

GNN tuning on same benchmark family; no held-out test set or cross-validation strategy reported.

Sample adequacy

moderate

n=56 for penalty calibration; n=90 instance-size pairs for GNN comparison; hardware experiments on 13 instances.

Source abstract

Graph coarsening reduces the large Quadratic Unconstrained Binary Optimization (QUBO) formulations arising when vehicle-routing problems are solved by quantum annealing. Nearby customers with compatible time windows are merged into super-nodes, the reduced problem is solved, and the solution is expanded to the original graph. For the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), existing coarsening heuristics require family-specific tuning and remain unreliable on random instances. We address these limitations on the Solomon benchmark using simulated annealing and a D-Wave Advantage2 processor. We first introduce adaptive penalty calibration. Uniform penalty scaling has little effect, whereas controlling the internal coefficient range substantially improves raw samples. Removing non-binding constraints, normalising binding ones, and scaling the remaining penalties reduces mean raw constraint violations from 33.0 to 0.06 at the same solver budget (p=3.7e-11, n=56). A variable-count-preserving control attributes this gain to conditioning rather than problem size. Second, we replace the hand-tuned merge score with a graph neural network (GNN) using one configuration across all families. At N=10, it achieves 100% feasibility across all Solomon families, including R-type (100% vs. 80% for the tuned heuristic). Across N=10,...,100, feasibility is 83% vs. 69%, with the GNN better or tied on 85/90 instance-size pairs. At N=80,100, the difference is significant (p=0.002; 25/25 pairs), while the QUBO remains approximately 5-6 times smaller. Finally, hardware experiments reproduce the conditioning effect at fixed logical variable count: feasible samples increase from 0.02% to 39% across 13 instances. Classical repair with local search remains a reference bound for end-to-end solution cost.

Follow from this

Taken from the source record, never inferred. Follow any of these and new work involving them reaches your briefing.

Youssef Kamel RezkPaweł Gora