Advanced Quantum Annealing Approach to Vehicle Routing Problems with Time Windows
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912301868646400 |
|---|---|
| author | Holliday, James B. Blount, Darren Osaba, Eneko Luu, Khoa |
| author_facet | Holliday, James B. Blount, Darren Osaba, Eneko Luu, Khoa |
| contents | 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%. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_24285 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Advanced Quantum Annealing Approach to Vehicle Routing Problems with Time Windows Holliday, James B. Blount, Darren Osaba, Eneko Luu, Khoa Emerging Technologies Quantum Physics 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%. |
| title | Advanced Quantum Annealing Approach to Vehicle Routing Problems with Time Windows |
| topic | Emerging Technologies Quantum Physics |
| url | https://arxiv.org/abs/2503.24285 |