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

International Conference on Agents and Artificial Intelligence (ICAART)

Solving the Dial-a-Ride Problem with Time Windows Using Quantum Annealing and Quantum-Guided Cluster Algorithms

Peter Eder, David Zambrano Manrique, Christian B. Mendl, Sarah Braun

Published Jan 1, 2026• 0 citations
Publisher

Abstract

The Dial-a-Ride Problem (DARP) is a variant of the NP-hard vehicle routing problem with significant practical relevance in modern transportation systems. In this work, we introduce a novel Quadratic Unconstrained Binary Optimization formulation of the DARP that explicitly incorporates routing and time window constraints without requiring continuous variables, thereby making it compatible with quantum optimization approaches. We employ quantum annealing on D-Wave hardware to solve the resulting instances. As the hardware alone cannot identify the ground states for instances with 196 qubits, we enhance the obtained solutions using the Quantum-Guided Cluster Algorithm, a post-processing heuristic that leverages two-point correlations between sampled states. Our numerical results demonstrate that the proposed hybrid quantum-classical framework yields close-to-optimal solutions quickly for instances of up to 14 requests.

DOI
10.5220/0014440600004052

Related papers

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•0 citations

QUBO Formulation of the Pickup and Delivery Problem with Time Windows for Quantum Annealing

Cosmin Ștefan Curuliuc, Florin Leon

This paper addresses the Pickup and Delivery Problem with Time Windows (PDPTW), an NP-hard combinatorial optimization problem with major practical relevance in logistics and transportation. The study focuses on a quadratic unconstrained binary optimization (QUBO) formulation for quantum annealing and benchmarks it against two classical optimization paradigms. A modular Python framework is developed that encodes PDPTW in three ways: a mixed-integer linear programming (MILP) model that serves as an exact reference, a genetic algorithm (GA) metaheuristic, and a QUBO model that is compatible with quantum annealers. The framework supports test scenarios with increasing structural complexity, with both feasible and intentionally infeasible instances. An additional contribution is the conceptual design and preliminary analysis of an automatic-penalty weight-tuning scheme for the QUBO model. Experimental results show that the proposed QUBO formulation can produce high-quality solutions for simpler PDPTW instances, but its performance strongly depends on the careful calibration of penalty weights. MILP provides optimal baselines on small instances but becomes intractable as problem size grows. The GA scales to the largest scenario and finds feasible solutions of reasonable quality, but they are not necessarily optimal. The evaluation also includes a large number of problem instances and runs on IBM Quantum hardware using the Quantum Approximate Optimization Algorithm (QAOA).

Applied Sciences•Feb 8, 2026•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

A Hybrid Quantum-Classical Approach to the Electric Mobility Problem

Margarita Veshchezerova, Mikhail Somov, D. Bertsche +4 more

We suggest a hybrid quantum-classical routine for the NP-hard Electric Vehicle Fleet Charging and Allocation Problem. The original formulation is a Mixed Integer Linear Program with continuous variables and inequality constraints. To separate inequality constraints that are difficult for quantum routines we use a decomposition in master and pricing problems: the former targets the assignment of vehicles to reservations and the latter suggests vehicle exploitation plans that respect the battery state-of-charge constraints. The master problem is equivalent to the search for an optimal set partition. In our hybrid scheme, the master problem is reformulated in a quadratic unconstrained binary optimization problem which can be solved with quantum annealing on the DWave Advantage system. On large instances, we benchmark the performance of the decomposition technique with classical and quantum-inspired metaheuristics: simulated annealing, tabu search, and vector annealing by NEC. The numerical results with purely classical solvers are comparable to the solutions from the traditional mixed integer linear programming approaches in terms of solution quality while being faster. In addition, it scales better to larger instances. The major advantage of the proposed approach is that it enables quantum-based methods for this realistic problem with many inequality constraints. We show this by initial studies on DWave hardware where optimal solutions can be found for small instances.

arXiv:2310.02760•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•9 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

Quantum annealing for vehicle routing problem with weighted segment

Toufan Diansyah Tambunan, Andriyan Bayu Suksmono, Ian Joseph Matheus Edward +1 more

Quantum annealing technologies aim to solve computational optimization and sampling problems. QPU (Quantum Processing Unit) machines such as the D-Wave system use the QUBO (Quadratic Unconstrained Binary Optimization) formula to define model optimization problems for quantum annealing. This machine uses quantum effects to speed up computing time better than classical computers. We propose a vehicle routing problem that can be formulated in the QUBO model as a combinatorial problem, which gives the possible route solutions increases exponentially. The solution aims to optimize the vehicle's journey to reach a destination. The study presents a QUBO formulation to solve traffic congestion problems on certain roads. The resulting route selection by optimizing the distribution of the flow of alternative road vehicles based on the weighting of road segments. Constraints formulated as a condition for the level of road density. The road weight parameter influences the cost function for each road choice. The simulations on the D-Wave quantum annealer show optimal results on the route deployment of several vehicles. So that each vehicle will be able to go through different road options and reduce road congestion accurately. This solution provides an opportunity to develop QUBO modeling for more complex vehicle routing problems for road congestion.

