Metraipolis › archive › dc_bb40b34bd46a
Correcting Connectivity in Arc-Based QUBO Models for Fixed-Fleet Vehicle Routing — arXiv:2608.26894
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.26894
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T19:21:14.260Z
- SHA-256 of the archived text
9fe05b1d03600809a240ec42cc30f0ab0aa53be40142d2cf900ebe43f1a9e5cb- Stable URL of this page
https://metraipolis.com/documento/dc_bb40b34bd46a
How to cite
Correcting Connectivity in Arc-Based QUBO Models for Fixed-Fleet Vehicle Routing — arXiv:2608.26894 — arXiv (en), https://arxiv.org/abs/2608.26894 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bb40b34bd46a (Metraipolis archive dc_bb40b34bd46a, sha256 9fe05b1d03600809a240ec42cc30f0ab0aa53be40142d2cf900ebe43f1a9e5cb)
BibTeX
@misc{dcbb40b34bd46a,
title = {Correcting Connectivity in Arc-Based QUBO Models for Fixed-Fleet Vehicle Routing — arXiv:2608.26894},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.26894},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bb40b34bd46a; sha256 9fe05b1d03600809a240ec42cc30f0ab0aa53be40142d2cf900ebe43f1a9e5cb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.26894. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We revisit a degree-only arc Hamiltonian for fixed-fleet, homogeneous, uncapacitated vehicle routing. Its local penalties define only a cycle cover, so ground states may contain customer cycles disconnected from the depot. We construct a polynomial-size quadratic unconstrained binary optimization (QUBO) repair using capped single-commodity flow and prove connected, cost-optimal ground-state routings under explicit penalty assumptions. For $N-1$ customers and $K$ nonempty routes, the unreduced encoding uses exactly $|E|(1+\lceil\log_2(N-K+1)\rceil)$ logical problem qubits. A reversible compute-phase-uncompute implementation evaluates the flow penalties in $O(N^2\log N+N\log^2N)$ logical gates on a complete graph, using $O(\log N)$ reusable workspace and no product register. On complete loopless graphs, a position encoding that arranges all routes in one sequence separated by depot occurrences uses fewer problem qubits and written terms when the number of bits per flow register grows. Under the same reversible accounting model, the flow formulation admits a smaller logical-gate upper bound. Exact Hamiltonian and circuit audits and a benchmark of 1,200 cost matrices verify the formulation and quantify the connectivity gap. A 32,000-shot Amazon Braket task on IQM Emerald characterizes depth-one termwise Ising circuits for a diagnostic $N=4$, $K=1$ counterexample. In the degree-only circuit, 78.05% of selected $p=1$ shots realize the invalid disconnected ground state; the reduced 14-qubit flow-augmented circuit yields no fully feasible sample. These device results characterize mapped Hamiltonians and compilation, not an asymptotic advantage in solving routing problems. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-28 in cs.DS). Categorie arXiv: Quantum Physics (quant-ph) ; Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2608.26894 — 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-17T19:16:36.845Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).