Open Access iconOpen Access

ARTICLE

crossmark

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

Eric Bourreau1, Gérard Fleury2, Philippe Lacomme2,*

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: email

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

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


Cite This Article

APA Style
Bourreau, E., Fleury, G., Lacomme, P. (2024). IQAOA for two routing problems: A methodological contribution with application to TSP and VRP. Journal of Quantum Computing, 6(1), 25-51. https://doi.org/10.32604/jqc.2024.048792
Vancouver Style
Bourreau E, Fleury G, Lacomme P. IQAOA for two routing problems: A methodological contribution with application to TSP and VRP. J Quantum Comput . 2024;6(1):25-51 https://doi.org/10.32604/jqc.2024.048792
IEEE Style
E. Bourreau, G. Fleury, and P. Lacomme, “IQAOA for Two Routing Problems: A Methodological Contribution with Application to TSP and VRP,” J. Quantum Comput. , vol. 6, no. 1, pp. 25-51, 2024. https://doi.org/10.32604/jqc.2024.048792



cc Copyright © 2024 The Author(s). Published by Tech Science Press.
This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 152

    View

  • 72

    Download

  • 0

    Like

Share Link