Open Access

ARTICLE

IQAOA for Two Routing Problems: A Methodological Contribution with Application to TSP and VRP

Eric Bourreau¹, Gérard Fleury², Philippe Lacomme^2,*

1 LIRMM (Laboratoire d’informatique, de robotique et de microélectronique de Montpellier), CNRS (Centre National de la Recherche Scientifique), Université de Montpellier, Montpellier, 34095, France
2 Université Clermont Auvergne, Clermont Auvergne INP, UMR 6158 LIMOS (Laboratoire d’Informatique de Modélisation et d’Optimisation des Systèmes), Aubière, 63178, France

* Corresponding Author: Philippe Lacomme. Email:

Journal of Quantum Computing 2024, 6, 25-51. https://doi.org/10.32604/jqc.2024.048792

Received 18 December 2023; Accepted 19 July 2024; Issue published 25 October 2024

Abstract

The paper presents a novel quantum method for addressing two fundamental routing problems: the Traveling Salesman Problem (TSP) and the Vehicle Routing Problem (VRP), both central to routing challenges. The proposed method, named the Indirect Quantum Approximate Optimization Algorithm (IQAOA), leverages an indirect solution representation using ranking. Our contribution focuses on two main areas: 1) the indirect representation of solutions, and 2) the integration of this representation into an extended version of QAOA, called IQAOA. This approach offers an alternative to QAOA and includes the following components: 1) a quantum parameterized circuit designed to simulate string vectors on a quantum processor, 2) a classical meta-optimization method executed on a classical computer, and 3) the computation of the average cost for each string vector, achieved through a well-established algorithm from the operations research community tailored to the specific problem. IQAOA provides an efficient means to address quantum optimization problems by combining quantum and classical computation methods. Its primary advantage lies in deriving a quantum circuit that requires significantly fewer gates, making it suitable for execution on current noisy quantum computing platforms. Through numerical experiments employing IQAOA, we successfully solved instances of the 10-customer Traveling Salesman Problem (TSP) using the IBM simulator. To our knowledge, this is the largest application of a QAOA-based approach to solving the TSP. Additionally, IQAOA enables the resolution of the Vehicle Routing Problem (VRP) by leveraging the Split algorithm, which transforms a TSP permutation into a corresponding VRP solution.

---

Keywords

---