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

A Greedy Quantum Route-Generation Algorithm

Jordan Makansi, Neira, David E. Bernal

Published May 5, 2024• 1 citation
arXivHTMLPDF

Abstract

Routing and scheduling problems with time windows have long been important optimization problems for logistics and planning. Many classical heuristics and exact methods exist for such problems. However, there are no satisfactory methods for generating routes using quantum computing (QC), for mainly two reasons: inequality constraints, and the trade-off of feasibility and solution quality. Inequality constraints are typically handled using slack variables; and feasible solutions are found by filtering samples. These challenges are amplified in the presence of noise inherent in QC. Here, we propose a greedy algorithm that generates routes by using information from all samples obtained from the quantum computer. By noticing the relationship between qubits in our formulation as a directed acyclic graph (DAG), we designed an algorithm that adaptively constructs a feasible solution. We prove its convergence to a feasible solution, and illustrate its efficacy by solving the Fleet Sizing Vehicle Routing Problem with Time Windows (FSVRPTW). Our computational results show that this method obtains a lower objective value than the current state-of-the-art annealing approaches, both classical and hybrid, for the same amount of time using D-Wave Hybrid Solvers. We also show its robustness to noise on D-Wave Advantage2 through computational results as compared to the filtering approach on DWaveSampler, even when the filtering approach is given a longer annealing time, and a larger sample size.

DOI
10.48550/arxiv.2405.03054

Related papers

Solving Vehicle Routing Problem Using Grover Adaptive Search Algorithm

Lu Liu, Ling Qian, Xing-Yu Wu +6 more

Intelligent Transportation Systems (ITS) occupy a pivotal position in the contemporary societal landscape, with one of their widespread applications being the vehicle routing problem, renowned for its classification as an NP-hard challenge. Traditional algorithms often require considerable time to address such problems or can only provide approximate solutions. Recent progress in quantum computation, however, offer a promising alternative by utilizing the parallelism inherent in quantum mechanics. In this study, we propose to solve the vehicle routing problem using the Grover adaptive algorithm. Compared to classical algorithms and existing quantum methods, our innovative algorithm achieves a quadratic speedup, with a time complexity of$O(K\sqrt{\frac{N}{M}})$. Additionally, it is applicable to a broader range of real-world scenarios, as it can directly handle linear inequality constraints without introducing slack variables. Notably, the algorithm operates independently of classical optimizers and gradient-based methods, thereby circumventing potential challenges such as the “barren plateaus” phenomenon. Experimental results from four instances demonstrate the feasibility and correctness of the proposed approach, highlighting its capability to handle inequality constraints easily.

IEEE Transactions on Intelligent Transportation Systems•May 1, 2025•16 citations

Advanced Quantum Annealing Approach to Vehicle Routing Problems with Time Windows

James B. Holliday, Darren Blount, Eneko Osaba +1 more

In this paper, we explore the potential for quantum annealing to solve realistic routing problems. We focus on two NP-Hard problems, including the Traveling Salesman Problem with Time Windows and the Capacitated Vehicle Routing Problem with Time Windows. We utilize D-Wave's Quantum Annealer and Constrained Quadratic Model (CQM) solver within a hybrid framework to solve these problems. We demonstrate that while the CQM solver effectively minimizes route costs, it struggles to maintain time window feasibility as the problem size increases. To address this limitation, we implement a heuristic method that fixes infeasible solutions through a series of swapping operations. Testing on benchmark instances shows our method achieves promising results with an average optimality gap of 3.86%.

arXiv:2503.24285•Mar 31, 2025•8 citations

Performance Analysis: Vehicle Routing using Quantum Annealing

Gautham Govind Anil, Anil Prabhakar

