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:2005.12478

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

Harikrishnakumar, Ramkumar, Saideep Nannapaneni, Nguyen, Nam H., James E. Steck, Elizabeth Behrman

Published May 26, 2020• 16 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2005.12478

Related papers

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

Utilizing Quantum Annealing to Address Vehicle Routing Challenges in Cold Chain Logistics

Wing Ho Elle, G.T.S. Ho, Valerie Tang +1 more

In the current competitive industrial environment, the study of NP-hard issues is becoming more and more significant. In logistics, the Vehicle Routing Problem (VRP) is one of the popular challenges, especially in cold chain logistics, which requires the management of perishable goods. This problem involves identifying the optimal paths for vehicles responsible for transporting goods to different locations. Due to its combinatorial nature and the complexity of finding optimal solutions, it is identified as an NP-hard problem that requires an unreasonable time frame to solve. Recently, quantum computing has proven to be a promising approach for addressing some of the complex challenges. Among quantum methodologies, quantum annealing (QA) has demonstrated the potential to accelerate computation times in solving optimization problems. By leveraging the principles of quantum tunneling and superposition, QA can explore solution spaces more efficiently. Therefore, this study explores the application of QA to address VRP in cold chain logistics, aiming to develop solutions that minimize travel distances during deliveries. The case study demonstrates that QA can achieve, on average, at least 85% of optimal performance while providing approximately 95% faster run times compared to classical genetic algorithms (GA). This contributes to greater efficiency in cold chain logistics operations.

International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence (ISMSI)•Apr 26, 2025•0 citations

An introduction to quantum annealing and review of QUBO models for Vehicle Routing Problem

Michał Jaroszczuk

Vehicle Routing Problem is a well-known optimization issue, which has many extensions resulting from practical appliances. The problem is NP-hard, therefore it may be impossible to find an optimal solution for big instances, with traditional computation methods. Recent development of quantum technology, may be a response for this challenge, which however requires a different formulation of the model. The problem is then modeled using Quadratic Unconstrained Binary Optimization (QUBO) equations. Such model can be run using quantum annealers (QA), designed specifically for optimization purposes. This paper is a systematic survey of Vehicle Routing Problem models that are formulated using QUBO, to be solved on quantum computers. The main goal of the paper is to check research gaps in this subject, compare and explain different approaches of modeling various problem extensions with QUBO. The results obtained in reviewed papers will be presented and analyzed. Moreover, the theoretical basis for quantum computation will be presented, with focus on D-Wave company solutions.

