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.
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.
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.
The Capacitated Vehicle Routing Problem (CVRP) is a fundamental NP-hard problem in logistics. Augmented Lagrangian Methods (ALM) for solving CVRP performance depends heavily on well-tuned penalty parameters. In this paper, we propose a hybrid optimization approach that integrates deep reinforcement learning (RL) to automate the selection of penalty parameter values within both classical (RL-C-ALM) and quantum-enhanced (RL-Q-ALM) ALM solvers. Using Soft Actor-Critic, our approach learns penalty values from CVRP instance features and constraint violations. In RL-Q-ALM, subproblems are encoded as QUBOs and solved using Variational Quantum Eigensolvers (VQE). The agent learns across episodes by maximizing solution feasibility and minimizing cost. Experiments show that RL-C-ALM outperforms manually tuned ALM on synthetic and benchmark CVRP instances, achieving better solutions with fewer iterations. Also, RL-Q-ALM matches classical solution quality on small instances but incurs higher runtimes due to quantum overhead. Our results highlight the potential of combining RL with classical and quantum solvers for scalable, adaptive combinatorial 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.
Quantum Reinforcement Learning (QRL) integrates reinforcement learning with parameterized quantum circuits and is a promising approach to combinatorial optimization. On Noisy Intermediate-Scale Quantum (NISQ) devices, however, decoherence, gate imperfections, and measurement errors reduce policy quality and make learning less reliable. Existing error mitigation techniques are generally applied as fixed corrections that do not adapt to changing noise conditions or to the evolving state of training. This work presents Adaptive Policy-Guided Error Mitigation (APGEM) as a context-aware orchestration layer of the hybrid quantum-classical training loop that dynamically selects the most suitable mitigation strategy during QRL training. APGEM evaluates Zero-Noise Extrapolation (ZNE), Probabilistic Error Cancellation (PEC), Clifford Data Regression (CDR), and Readout Error Mitigation (REM) using policy-level indicators, including quantum-state fidelity, policy entropy, cumulative reward, and approximation ratio, and integrates the selected strategy directly into the reinforcement learning loop. The framework is evaluated on the Capacitated Vehicle Routing Problem (CVRP), a representative NP-hard problem in urban logistics, under a range of NISQ noise models and noise levels. APGEM consistently outperforms conventional static mitigation methods, reaches approximately 94% of the utility of an oracle strategy, maintains higher quantum-state fidelity as noise increases, and produces more stable learning behaviour throughout training. Ablation studies show that the framework learns context-aware mitigation policies that adapt to different noise environments and circuit execution conditions. These findings demonstrate that integrating adaptive error mitigation into the learning process substantially improves the robustness and reliability of QRL on NISQ hardware.
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.
This study develops a hybrid quantum-classical framework for constrained vehicle routing problems, focusing on the pickup-and-delivery problem with time windows. Instead of casting the full routing problem as a stand-alone quantum optimization task, we embed shallow quantum samplers inside the repair phase of an Adaptive Large Neighbourhood Search (ALNS) heuristic. A Deep Q-Network controller decides whether each reduced repair subproblem should be handled by a classical repair heuristic or by a quantum sampler, using features that describe the local repair structure and predicted hardware reliability. IBM Heron experiments are used to calibrate an empirical noise-aware model for local quantum repair circuits. Across the tested instances, quantum repair is admissible in only about 16% of reduced repair states and is not superior on average. However, under selected matched repair budgets, quantum-enabled repair reduces the final gap relative to standard ALNS in 29 of 36 tested settings. These results suggest that near-term quantum sampling is most useful as a selective local repair mechanism rather than as a replacement for classical routing heuristics.