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.
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.
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 ON2 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.
Hybrid quantum optimization for vehicle routing faces a practical bottleneck: direct QUBO encodings of CVRP quickly exceed near-term qubit and gate budgets, while quantum evaluations are expensive, noise-limited, and sensitive to backend and circuit configuration. We address this gap with an end-to-end decomposition pipeline that converts CVRP into bounded-width quantum subproblems and treats quantum execution as a decision problem within the optimization loop. Starting from a Fisher--Jaikumar assignment linearization, we apply Lagrangian relaxation to dualize customer-assignment couplers, yielding independent per-vehicle knapsack subproblems that admit QUBO/Ising evaluation. To replace brittle subgradient tuning, we learn a multiplier-update controller using expert-guided pretraining followed by reinforcement-learning fine-tuning, with rewards based on execution-realized progress and route reconstruction. We also introduce a constrained contextual bandit as a hardware-aware execution layer that selects backend and circuit configuration with feasibility screening, enabling adaptation across heterogeneous noisy resources and parallel multi-QPU scheduling. Computational results on multiple CVRPLIB families show that the decomposition yields stable bounded-width subproblems across instance sizes, learned multiplier updates improve end-to-end routing quality relative to classical subgradient control under matched budgets, and hardware-mode configuration reduces median optimality gaps relative to static execution choices in our test set. We do not claim quantum advantage. Instead, the contribution is a practical end-to-end framework for scaling hybrid quantum CVRP optimization through OR decomposition, learning-augmented dual control, and adaptive hardware-aware execution.
Many relevant problems in industrial settings result in NP-hard optimization problems, such as the Capacitated Vehicle Routing Problem (CVRP) or its reduced variant, the Travelling Salesperson Problem (TSP). Even with today's most powerful classical algorithms, the CVRP is challenging to solve classically. Quantum computing may offer a way to improve the time to solution, although the question remains open as to whether Noisy Intermediate-Scale Quantum (NISQ) devices can achieve a practical advantage compared to classical heuristics. The most prominent algorithms proposed to solve combinatorial optimization problems in the NISQ era are the Quantum Approximate Optimization Algorithm (QAOA) and the more general Variational Quantum Eigensolver (VQE). However, implementing them in a way that reliably provides high-quality solutions is challenging, even for toy examples. In this work, we discuss decomposition and formulation aspects of the CVRP and propose an application-driven way to measure solution quality. Considering current hardware constraints, we reduce the CVRP to a clustering phase and a set of TSPs. For the TSP, we extensively test both QAOA and VQE and investigate the influence of various hyperparameters, such as the classical optimizer choice and strength of constraint penalization. Results of QAOA are generally of limited quality because the algorithm does not reach the energy threshold for feasible TSP solutions, even when considering various extensions such as recursive and constraint-preserving mixer QAOA. On the other hand, the VQE reaches the energy threshold and shows a better performance. Our work outlines the obstacles to quantum-assisted solutions for real-world optimization problems and proposes perspectives on how to overcome them.
The Capacitated Vehicle Routing Problem is one of the most well-known issues in operations research and transportation logistics. It comprises optimizing a set of vehicle routes to serve a set of clients, subject to vehicle capacity restrictions. Reducing the total distance that the cars go is the aim of the challenge. The Capacitated Vehicle Routing Problem has been studied by academics for a very long time. This topic is receiving a lot of interest because it can be applied to almost every industry, including marketing, logistics, healthcare, and others. One of the main obstacles, though, is that when the problem is attempted to be solved for a greater number of clients and vehicles, the problem becomes so complex that standard computers are either unable to solve it or require several months or even years to generate an output. We proposed an approach for this restriction that enables the problem to be resolved with quantum computers. We use two algorithms in our methodology, Constrained Clustering and Fuzzy C-Means, to attain our results. Clustering and routing are the two phases each of these algorithms go through. This method involves grouping all connected consumers into different clusters and then conducting routing within each cluster. They work with notable efficiency, producing optimal solutions in a noticeably smaller span of time. The results show that the CC approach outperforms FCM in most instances, achieving an average optimality gap of 13.04%, compared to 16.5% for FCM. Furthermore, both approaches perform significantly better than non-clustered methods.
Vehicle Routing Problem (VRP) is considered one of the most challenging problems with application in several domains, including transportation and logistics distribution. VRP is known to be NP-Hard problem. Several algorithms have been proposed to solve VRP in polynomial time. However, these algorithms are inefficient if the VRP instance increases. Recently, researchers investigated how quantum computing can be used to solve VRP. In particular, two promising variational quantum algorithms have been studied, i.e., Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization Algorithm (QAOA). In this paper, we implement both algorithms on IBM Qiskit and compare their evaluation in solving several instances of VRP. We observe that current Noisy-Intermediate Scale Quantum (NISQ) devices cannot solve VRP instances beyond 5 nodes and 2 vehicles. Furthermore, we observe that classical optimizers still provide better results. However, we believe that with the rapid advancement of quantum computing manufacturing, VQE and QAOA can provide better performance as compared to classical computing,
We introduce a transparent, encoding-agnostic framework for determining when the Capacitated Vehicle Routing Problem (CVRP) can achieve early quantum advantage. Our analysis shows this is unlikely on noisy intermediate scale quantum (NISQ) hardware even in best case scenarios that use the most qubit-efficient direct encodings. Closed-form resource counts, combined with recent device benchmarks, yield three decisive go/no-go figures of merit: the quantum feasibility point and the qubit- and gate-feasibility lines, which place any CVRP instance on a single decision diagram. Contrasting a direct QUBO mapping with a space-efficient higher-order (HOBO) encoding reveals a large gap. Applied to early-advantage benchmarks such as Golden-5, our diagram shows that HOBO circuits require only 7,685 qubits, whereas comparable QUBO encodings still exceed 200,000 qubits. In addition to identifying candidate instances for early quantum advantage in CVRP, the framework provides a unifying go/no-go metric that ingests any CVRP encoding together with any hardware profile and highlights when quantum devices could challenge classical heuristics. Quantum advantage in CVRP would likely require innovative problem decomposition techniques.