IEEE International Symposium on Computational Intelligence and Informatics (CINTI)•Nov 18, 2025•1 citation

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 (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.

arXiv:2309.05564•Sep 11, 2023•2 citations

An Intelligent and Sustainable Green Supply Chain Optimization of Transportation Systems Using Classical and Quantum-Powered Computing

Muhammad Makama Mahmudur Rahman Ohee, Hafiz Md. Hasan Babu

Transportation strategists increasingly handle heterogeneous fleets under tight service levels, fluctuating costs, and stated environmental targets. This paper addresses the operational Heterogeneous Vehicle Routing Problem (HVRP) with a practical, mathematically light decision framework that treats sustainability as the main goal of the design. We introduce a Quantum-Inspired Supply Chain and Logistics Optimization Algorithm (QISCLOA), solver-independent HVRP approach for transportation system. Our proposed framework builds a curated, capacity-feasible, and diversified route pool using multi-strategy generation. In our $16\times 16$ HVRP benchmarks, our proposed algorithm reduces elapsed time by up to 98.6% compared with strong classical formulations, while matching classical distance quality and delivering higher load utilization (95–99%) under the same feasibility constraints. Compared with existing classical system, our proposed system preserves full feasibility and comparable distance, shows clear distance-per-demand gains in symmetric unit-demand cases, and attains near-zero solve time on identical Binary Quadratic Models (BQM), evidencing orders-of-magnitude speedups. The proposed model further introduces a load–carbon emission correlation with speed, road-condition, and congestion factors, and the proposed Quantum Annealing (QA) and existing Quantum Approximate Optimization Algorithm (QAOA) comparison demonstrates competitive solution quality, solver-dependent efficiency, and full logical hardware compatibility. Additionally, we extend the formulation to a multi-depot setting with depot availability, dispatch-capacity, time-window, and Electric Vehicle (EV) charging constraints, and validate it on 21 Multi-Depot Vehicle Routing Problem (MDVRP) benchmark instances to demonstrate scalable multi-depot route selection, while a reduced comparison confirms competitive solution quality and solver-dependent efficiency, with existing QAOA improving overall route distance by 0.63% and proposed QA achieving a 9.14% overall runtime advantage. In multitasking Capacitated Vehicle Routing Problem (CVRP) benchmarks used in explicit evolutionary multitasking studies, our approach achieves lower routing cost for both best and average results with a win rate of 81.48%, indicating a lower emission of CO2. Empirically, our proposed method outperforms competitive state-of-the-art approaches in our evaluation metrics while maintaining core feasibility.

IEEE Open Journal of Intelligent Transportation Systems•Jan 1, 2026•0 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
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.
In the current competitive industrial environment, the study of NP-hard issues is becoming more and more significant. In logistics, the Vehicle Routing Problem (VRP) is one of the popular challenges, especially in cold chain logistics, which requires the management of perishable goods. This problem involves identifying the optimal paths for vehicles responsible for transporting goods to different locations. Due to its combinatorial nature and the complexity of finding optimal solutions, it is identified as an NP-hard problem that requires an unreasonable time frame to solve. Recently, quantum computing has proven to be a promising approach for addressing some of the complex challenges. Among quantum methodologies, quantum annealing (QA) has demonstrated the potential to accelerate computation times in solving optimization problems. By leveraging the principles of quantum tunneling and superposition, QA can explore solution spaces more efficiently. Therefore, this study explores the application of QA to address VRP in cold chain logistics, aiming to develop solutions that minimize travel distances during deliveries. The case study demonstrates that QA can achieve, on average, at least 85% of optimal performance while providing approximately 95% faster run times compared to classical genetic algorithms (GA). This contributes to greater efficiency in cold chain logistics operations.
Vehicle Routing Problem is a well-known optimization issue, which has many extensions resulting from practical appliances. The problem is NP-hard, therefore it may be impossible to find an optimal solution for big instances, with traditional computation methods. Recent development of quantum technology, may be a response for this challenge, which however requires a different formulation of the model. The problem is then modeled using Quadratic Unconstrained Binary Optimization (QUBO) equations. Such model can be run using quantum annealers (QA), designed specifically for optimization purposes. This paper is a systematic survey of Vehicle Routing Problem models that are formulated using QUBO, to be solved on quantum computers. The main goal of the paper is to check research gaps in this subject, compare and explain different approaches of modeling various problem extensions with QUBO. The results obtained in reviewed papers will be presented and analyzed. Moreover, the theoretical basis for quantum computation will be presented, with focus on D-Wave company solutions.
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.
Transportation strategists increasingly handle heterogeneous fleets under tight service levels, fluctuating costs, and stated environmental targets. This paper addresses the operational Heterogeneous Vehicle Routing Problem (HVRP) with a practical, mathematically light decision framework that treats sustainability as the main goal of the design. We introduce a Quantum-Inspired Supply Chain and Logistics Optimization Algorithm (QISCLOA), solver-independent HVRP approach for transportation system. Our proposed framework builds a curated, capacity-feasible, and diversified route pool using multi-strategy generation. In our 16×1616\times 1616×16 HVRP benchmarks, our proposed algorithm reduces elapsed time by up to 98.6% compared with strong classical formulations, while matching classical distance quality and delivering higher load utilization (95–99%) under the same feasibility constraints. Compared with existing classical system, our proposed system preserves full feasibility and comparable distance, shows clear distance-per-demand gains in symmetric unit-demand cases, and attains near-zero solve time on identical Binary Quadratic Models (BQM), evidencing orders-of-magnitude speedups. The proposed model further introduces a load–carbon emission correlation with speed, road-condition, and congestion factors, and the proposed Quantum Annealing (QA) and existing Quantum Approximate Optimization Algorithm (QAOA) comparison demonstrates competitive solution quality, solver-dependent efficiency, and full logical hardware compatibility. Additionally, we extend the formulation to a multi-depot setting with depot availability, dispatch-capacity, time-window, and Electric Vehicle (EV) charging constraints, and validate it on 21 Multi-Depot Vehicle Routing Problem (MDVRP) benchmark instances to demonstrate scalable multi-depot route selection, while a reduced comparison confirms competitive solution quality and solver-dependent efficiency, with existing QAOA improving overall route distance by 0.63% and proposed QA achieving a 9.14% overall runtime advantage. In multitasking Capacitated Vehicle Routing Problem (CVRP) benchmarks used in explicit evolutionary multitasking studies, our approach achieves lower routing cost for both best and average results with a win rate of 81.48%, indicating a lower emission of CO2. Empirically, our proposed method outperforms competitive state-of-the-art approaches in our evaluation metrics while maintaining core feasibility.
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.