Vehicle routing refers to the generic problem of finding the optimal routes for a given fleet of vehicles with respect to a given measure of optimality and subject to a given set of constraints. Finding the exact solution to such a problem is NPhard. Hence, we often use heuristics to find feasible solutions. We use the DWave Hybrid solver to find a solution to the vehicle routing problem, and compare the time complexity of finding the solution as well as the quality of the solution found against a classical alternative, namely Gurobi v9.5. We observe that the quantum annealer shows better scaling with respect to size when compared to Gurobi.

International Conference on Trends in Quantum Computing and Emerging Business Technologies (TQCEBT)•Oct 13, 2022•0 citations

Solving Real-World Optimization Problems using Near-Term Quantum Computing with Applications in Vehicle Routing and Drone Delivery

Holliday, James Bradley

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.

Journal of the Arkansas Academy of Science•May 1, 2025•0 citations

A Flexible Hybrid Quantum Algorithm for Vehicle Routing

Arun Vellat Sadashivan, Robin Ajmera, Shantom Kumar Borah +2 more

The capacitated vehicle routing problem (CVRP) is an important problem for logistics optimization in supply chain. We propose a novel hybrid classical quantum algorithm that works by splitting the problem into a quantum travelling salesman problem (TSP) phase and a partitioning phase. In order to validate our methods, we run tests using D-Wave's Leap framework on random test cases, as well as a real-world data set from the retail domain. We run a comparison study against existing state of the art hybrid quantum-classical approaches for the CVRP, in addition to classical heuristic methods. Our method is shown to have the additional flexibility to handle fleet extension, and the solution quality is at least as good as the considered state of the art quantum hybrid algorithms. Further, we show that the algorithm can easily be modified for tackling other realistic vehicle routing variants.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•1 citation

Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes

Emanuele Casciaro, Mario De Simone, Stefano Martina +3 more

With the expansion of complex transport infrastructure, new paths for linking different destinations have emerged, allowing the definition of multiple routes. The introduction of new roads may also lead to disruptions in traffic flow. This problem can be generalized into a special case of VRP, which aims to find the optimal route for a fleet of vehicles within a network of destinations. Finding solutions to this problem requires an exponential number of operations, hindering the ability of exact solvers to deal with large instances, which must therefore be tackled using heuristics, often leading to suboptimal results. Quantum-based algorithms may allow us to find exact solutions in polynomial time with high probability, offering a potential future alternative to classical solvers and in this work, we focus on the QAOA. Our novel contributions are a parameter-initialization strategy that improves the convergence probability and the integration of the subtour constraints directly into the optimization without using additional qubits by employing an approximation of exponential equality constraints. We believe that our results pave the way for effectively solving instances of VRP using quantum-based solutions, leveraging the space-efficient problem encoding and our initialization strategy, which limits the effect of barren-plateau under random parameter initialization.

