Routing-Aware Decomposition for Capacitated Vehicle Routing Problem via Quantum Kernels and Hybrid Refinement

Abstract

Vehicle Routing Problems (VRPs) remain computationally challenging at scale. Since Noisy Intermediate-Scale Quantum (NISQ) devices are not yet mature enough for direct end-to-end Capacitated Vehicle Routing Problem (CVRP) optimization, this study evaluated quantum kernels as structural preprocessing modules for classical routing pipelines. We proposed a hybrid quantum-classical framework in which shallow quantum feature maps generated customer-to-customer similarity matrices from spatial coordinates and normalized demand. These matrices were used as precomputed affinities for spectral clustering, followed by capacity-aware adjustment, reinforcement-learning-based initialization, and Adaptive Large Neighborhood Search (ALNS) refinement. Experiments on eight CVRPLIB instances showed that the proposed ZFeatureMap-based decomposition achieved an optimality gap below 2.0% across all tested instances. Compared with the coordinate-based $k$ -means decomposition baseline under the same downstream pipeline, it improved routing cost on five instances, tied on one, and performed worse on two. The proposed method outperformed SCIP on most instances under the same 60-second limit, but did not outperform PyVRP, which achieved zero optimality gap on all tested instances. Geometrically compact clusters, measured by the Silhouette score, did not necessarily yield better routing performance. Hardware experiments on IBM Quantum’s ibm_kobe processor suggested that clustering-relevant kernel structure remained observable under the tested shallow-circuit NISQ setting, although this should not be interpreted as evidence of scalable routing advantage or real-time QPU deployability. Dense all-pair kernel estimation incurs an $\mathcal{O} {N^{2}}$ preprocessing cost, and scalability, noise, and feature-dimension growth remain important limitations. Despite these limitations, the results suggest that quantum kernels may serve as complementary routing-aware decomposition modules within classical optimization pipelines, particularly for offline structural preprocessing.