Hardware-Aware Sparse QUBO Encoding for CVRPTW on Coherent Ising Machines: An LKH-Guided Variable-Compression Framework
Algorithms · 29.06.2026 · 19 (7) · 525
DOI: 10.3390/a19070525 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithms, online erschienen am 29.06.2026. Verfasst von Zhitao Wu und 4 weiteren Autor:innen. Die Arbeit nennt 49 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Natural Science Foundation of Gansu Province.
Abstract (Originalsprache)
Capacitated vehicle routing with time windows (CVRPTW) is a natural target for coherent Ising machines (CIMs), but a direct multi-vehicle arc encoding scales as O(mN2) and exceeds the variable budget of current CIM-compatible systems. We argue the bottleneck is encoding density, not expressiveness, and present LSQ, a hardware-aware sparse Quadratic Unconstrained Binary Optimization (QUBO) framework that decouples CVRPTW into a compact customer-to-route assignment QUBO and a classical intra-route ordering step under a soft no-wait service convention. LKH candidate edges compress the per-route edge space from O(N2) to O(KN), and a per-route dynamic-penalty subroutine encodes time-window sensitivities as binary variables in a round-wise outer loop. On a six-vehicle, 51-node reference instance curated from long-term operational data, LSQ shrinks the maximum single-submission QUBO from 15,300 arc variables to 342 logicalQUBOvariables (∼45× compression), cuts travel time by 22.9% (74 vs. 96), and cuts route duration by 11.2% (174 vs. 196) against an OR-Tools soft-window baseline at the same fleet size. OR-Tools retains an advantage on raw time-window penalty (1600 vs. 3540) and runtime; under the scalar operational cost ∑kT(πk)+∑iℓi(τi), OR-Tools is therefore the better single-objective solver, and the comparison is a multi-objective trade-off rather than a scalar dominance claim. Ablations confirm that the LKH prior recovers Held–Karp on a 15-customer TSP at 53 vs. 120 variables and that the dynamic-penalty encoding reduces compressed time-window loss by 15.25% at constant travel. All hardware claims refer to QUBO sizing on a Kaiwu/CIM-compatible backend, not physical CIM execution.
Förderung
- Natural Science Foundation of Gansu Province
Zitieren
APA
Wu, Z., Yang, Z., Zhou, J., Li, X., & Wang, H. (2026). Hardware-Aware Sparse QUBO Encoding for CVRPTW on Coherent Ising Machines: An LKH-Guided Variable-Compression Framework. Algorithms, 19(7), 525. https://doi.org/10.3390/a19070525
Vancouver
Wu Z, Yang Z, Zhou J, Li X, Wang H. Hardware-Aware Sparse QUBO Encoding for CVRPTW on Coherent Ising Machines: An LKH-Guided Variable-Compression Framework. Algorithms. 2026;19(7):525. doi:10.3390/a19070525
BibTeX
@article{Wu2026,
author = {Wu, Zhitao and Yang, Zonglin and Zhou, Jie and Li, Xuechen and Wang, Hongmin},
title = {Hardware-Aware Sparse QUBO Encoding for CVRPTW on Coherent Ising Machines: An LKH-Guided Variable-Compression Framework},
journal = {Algorithms},
year = {2026},
volume = {19},
number = {7},
pages = {525},
doi = {10.3390/a19070525}
}
EUVIMED