This paper describes a hybrid quantum-classical system for solving the Capacity-Constrained Vehicle Routing Problem (CVRP) using a real-world distribution network in Samarkand, Uzbekistan.The problem is formulated as a quadratic unconstrained binary optimization (QUBO) model, and the solution is implemented using the D-Wave quantum approximate optimization algorithm (QAOA) and quantum annealing. A modular software architecture is described that enables seamless execution on both the IBM Quantum platform and the D-Wave platform. Testing experiments on custom Samarkand instances and standard CVRP datasets showed that the D-Wave hybrid solver yields 1.86–2.34% better solutions than the OR-Tools heuristics on average instances.
This paper describes a hybrid quantum-classical system for solving the Capacity-Constrained Vehicle Routing Problem (CVRP) using a real-world distribution network in Samarkand, Uzbekistan.The problem is formulated as a quadratic unconstrained binary optimization (QUBO) model, and the solution is implemented using the D-Wave quantum approximate optimization algorithm (QAOA) and quantum annealing. A modular software architecture is described that enables seamless execution on both the IBM Quantum platform and the D-Wave platform. Testing experiments on custom Samarkand instances and standard CVRP datasets showed that the D-Wave hybrid solver yields 1.86–2.34% better solutions than the OR-Tools heuristics on average instances.
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.
Quantum Optimization Pipeline for the Capacitated Vehicle Routing Problem (CVRP) This repository presents a research-oriented implementation of classical and quantum optimization techniques for solving the Capacitated Vehicle Routing Problem (CVRP). The project serves as an educational and experimental framework for studying hybrid quantum-classical optimization methods and benchmarking their performance on combinatorial optimization problems. The implementation includes: Classical CVRP optimization using Google OR-Tools Mathematical formulation of the routing problem Transformation of the optimization problem into a Quadratic Unconstrained Binary Optimization (QUBO) model Conversion of the QUBO formulation into an Ising Hamiltonian Implementation of the Quantum Approximate Optimization Algorithm (QAOA) using Qiskit Classical versus quantum performance comparison Route visualization and benchmarking Modular Python code designed for experimentation and future extensions The project is intended as a foundation for exploring applications of Quantum Computing, Operations Research, and Hybrid Quantum-Classical Optimization in real-world routing and logistics problems. It provides a reproducible environment for understanding optimization workflows, evaluating quantum algorithms, and extending the framework toward more complex scenarios such as dynamic vehicle routing and emergency ambulance dispatch. Keywords: Quantum Computing, Quantum Optimization, QAOA, QUBO, Ising Model, Capacitated Vehicle Routing Problem (CVRP), Operations Research, OR-Tools, Qiskit, Combinatorial Optimization, Hybrid Quantum-Classical Algorithms. This software was developed as part of a research internship focused on quantum optimization and serves as a learning and experimentation platform for future research.
The Capacitated Vehicle Routing Problem (CVRP) is a combinatorial optimization problem that can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, making it a potential application for near-term quantum optimization. This paper benchmarks the Quantum Approximate Optimization Algorithm (QAOA, p = 2) against Google OR-Tools Guided Local Search on a seeded instance with three customers and two vehicles. The study examines the QUBO formulation, energy spectrum, optimization behavior, penalty weights, Hamiltonian scaling, and circuit depths. The experiments show that the tested QAOA configurations do not reliably concentrate probability on optimal solutions. The classical solver identifies the optimal solution for the selected instance. The study provides a reproducible baseline and discusses limitations and future research directions. The findings are limited to the tested instance, formulation, and optimization configurations.
Quantum computing (QC) is expected to solve incredibly difficult problems, including finding optimal solutions to combinatorial optimization problems. However, to date, QC alone has still been unable to demonstrate this capability except for small-sized problems. Hybrid approaches, where QC and classical computing work together, have shown the most potential for solving real-world-scale problems. This work aims to show that we can enhance a classical optimization algorithm with QC so that it can overcome this limitation. We present a new Hybrid Quantum-classical Tabu Search (HQTS) algorithm to solve the Capacitated Vehicle Routing Problem (CVRP). Based on our prior work, HQTS leverages QC for routing within a classical tabu search framework. The quantum component formulates the Traveling Salesman Problem (TSP) for each route as a Quadratic Unconstrained Binary Optimization (QUBO) and solves it using D-Wave’s Advantage system. Experiments investigate the impact of quantum routing frequency and starting solution methods. Across different starting solution methods, including quantum-based and classical heuristics, it shows minimal overall impact. HQTS achieved optimal or near-optimal solutions for several CVRP problems, outperforming other hybrid CVRP algorithms and significantly reducing the optimality gap relative to preliminary research. The experimental results demonstrate that more frequent quantum routing improves solution quality and runtime. The findings highlight the potential of integrating QC within meta-heuristic frameworks for complex optimization in vehicle routing problems.
Abstract The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that arises in various fields including transportation and logistics. The CVRP extends from the Vehicle Routing Problem (VRP), aiming to determine the most efficient plan for a fleet of vehicles to deliver goods to a set of customers, subject to the limited carrying capacity of each vehicle. As the number of possible solutions skyrockets when the number of customers increases, finding the optimal solution remains a significant challenge. Recently, the Quantum Approximate Optimization Algorithm (QAOA), a quantum-classical hybrid algorithm, has exhibited enhanced performance in certain combinatorial optimization problems compared to classical heuristics. However, its ability diminishes notably in solving constrained optimization problems including the CVRP. This limitation primarily arises from the typical approach of encoding the given problems as penalty-inclusive binary optimization problems. In this case, the QAOA faces challenges in sampling solutions satisfying all constraints. Addressing this, our work presents a new binary encoding for the CVRP, with an alternative objective function of minimizing the shortest path that bypasses the vehicle capacity constraint of the CVRP. The search space is further restricted by the constraint-preserving mixing operation. We examine and discuss the effectiveness of the proposed encoding under the framework of the variant of the QAOA, Quantum Alternating Operator Ansatz (AOA), through its application to several illustrative examples. Compared to the typical QAOA approach, the proposed method not only preserves the feasibility but also achieves a significant enhancement in the probability of measuring optimal solutions.
Quantum computing (QC) stands at the cusp of revolutionizing computation, yet its near-term potential, constrained by Noisy Intermediate-Scale Quantum (NISQ) devices, remains underexplored. This dissertation investigates how hybrid quantum-classical algorithms can address combinatorial optimization challenges in logistics, focusing on vehicle routing and drone delivery—NP-hard problems with exponential solution spaces that defy classical exhaustive methods. Amidst NISQ limitations like limited qubits and high noise, we confront key challenges: encoding complex constraints, e.g., time windows, battery capacity, into quantum models, balancing quantum and classical components for scalability, and accessing scarce quantum resources. By integrating quantum annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA) with classical heuristics, this work demonstrates QC’s practical utility, advancing both optimization theory and real-world logistics applications. The dissertation unfolds across four core contributions. First, the Hybrid Quantum Tabu Search (HQTS) optimally solves the 50-location Capacitated Vehicle Routing Problem (CVRP), achieving a 4.72% optimality gap. Secondly, we refine HQTS to reach a 2.15% gap with enhanced QA utilization, outperforming prior hybrids on standard datasets. Third, adapting HQTS for the CVRPTWwith D-Wave’s Constrained Quadratic Model solver yields a 3.85% gap on 100-location instances, leveraging a novel heuristic to ensure time-window feasibility where quantum outputs falter. Lastly, QUADRO, a pioneering framework for drone delivery, employs QAOA-driven routing and hybrid scheduling, minimizing transit time and makespan for fleets of 2–11 drones needing fewer than 100 qubits, rivaling classical benchmarks on adapted Augerat datasets. These advances, tested via D-Wave’s Advantage system and Qiskit simulations, showcase hybrid strategies that mitigate NISQ constraints, delivering scalable, feasible solutions to logistics challenges. This work establishes near-term QC’s viability for combinatorial optimization, bridging theoretical promise with practical impact. Synthesizing quantum exploration with classical refinement achieves competitive performance, e.g., matching or surpassing Google ORTools in select CVRPTW cases, while illuminating NISQ limits, such as feasibility degradation beyond small scales. These hybrid strategies deliver scalable, feasible solutions, from a 2.15% optimality gap for CVRP to effective drone fleet management with fewer than 100 qubits, illuminating quantum computing’s potential despite its current constraints. Ultimately, this dissertation positions hybrid QC as a transformative tool for optimization challenges, offering a robust foundation for scaling quantum optimization into operational reality.