Source-linked AI summary
A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
Sebastian Feld, Christoph Roch, Thomas Gabor, Christian Seidel, Florian Neukart, Isabella Galter, Wolfgang Mauerer, Claudia Linnhoff-Popien
TL;DR
CVRP requires efficient capacity-constrained vehicle routing, while its combinatorial scale and QUBO-to-hardware mapping make quantum solution difficult. The paper develops a hybrid method that decomposes CVRP into clustering and routing subproblems and evaluates it against classical approaches. It competes with classical heuristics in solution quality in some cases, but the study finds no clear overall benefit in quality or computation time.
Problem
CVRP requires designing minimum-cost depot-based routes for customers under capacity constraints, while mapping large instances to quantum-annealing hardware is difficult because of limited qubits and connectivity.
Method
The paper maps CVRP components to QUBO formulations and uses a classical 2-Phase-Heuristic to solve clustering and routing through hybrid quantum-classical approaches.
Results
The hybrid method competed with classical construction and 2-phase heuristics and sometimes surpassed them in solution quality, while QBSolv overhead made the classical version more advantageous in total calculation time.
Takeaways & Limitations
The study demonstrates a hybrid decomposition approach for applying quantum annealing to complex optimization problems, but reports no clear benefit in solution quality or computational time.
Takeaways & Limitations
Larger QUBOs require QBSolv because current hardware has limited qubits, adding latency and waiting times that reduce hoped-for computational acceleration.
Abstract
from arXiv · showhide
The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that has been of great interest for decades for both, science and industry. The CVRP is a variant of the vehicle routing problem characterized by capacity constrained vehicles. The aim is to plan tours for vehicles to supply a given number of customers as efficiently as possible. The problem is the combinatorial explosion of possible solutions, which increases superexponentially with the number of customers. Classical solutions provide good approximations to the globally optimal solution. D-Wave's quantum annealer is a machine designed to solve optimization problems. This machine uses quantum effects to speed up computation time compared to classic computers. The problem on solving the CVRP on the quantum annealer is the particular formulation of the optimization problem. For this, it has to be mapped onto a quadratic unconstrained binary optimization (QUBO) problem. Complex optimization problems such as the CVRP can be translated to smaller subproblems and thus enable a sequential solution of the partitioned problem. This work presents a quantum-classic hybrid solution method for the CVRP. It clarifies whether the implemenation of such a method pays off in comparison to existing classical solution methods regarding computation time and solution quality. Several approaches to solving the CVRP are elaborated, the arising problems are discussed, and the results are evaluated in terms of solution quality and computation time.
1 Introduction
The paper frames CVRP as a capacity-constrained routing problem whose large combinatorial search space complicates direct quantum-annealer solution. It proposes splitting CVRP into clustering and routing subproblems, mapping them to QUBO formulations for hybrid quantum-classical solution.
- Problem definition: CVRP seeks minimum-cost vehicle routes from one depot to geographically scattered customers under capacity and routing constraints.Each customer must be visited exactly once, routes must start and end at the depot, and route demand cannot exceed vehicle capacity.
- Quantum formulation: D-Wave solution requires formulating CVRP as a quadratic unconstrained binary optimization problem and mapping it onto hardware.The paper identifies limited qubit count and connectivity as obstacles to mapping large QUBOs.
- Proposed approach: The proposed 2-Phase-Heuristic separates CVRP into clustering and routing phases to create smaller optimization problems.Clustering assigns customers to capacity-restricted vehicles, while routing seeks a shortest depot-returning tour within each cluster.
- Problem decomposition: The clustering phase is represented by Knapsack Problems, while the routing phase is represented by Travelling Salesman Problems.This decomposition solves the two components sequentially or as part of hybrid approaches.
- Study scope: The study investigates quantum-classical hybrid CVRP approaches and evaluates solution quality and computational performance on large benchmark datasets.It discusses implementation difficulties before proposing a hybrid method using D-Wave’s quantum annealer.
2 Quantum Annealing on D-Wave processor
The section explains how D-Wave quantum annealing interpolates between an initial and problem Hamiltonian to minimize QUBO objectives. Hardware qubit connectivity and limited capacity require embedding techniques and QBSolv decomposition for larger problems.
- Quantum annealing: Quantum annealing interpolates between an initial Hamiltonian with an easy ground state and a problem Hamiltonian whose minimum-energy state encodes the solution.The interpolation follows a time-dependent path governed by s(t).
- QUBO formulation: D-Wave hardware minimizes QUBO objectives over binary variable assignments represented by a variable vector x and matrix Q.Matrix Q describes relationships between variables, and the annealer seeks assignments minimizing the resulting objective.
- Hardware mapping: The QPU represents QUBO variables as qubits and variable couplings as edges in a Chimera graph.Auxiliary qubits may augment couplings when the logical problem structure cannot be embedded directly.
- Chimera architecture: The full Chimera graph contains 2048 qubits arranged as a 16 × 16 lattice of groups of 8 qubits.The paper uses an instance with 2038 working qubits and 5955 couplers.
- Scaling constraint: QBSolv splits oversized QUBOs into smaller components and solves them sequentially when the problem cannot fit on the QPU.This addresses large data sets whose QUBO size exceeds the available hardware qubits.
3 Related Work
Related work spans construction, improvement, and metaheuristic approaches for CVRP, including classical two-phase methods. Quantum-computing studies have explored QUBO mappings and embeddings but have not yet matched state-of-the-art classical approaches on small instances.
- Heuristic families: CVRP heuristics are commonly divided into construction heuristics, improvement heuristics, and metaheuristics.Construction methods build solutions incrementally, improvement methods modify feasible tours, and metaheuristics guide local improvement toward global solutions.
- Classical methods: Construction heuristics include Clarke and Wright savings, which iteratively merges customer tours according to calculated savings.Improvement heuristics instead swap or replace customers between sub-tours while respecting capacity constraints.
- Two-phase heuristics: Classical two-phase methods first form feasible customer clusters and then solve a TSP for each cluster.Examples include Sweep, generalized-assignment-based clustering, and capacitated-location-based seed selection.
- Quantum-computing research: Prior quantum-computing research studied small hard operational-planning instances under different QUBO mappings and embeddings.That study did not produce results competitive with state-of-the-art classical approaches but offered programming and hardware-design insights.
4 Concept of Hybrid Solution Method
The proposed Hybrid Solution separates CVRP clustering and routing: a classical method forms capacity-feasible customer clusters, while quantum annealing solves a TSP QUBO within each cluster. Earlier sequential and simultaneous quantum approaches encountered parameter-selection or objective-conflict problems that motivated this division.
- Approach decomposition: The 2-Phase-Heuristic divides CVRP into clustering and routing, represented by KP with distance minimization and TSP, respectively.This decomposition permits the two phases to be mapped to one or two QUBO problems and executed sequentially.
- Preliminary approaches: The first Q2Q approach was impractical because its clustering edge-weighting parameter had to be selected individually for each dataset.The parameter was intended to group nearby customers, but experiments found no generally suitable value.
- Preliminary approaches: The simultaneous Q1Q approach produced invalid or unusable solutions because its clustering and routing optimization functions hindered each other.Omitting clustering produced sparse clusters, whereas omitting routing produced dense clusters with invalid internal routes.
- Hybrid Solution: The proposed HS assigns clustering to a classical algorithm and maps routing within each cluster to a TSP QUBO solved on the quantum annealer.This combines the favorable aspects of the previous approaches while avoiding their problematic joint optimization.
- Clustering phase: HS clustering generates and improves clusters using capacity-aware assignments centered on a selected core stop.Core stops may be chosen by maximum demand or largest depot distance; customers are then added by proximity to the recalculated cluster center.
- Routing phase: For each generated cluster, the routing phase formulates the TSP as a Hamiltonian-cycle QUBO whose constraints enforce unique customer positions and whose objective sums successive-edge distances.The routing penalty B must remain sufficiently small relative to the constraint penalty A; experiments set B = 1 and A = n · max(Dui).
5 Evaluation
The evaluation examines QBSolv-based TSP and hybrid CVRP performance across solution quality and runtime. Results show size-dependent solution quality, parameter sensitivity, dataset-specific clustering choices, and lower remote QUBO-solving time offset by execution overhead.
- Test setup: QBSolv splits QUBOs into smaller subQUBOs and repeats this process iteratively, either classically or through quantum-classic hybrid solving.The num_repeats parameter controls how often the QUBO splitting is repeated after an improved sample is found.
- TSP – Solution Quality: For smaller TSP instances, the quantum annealer found the BKS with average deviations of 0.00% to 0.31%; larger instances had deviations of 2.70% to 25.91%.The BKS was not found for the larger problem sizes, which yielded only good approximations.
- CVRP – Solution Quality: Larger CVRP datasets showed greater deviation variance, increasing from 0.00% for dataset (1) to 11.12%-36.01% for dataset (5).Datasets (4) and (5) fluctuated over 2.50%-13.77% and 11.12%-36.01%, respectively.
- CVRP – Solution Quality: Increasing num_repeats tended to improve solution quality by decreasing deviation from the BKS.Burma14 was excluded because num_repeats set to 50 found the BKS in every run; each other setting was executed 10 times.
- CVRP – Solution Quality: The hybrid method achieved 2.66%-6.91% deviation on the first three datasets, but the core stop had to be selected individually for each dataset.The results did not establish a problem-size-independent choice between max_distance and max_request.
- CVRP – Computational Results: The locally executed hybrid algorithm took 1.474 seconds versus 15.792 seconds remotely, although remote QUBO solving itself took 0.11 seconds versus 0.234 seconds locally.Remote embedding, Internet latency, and hardware queueing created overhead, making local QBSolv more advantageous in total calculation time.
6 Conclusion
The study presents a hybrid quantum-classic CVRP method based on splitting the problem into clustering and routing phases. It reports no clear overall benefit yet, while identifying hardware size and mapping overhead as important future considerations.
- Conclusion: The hybrid method divides CVRP into clustering and routing phases and solves them sequentially or simultaneously through Q2Q and Q1Q approaches.The method uses a classical 2-phase heuristic and maps the resulting optimization problems to QUBOs.
- Conclusion: The hybrid method competed with classical construction and 2-phase heuristics and sometimes surpassed them in solution quality.The paper also states that metaheuristics produced better solutions on the benchmark datasets.
- Conclusion: QBSolv introduces latency and waiting times because limited qubit counts prevent large QUBOs from being embedded directly on the D-Wave chip.QBSolv splits large QUBOs into smaller subQUBOs processed sequentially on the quantum annealer.
- Conclusion: Increasing hardware size is expected to reduce QBSolv use and classical overhead, while embeddable QUBO solution time is expected to remain in the microsecond range.The paper identifies effective scaling, QBSolv necessity, and annealing duration as future research topics.
- Conclusion: The study concludes that the hybrid method has not produced a clear benefit in solution quality or computational time.Establishing a clear advantage remains future work while larger hardware is awaited.
Appendix
The appendix reports local and remote QBSolv profiling outputs alongside repeated QPU access-time measurements. The listings provide execution-time and access-time figures for the tested configurations.
- Appendix: Additional QPU access-time pairs are reported as 7783 versus 7789, 7787 versus 7783, and 7808 versus 7807.The values appear in the later appendix listing.
- Appendix: The appendix lists QPU access times of 7814 versus 7778, 7768 versus 7795, 7802 versus 7788, and 7807 versus 7782.These paired values are reported in the QBSolv output listings.
- Appendix: The remote QBSolv access-time listing states that qpu_access_time includes programming through post-processing overhead.This description defines the reported access-time measure for the remote execution listing.