Correcting Connectivity in Arc-Based QUBO Models for Fixed-Fleet Vehicle Routing
Abstract
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+⌈log2(N−K+1)⌉) logical problem qubits. A reversible compute-phase-uncompute implementation evaluates the flow penalties in O(N2log N+Nlog2N) 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.
Related
- RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem
- Hybridizing 0/1 Knapsack and Priority-Aware TSP for Vehicle Routing: an Applied Variant of the TSP with Profits
- Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes
- Robust Heterogeneous Vehicle Routing Optimization for Hazmat Transportation Under Time-Varying Risk
- Carbon-Aware Electric Vehicle Routing Problem with Decision-Focused Learning
BibTeX
@misc{gurevich2026correcting,
title = {{Correcting Connectivity in Arc-Based QUBO Models for Fixed-Fleet Vehicle Routing}},
author = {Omer Gurevich and Maor Matityahu and Tal Mor and Aryeh Lev Zabokritskiy},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.26894},
eprint = {2608.26894},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.26894},
}
RIS
TY - UNPB
TI - Correcting Connectivity in Arc-Based QUBO Models for Fixed-Fleet Vehicle Routing
AU - Omer Gurevich
AU - Maor Matityahu
AU - Tal Mor
AU - Aryeh Lev Zabokritskiy
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2608.26894
UR - https://arxiv.org/abs/2608.26894
AB - 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+⌈log_2(N−K+1)⌉) logical problem qubits. A reversible compute-phase-uncompute implementation evaluates the flow penalties in O(N^2log N+Nlog^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.
ER -