Beyond Euclidean Clustering: Quantum Kernel-Driven Decomposition for the Capacitated Vehicle Routing Problem

Vehicle routing problems (VRPs) remain challenging at scale under practical time budgets. Since noisy intermediate-scale quantum (NISQ) devices are not yet suitable for end-to-end capacitated VRP (CVRP) optimization, we use quantum processors as feature extractors for structural preprocessing. We propose a hybrid quantum-classical pipeline in which a shallow quantum feature map induces a quantum kernel that defines nonlinear customer-to-customer similarities. The induced similarities drive a spectral-clustering-based decomposition, which is refined by capacity adjustment, and the resulting subproblems are solved by a classical routing pipeline with RL-based initialization and adaptive large neighborhood search (ALNS). Compared with a strong classical baseline that applies K-means on the same feature space, we find that higher geometric cluster separability (e.g., Silhouette score) does not necessarily yield better downstream routing. In contrast, quantum-kernel-driven decomposition achieves smaller routing optimality gaps (sub-2% under our evaluation setting) on difficult instances such as CMT1, indicating that quantum kernels can capture latent routing-aware structure beyond Euclidean clustering. Experiments on IBM's ibm_kobe device further show that clustering-relevant kernel structure remains observable under hardware noise, supporting the feasibility of NISQ-era quantum kernels as scalable structural components in logistics optimization.