2025/03/31 by James B. Holliday, Darren Blount, Holliday, James B. +5 · 5 citations
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2503.24285
openalex publication_date 2025/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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%.