The Capacitated Vehicle Routing Problem (CVRP) involves finding the shortest possible routes for a fleet of vehicles, each with a fixed capacity limit, to serve a set of customers where every customer is visited exactly once. When CVRP is encoded as a Quadratic Unconstrained Binary Optimization (QUBO) model, one of the biggest practical hurdles is setting the penalty coefficients correctly — a process that is typically done by hand and has to be repeated for every new problem instance. This paper introduces a new technique called BOSA (Bayesian Optimization for Simulated Annealing), a framework that removes this manual step by using Gaussian Process-based Bayesian Optimization to find good penalty values automatically, while the underlying QUBO is solved using Simulated Annealing. Our hybrid approach integrates multi-start greedy construction and 2-opt local search to ensure solution feasibility when SA produces invalid routes. Experiments on 11 benchmark instances demonstrate solution distances of 12.04%- 33.26% relative to the best-known optima. On the two instances where comparison is possible, our proposed technique, BOSA achieves shorter routes than D-Wave (949 vs 1085 for A-n32-k5, and 2240 vs 2660 for A-n80-k10), suggesting that automated classical penalty tuning can match or exceed commercial quantum annealing solutions on these problem sizes without requiring quantum resources. Although not competitive with state-of-the-art CVRP solvers such as HGS and branch and cut algorithm, our automated tuning framework provides a foundation for future quantum-classical hybrid algorithms. It demonstrates the viability of BO-driven parameter optimization for QUBO-based combinatorial problems.
The Capacitated Vehicle Routing Problem (CVRP) involves finding the shortest possible routes for a fleet of vehicles, each with a fixed capacity limit, to serve a set of customers where every customer is visited exactly once. When CVRP is encoded as a Quadratic Unconstrained Binary Optimization (QUBO) model, one of the biggest practical hurdles is setting the penalty coefficients correctly — a process that is typically done by hand and has to be repeated for every new problem instance. This paper introduces a new technique called BOSA (Bayesian Optimization for Simulated Annealing), a framework that removes this manual step by using Gaussian Process-based Bayesian Optimization to find good penalty values automatically, while the underlying QUBO is solved using Simulated Annealing. Our hybrid approach integrates multi-start greedy construction and 2-opt local search to ensure solution feasibility when SA produces invalid routes. Experiments on 11 benchmark instances demonstrate solution distances of 12.04%- 33.26% relative to the best-known optima. On the two instances where comparison is possible, our proposed technique, BOSA achieves shorter routes than D-Wave (949 vs 1085 for A-n32-k5, and 2240 vs 2660 for A-n80-k10), suggesting that automated classical penalty tuning can match or exceed commercial quantum annealing solutions on these problem sizes without requiring quantum resources. Although not competitive with state-of-the-art CVRP solvers such as HGS and branch and cut algorithm, our automated tuning framework provides a foundation for future quantum-classical hybrid algorithms. It demonstrates the viability of BO-driven parameter optimization for QUBO-based combinatorial problems.
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.
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.
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.
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.
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 annealing (QA) is a quantum computing algorithm that works on the principle of Adiabatic Quantum Computation (AQC), and it has shown significant computational advantages in solving combinatorial optimization problems such as vehicle routing problems (VRP) when compared to classical algorithms. This paper presents a QA approach for solving a variant VRP known as multi-depot capacitated vehicle routing problem (MDCVRP). This is an NP-hard optimization problem with real-world applications in the fields of transportation, logistics, and supply chain management. We consider heterogeneous depots and vehicles with different capacities. Given a set of heterogeneous depots, the number of vehicles in each depot, heterogeneous depot/vehicle capacities, and a set of spatially distributed customer locations, the MDCVRP attempts to identify routes of various vehicles satisfying the capacity constraints such as that all the customers are served. We model MDCVRP as a quadratic unconstrained binary optimization (QUBO) problem, which minimizes the overall distance traveled by all the vehicles across all depots given the capacity constraints. Furthermore, we formulate a QUBO model for dynamic version of MDCVRP known as D-MDCVRP, which involves dynamic rerouting of vehicles to real-time customer requests. We discuss the problem complexity and a solution approach to solving MDCVRP and D-MDCVRP on quantum annealing hardware from D-Wave.