Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2309.05564

Performance of Commercial Quantum Annealing Solvers for the Capacitated Vehicle Routing Problem

Salvatore Sinno, Thomas Groß, Alan Mott, Arati Sahoo, Deepak Honnalli, Shruthi Thuravakkath, Bhavika Bhalgamiya

Published Sep 11, 2023• 2 citations
arXivHTMLPDF

Abstract

Quantum annealing (QA) is a heuristic search algorithm that can run on Adiabatic Quantum Computation (AQC) processors to solve combinatorial optimization problems. Although theoretical studies and simulations on classic hardware have shown encouraging results, these analyses often assume that the computation occurs in adiabatically closed systems without environmental interference. This is not a realistic assumption for real systems; therefore, without extensive empirical measurements on real quantum platforms, theory-based predictions, simulations on classical hardware or limited tests do not accurately assess the current commercial capabilities. This study has assessed the quality of the solution provided by a commercial quantum annealing platform compared to known solutions for the Capacitated Vehicle Routing Problem (CVRP). The study has conducted extensive analysis over more than 30 hours of access to QA commercial platforms to investigate how the size of the problem and its complexity impact the solution accuracy and the time used to find a solution. Our results have found that the absolute error is between 0.12 and 0.55, and the quantum processor unit (QPU) time is between 30 and 46 micro seconds. Our results show that as the constraint density increases, the quality of the solution degrades. Therefore, more than the problem size, the model complexity plays a critical role, and practical applications should select formulations that minimize the constraint density.

DOI
10.48550/arxiv.2309.05564

Related papers

Analyzing performance of commercial quantum annealing solvers for the capacitated vehicle routing problem

Salvatore Sinno, Thomas Groß, Alan Mott +4 more

Quantum Annealing (QA) is a heuristic search algorithm that can run on adiabatic quantum computation processors to solve combinatorial optimization problems. Although theoretical studies and simulations on classical hardware have shown encouraging results, these analyses often assume that the computation occurs in adiabatically closed systems without environmental interference. This is not a realistic assumption for real systems; therefore, without extensive empirical measurements on real quantum platforms, theory-based predictions, simulations on classical hardware, or limited tests do not accurately assess the current commercial capabilities. This study has assessed the quality of the solution provided by a commercial quantum annealing platform compared to known solutions for the capacitated vehicle routing problem. This study has conducted an extensive analysis on more than 30 hours of access to QA commercial platforms to investigate how the size of the problem and its complexity impact the accuracy of the solution and the time used to find a solution. Our results have found that the absolute error is between 0.12 and 0.55, and the time of the quantum processor unit is between 30 and 46 μs. Our results show that as the constraint density increases, the quality of the solution degrades. Therefore, more than the size of the problem, the complexity of the model plays a critical role, and practical applications should select formulations that minimize the constraint density.

AIP Advances•Dec 1, 2025•2 citations

Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem

Lilly Palackal, Benedikt Poggel, Matthias Wulff +3 more

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.

arXiv:2304.09629•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•24 citations

A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem

Harikrishnakumar, Ramkumar, Saideep Nannapaneni, Nguyen, Nam H. +2 more

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.

arXiv:2005.12478•May 26, 2020•16 citations

A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer

Sebastian Feld, Christoph Roch, Thomas Gabor +5 more

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.

arXiv:1811.07403•Frontiers in ICT•Jun 25, 2019•190 citations

On Solving the Capacitated Vehicle Routing Problem with Time Windows using Quantum Annealing

Axel Vargas, Pradyumn Kumar Shukla, Richard Allmendinger +1 more

This study explores Quantum Annealing (QA) versus Classical Computing (CC) approaches in solving the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), using real-world logistics data from Siemens Advanta. By modeling the problem as a Service Network Design (SND) with binary variables and framing CVRPTW within a quantum mechanical paradigm suitable for QA, this approach leverages quantum annealing in a novel manner to tackle the complex optimization challenges inherent in the VRP. Contrasting it with the performance of the traditional branch and cut solver---a specific CC technique---this research unveils the prospective benefits and existing challenges of QA in complex optimization scenarios, thereby emphasizing the need for advancing quantum computing.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2024•3 citations