quant-pharXiv:2610.41120•Nov 2, 2026•0 citations
Routing and scheduling problems with time windows have long been important optimization problems for logistics and planning. Many classical heuristics and exact methods exist for such problems. However, there are no satisfactory methods for generating routes using quantum computing (QC), for mainly two reasons: inequality constraints, and the trade-off of feasibility and solution quality. Inequality constraints are typically handled using slack variables; and feasible solutions are found by filtering samples. These challenges are amplified in the presence of noise inherent in QC. Here, we propose a greedy algorithm that generates routes by using information from all samples obtained from the quantum computer. By noticing the relationship between qubits in our formulation as a directed acyclic graph (DAG), we designed an algorithm that adaptively constructs a feasible solution. We prove its convergence to a feasible solution, and illustrate its efficacy by solving the Fleet Sizing Vehicle Routing Problem with Time Windows (FSVRPTW). Our computational results show that this method obtains a lower objective value than the current state-of-the-art annealing approaches, both classical and hybrid, for the same amount of time using D-Wave Hybrid Solvers. We also show its robustness to noise on D-Wave Advantage2 through computational results as compared to the filtering approach on DWaveSampler, even when the filtering approach is given a longer annealing time, and a larger sample size.
Intelligent Transportation Systems (ITS) occupy a pivotal position in the contemporary societal landscape, with one of their widespread applications being the vehicle routing problem, renowned for its classification as an NP-hard challenge. Traditional algorithms often require considerable time to address such problems or can only provide approximate solutions. Recent progress in quantum computation, however, offer a promising alternative by utilizing the parallelism inherent in quantum mechanics. In this study, we propose to solve the vehicle routing problem using the Grover adaptive algorithm. Compared to classical algorithms and existing quantum methods, our innovative algorithm achieves a quadratic speedup, with a time complexity ofO(KNM)O(K\sqrt{\frac{N}{M}})O(KMN​​). Additionally, it is applicable to a broader range of real-world scenarios, as it can directly handle linear inequality constraints without introducing slack variables. Notably, the algorithm operates independently of classical optimizers and gradient-based methods, thereby circumventing potential challenges such as the “barren plateaus” phenomenon. Experimental results from four instances demonstrate the feasibility and correctness of the proposed approach, highlighting its capability to handle inequality constraints easily.
In this paper, we explore the potential for quantum annealing to solve realistic routing problems. We focus on two NP-Hard problems, including the Traveling Salesman Problem with Time Windows and the Capacitated Vehicle Routing Problem with Time Windows. We utilize D-Wave's Quantum Annealer and Constrained Quadratic Model (CQM) solver within a hybrid framework to solve these problems. We demonstrate that while the CQM solver effectively minimizes route costs, it struggles to maintain time window feasibility as the problem size increases. To address this limitation, we implement a heuristic method that fixes infeasible solutions through a series of swapping operations. Testing on benchmark instances shows our method achieves promising results with an average optimality gap of 3.86%.
Vehicle routing refers to the generic problem of finding the optimal routes for a given fleet of vehicles with respect to a given measure of optimality and subject to a given set of constraints. Finding the exact solution to such a problem is NPhard. Hence, we often use heuristics to find feasible solutions. We use the DWave Hybrid solver to find a solution to the vehicle routing problem, and compare the time complexity of finding the solution as well as the quality of the solution found against a classical alternative, namely Gurobi v9.5. We observe that the quantum annealer shows better scaling with respect to size when compared to Gurobi.
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.
The capacitated vehicle routing problem (CVRP) is an important problem for logistics optimization in supply chain. We propose a novel hybrid classical quantum algorithm that works by splitting the problem into a quantum travelling salesman problem (TSP) phase and a partitioning phase. In order to validate our methods, we run tests using D-Wave's Leap framework on random test cases, as well as a real-world data set from the retail domain. We run a comparison study against existing state of the art hybrid quantum-classical approaches for the CVRP, in addition to classical heuristic methods. Our method is shown to have the additional flexibility to handle fleet extension, and the solution quality is at least as good as the considered state of the art quantum hybrid algorithms. Further, we show that the algorithm can easily be modified for tackling other realistic vehicle routing variants.
With the expansion of complex transport infrastructure, new paths for linking different destinations have emerged, allowing the definition of multiple routes. The introduction of new roads may also lead to disruptions in traffic flow. This problem can be generalized into a special case of VRP, which aims to find the optimal route for a fleet of vehicles within a network of destinations. Finding solutions to this problem requires an exponential number of operations, hindering the ability of exact solvers to deal with large instances, which must therefore be tackled using heuristics, often leading to suboptimal results. Quantum-based algorithms may allow us to find exact solutions in polynomial time with high probability, offering a potential future alternative to classical solvers and in this work, we focus on the QAOA. Our novel contributions are a parameter-initialization strategy that improves the convergence probability and the integration of the subtour constraints directly into the optimization without using additional qubits by employing an approximation of exponential equality constraints. We believe that our results pave the way for effectively solving instances of VRP using quantum-based solutions, leveraging the space-efficient problem encoding and our initialization strategy, which limits the effect of barren-plateau under random parameter initialization.