Advanced Quantum Annealing Approach to Vehicle Routing Problems with Time Windows

• URL: http://arxiv.org/abs/2503.24285v1
• Date: Mon, 31 Mar 2025 16:32:40 GMT
• Title: Advanced Quantum Annealing Approach to Vehicle Routing Problems with Time Windows
• Authors: James B. Holliday, Darren Blount, Eneko Osaba, Khoa Luu,
• Abstract summary: We focus on two NP-Hard problems, including the Traveling Salesman Problem with Time Windows and the Capacitated Vehicle Routing Problem with Time Windows.<n>We utilize D-Wave's Quantum Annealer and Constrained Quadratic Model (CQM) solver within a hybrid framework to solve these problems.<n>We demonstrate that while the CQM solver effectively minimizes route costs, it struggles to maintain time window feasibility as the problem size increases.
• Score: 7.819888986737809
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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%.

Related papers

• Quantum Annealing based Hybrid Strategies for Real Time Route Optimization [0.0]
  We propose a method to aid classical computers in solving problems faster while reducing complexity.<n>We employ two algorithms: Hybrid Two Step (H2S) and Hybrid Three Step (H3S)<n>Both algorithms produce promising results, both in terms of solution time and solution cost.
  arXiv  Detail & Related papers  (2024-11-21T14:45:40Z)
• Quantum Algorithms for Drone Mission Planning [0.0]
  Mission planning often involves optimising the use of ISR (Intelligence, Surveillance and Reconnaissance) assets in order to achieve a set of mission objectives. Finding such solutions is often an NP-Hard problem and cannot be solved efficiently on classical computers. We investigate near term quantum algorithms that have the potential to offer speed-ups against current classical methods.
  arXiv  Detail & Related papers  (2024-09-27T10:58:25Z)
• A Greedy Quantum Route-Generation Algorithm [0.0]
  We propose a greedy algorithm that generates routes by using information from all samples obtained from the quantum computer.<n>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.
  arXiv  Detail & Related papers  (2024-05-05T21:20:46Z)
• Optimal Chaining of Vehicle Plans with Time Windows [0.0]
  This work presents a new plan chaining formulation that considers delays as allowed by the time windows and a solution method for solving it. We list some practical applications and perform a demonstration for one of them: a new vehicle dispatching method for solving the static dial-a-ride problem.
  arXiv  Detail & Related papers  (2024-01-05T16:04:55Z)
• Solving the Team Orienteering Problem with Transformers [46.93254771681026]
  Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation. This paper presents a multi-agent route planning system capable of solving the Team Orienteering Problem in a very fast and accurate manner.
  arXiv  Detail & Related papers  (2023-11-30T16:10:35Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  This paper presents a novel form of the PSO methodology that uses the Roulette Wheel Method (RWPSO) Experiments using the Solomon VRPTW benchmark datasets on the RWPSO demonstrate that RWPSO is competitive with other state-of-the-art algorithms from the literature.
  arXiv  Detail & Related papers  (2023-06-04T09:18:02Z)
• Light Unbalanced Optimal Transport [69.18220206873772]
  We propose a novel theoretically-justified, lightweight, unbalanced EOT solver.<n>Our advancement consists of developing a novel view on the optimization of the UEOT problem yielding tractable and a non-minimax optimization objective.<n>We show that our solver provides a universal approximation of UEOT solutions and obtains its generalization bounds.
  arXiv  Detail & Related papers  (2023-03-14T15:44:40Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Analysis of Vehicle Routing Problem in Presence of Noisy Channels [0.0]
  Vehicle routing problem (VRP) is an NP-hard optimization problem. This work builds a basic VRP solution for 3 and 4 cities using variational quantum eigensolver on a variable ANSATZ.
  arXiv  Detail & Related papers  (2021-12-28T10:20:42Z)
• Adversarially Robust Learning for Security-Constrained Optimal Power Flow [55.816266355623085]
  We tackle the problem of N-k security-constrained optimal power flow (SCOPF) N-k SCOPF is a core problem for the operation of electrical grids. Inspired by methods in adversarially robust training, we frame N-k SCOPF as a minimax optimization problem.
  arXiv  Detail & Related papers  (2021-11-12T22:08:10Z)
• Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines [0.4724825031148411]
  We consider a practical railway dispatching problem: delay and conflict management on a single-track railway line. We introduce a quadratic unconstrained binary optimization (QUBO) model of the problem in question, compatible with the emerging quantum annealing technology. As a proof-of-concept, we solve selected real-life problems from the Polish railway network using D-Wave quantum annealers.
  arXiv  Detail & Related papers  (2020-10-16T08:17:57Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  We present a modified Cross-Entropy Method (CEM) that uses a masked auto-regressive neural network for modeling uniform distributions over the solution space. Our algorithm is able to express complicated solution spaces, thus allowing it to track a variety of different solution regions.
  arXiv  Detail & Related papers  (2020-02-17T20:21:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.