An Advanced Hybrid Quantum Tabu Search Approach to Vehicle Routing Problems

James B. Holliday, Eneko Osaba, Khoa Luu

Quantum computing (QC) is expected to solve incredibly difficult problems, including finding optimal solutions to combinatorial optimization problems. However, to date, QC alone is still far to demonstrate this capability except on 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 QUBO, solved using D-Wave's Advantage system. Experiments investigate the impact of quantum routing frequency and starting solution methods. While different starting solution methods, including quantum-based and classical heuristics methods, 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 compared 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.

arXiv:2501.12652•Jan 22, 2025•0 citations
Quantum annealing (QA) is a heuristic search algorithm that can run on Adiabatic Quantum Computation (AQC) processors to solve combinatorial optimization problems. Although theoretical studies and simulations on classic hardware have shown encouraging results, these analyses often assume that the computation occurs in adiabatically closed systems without environmental interference. This is not a realistic assumption for real systems; therefore, without extensive empirical measurements on real quantum platforms, theory-based predictions, simulations on classical hardware or limited tests do not accurately assess the current commercial capabilities. This study has assessed the quality of the solution provided by a commercial quantum annealing platform compared to known solutions for the Capacitated Vehicle Routing Problem (CVRP). The study has conducted extensive analysis over more than 30 hours of access to QA commercial platforms to investigate how the size of the problem and its complexity impact the solution accuracy and the time used to find a solution. Our results have found that the absolute error is between 0.12 and 0.55, and the quantum processor unit (QPU) time is between 30 and 46 micro seconds. Our results show that as the constraint density increases, the quality of the solution degrades. Therefore, more than the problem size, the model complexity plays a critical role, and practical applications should select formulations that minimize the constraint density.
Quantum Annealing (QA) is a heuristic search algorithm that can run on adiabatic quantum computation processors to solve combinatorial optimization problems. Although theoretical studies and simulations on classical hardware have shown encouraging results, these analyses often assume that the computation occurs in adiabatically closed systems without environmental interference. This is not a realistic assumption for real systems; therefore, without extensive empirical measurements on real quantum platforms, theory-based predictions, simulations on classical hardware, or limited tests do not accurately assess the current commercial capabilities. This study has assessed the quality of the solution provided by a commercial quantum annealing platform compared to known solutions for the capacitated vehicle routing problem. This study has conducted an extensive analysis on more than 30 hours of access to QA commercial platforms to investigate how the size of the problem and its complexity impact the accuracy of the solution and the time used to find a solution. Our results have found that the absolute error is between 0.12 and 0.55, and the time of the quantum processor unit is between 30 and 46 μs. Our results show that as the constraint density increases, the quality of the solution degrades. Therefore, more than the size of the problem, the complexity of the model plays a critical role, and practical applications should select formulations that minimize the constraint density.
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.
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.
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.
This study explores Quantum Annealing (QA) versus Classical Computing (CC) approaches in solving the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), using real-world logistics data from Siemens Advanta. By modeling the problem as a Service Network Design (SND) with binary variables and framing CVRPTW within a quantum mechanical paradigm suitable for QA, this approach leverages quantum annealing in a novel manner to tackle the complex optimization challenges inherent in the VRP. Contrasting it with the performance of the traditional branch and cut solver---a specific CC technique---this research unveils the prospective benefits and existing challenges of QA in complex optimization scenarios, thereby emphasizing the need for advancing quantum computing.
Quantum computing (QC) is expected to solve incredibly difficult problems, including finding optimal solutions to combinatorial optimization problems. However, to date, QC alone is still far to demonstrate this capability except on 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 QUBO, solved using D-Wave's Advantage system. Experiments investigate the impact of quantum routing frequency and starting solution methods. While different starting solution methods, including quantum-based and classical heuristics methods, 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 compared 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.