Formulating and Solving Routing Problems on Quantum Computers

The determination of vehicle routes fulfilling connectivity, time, and operational constraints is a well-studied combinatorial optimization problem. The NP-hard complexity of vehicle routing problems has fostered the adoption of tailored exact approaches, matheuristics, and metaheuristics on classic...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on quantum engineering 2021, Vol.2, p.1-17
Main Authors: Harwood, Stuart, Gambella, Claudio, Trenev, Dimitar, Simonetto, Andrea, Bernal Neira, David, Greenberg, Donny
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial analysis
Computers
Decision making
Heuristic methods
Mathematical model
Mathematical programming
Optimization
Quantum algorithm
Quantum computers
Quantum computing
Robustness (mathematics)
Route planning
Routing
variational algorithms
Vehicle routing
Windows (intervals)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The determination of vehicle routes fulfilling connectivity, time, and operational constraints is a well-studied combinatorial optimization problem. The NP-hard complexity of vehicle routing problems has fostered the adoption of tailored exact approaches, matheuristics, and metaheuristics on classical computing devices. The ongoing evolution of quantum computing hardware and the recent advances of quantum algorithms (i.e., VQE, QAOA, and ADMM) for mathematical programming make decision-making for routing problems an avenue of research worthwhile to be explored on quantum devices. In this article, we propose several mathematical formulations for inventory routing cast as vehicle routing with time windows and comment on their strengths and weaknesses. The optimization models are compared from a quantum computing perspective, specifically with metrics to evaluate the difficulty in solving the underlying quadratic unconstrained binary optimization problems. Finally, the solutions obtained on simulated quantum devices demonstrate the relative benefits of different algorithms and their robustness when put into practice.
ISSN:2689-1808
2689-1808
DOI:10.1109/TQE.2021.3049230