Hardware-Aware Sparse QUBO Encoding for CVRPTW on Coherent Ising Machines: An LKH-Guided Variable-Compression Framework

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.