arXiv:2203.13469•AIP conference proceedings•Jan 1, 2023•19 citations
The Dial-a-Ride Problem (DARP) is a variant of the NP-hard vehicle routing problem with significant practical relevance in modern transportation systems. In this work, we introduce a novel Quadratic Unconstrained Binary Optimization formulation of the DARP that explicitly incorporates routing and time window constraints without requiring continuous variables, thereby making it compatible with quantum optimization approaches. We employ quantum annealing on D-Wave hardware to solve the resulting instances. As the hardware alone cannot identify the ground states for instances with 196 qubits, we enhance the obtained solutions using the Quantum-Guided Cluster Algorithm, a post-processing heuristic that leverages two-point correlations between sampled states. Our numerical results demonstrate that the proposed hybrid quantum-classical framework yields close-to-optimal solutions quickly for instances of up to 14 requests.
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%.
This paper addresses the Pickup and Delivery Problem with Time Windows (PDPTW), an NP-hard combinatorial optimization problem with major practical relevance in logistics and transportation. The study focuses on a quadratic unconstrained binary optimization (QUBO) formulation for quantum annealing and benchmarks it against two classical optimization paradigms. A modular Python framework is developed that encodes PDPTW in three ways: a mixed-integer linear programming (MILP) model that serves as an exact reference, a genetic algorithm (GA) metaheuristic, and a QUBO model that is compatible with quantum annealers. The framework supports test scenarios with increasing structural complexity, with both feasible and intentionally infeasible instances. An additional contribution is the conceptual design and preliminary analysis of an automatic-penalty weight-tuning scheme for the QUBO model. Experimental results show that the proposed QUBO formulation can produce high-quality solutions for simpler PDPTW instances, but its performance strongly depends on the careful calibration of penalty weights. MILP provides optimal baselines on small instances but becomes intractable as problem size grows. The GA scales to the largest scenario and finds feasible solutions of reasonable quality, but they are not necessarily optimal. The evaluation also includes a large number of problem instances and runs on IBM Quantum hardware using the Quantum Approximate Optimization Algorithm (QAOA).
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.
We suggest a hybrid quantum-classical routine for the NP-hard Electric Vehicle Fleet Charging and Allocation Problem. The original formulation is a Mixed Integer Linear Program with continuous variables and inequality constraints. To separate inequality constraints that are difficult for quantum routines we use a decomposition in master and pricing problems: the former targets the assignment of vehicles to reservations and the latter suggests vehicle exploitation plans that respect the battery state-of-charge constraints. The master problem is equivalent to the search for an optimal set partition. In our hybrid scheme, the master problem is reformulated in a quadratic unconstrained binary optimization problem which can be solved with quantum annealing on the DWave Advantage system. On large instances, we benchmark the performance of the decomposition technique with classical and quantum-inspired metaheuristics: simulated annealing, tabu search, and vector annealing by NEC. The numerical results with purely classical solvers are comparable to the solutions from the traditional mixed integer linear programming approaches in terms of solution quality while being faster. In addition, it scales better to larger instances. The major advantage of the proposed approach is that it enables quantum-based methods for this realistic problem with many inequality constraints. We show this by initial studies on DWave hardware where optimal solutions can be found for small instances.
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.
Quantum annealing technologies aim to solve computational optimization and sampling problems. QPU (Quantum Processing Unit) machines such as the D-Wave system use the QUBO (Quadratic Unconstrained Binary Optimization) formula to define model optimization problems for quantum annealing. This machine uses quantum effects to speed up computing time better than classical computers. We propose a vehicle routing problem that can be formulated in the QUBO model as a combinatorial problem, which gives the possible route solutions increases exponentially. The solution aims to optimize the vehicle's journey to reach a destination. The study presents a QUBO formulation to solve traffic congestion problems on certain roads. The resulting route selection by optimizing the distribution of the flow of alternative road vehicles based on the weighting of road segments. Constraints formulated as a condition for the level of road density. The road weight parameter influences the cost function for each road choice. The simulations on the D-Wave quantum annealer show optimal results on the route deployment of several vehicles. So that each vehicle will be able to go through different road options and reduce road congestion accurately. This solution provides an opportunity to develop QUBO modeling for more complex vehicle routing problems for road congestion.