Metraipolis › archive › dc_2d57fc692040

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.04593
License (as archived)
CC0-1.0
Archived
2026-10-16T22:57:57.287Z
SHA-256 of the archived text
9b292edbfa4f603c37e2bb42c0ac74b080d48314c30074f6235010f41cebe7c4
Stable URL of this page
https://metraipolis.com/documento/dc_2d57fc692040

How to cite

GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer — arXiv:2609.04593 — arXiv (en), https://arxiv.org/abs/2609.04593 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2d57fc692040 (Metraipolis archive dc_2d57fc692040, sha256 9b292edbfa4f603c37e2bb42c0ac74b080d48314c30074f6235010f41cebe7c4)
BibTeX
@misc{dc2d57fc692040,
  title = {GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer — arXiv:2609.04593},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.04593},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2d57fc692040; sha256 9b292edbfa4f603c37e2bb42c0ac74b080d48314c30074f6235010f41cebe7c4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.04593. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-07 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.04593 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T22:31:32.177Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).