2023, issue 2, p. 23-31

Received 21.06.2023; Revised 11.07.2023; Accepted 25.07.2023

Published 28.07.2023; First Online 18.08.2023

https://doi.org/10.34229/2707-451X.23.2.3

Previous  |  FULL TEXT  |  Next

 

MSC 90C27, 68Q12

An Overview of Algorithms for Solving Vehicle Routing Problems in the Quantum-Classical Cloud

Leonid Hulianitskyi * ORCID ID favicon Big,   Vyacheslav Korolyov ORCID ID favicon Big,   Oleksandr Khodzinskyi ORCID ID favicon Big

V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv

* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.

 

Introduction. The hope of solving the problem of the avalanche-like growth of requirements for computing power, essential for solving complex routing problems and other problems of combinatorial optimization, relies on the latest quantum computers, in the development of which governments and corporations invest multi-billion investments.

The article examines modern routing algorithms and performs their analysis and verification, if the authors of the algorithm provided appropriate test programs.

The purpose of the article is to review the current state of development in the field of development of routing algorithms for hybrid quantum-classical clouds, analyze them and propose a classification of algorithms.

Results. Modern quantum computers (QCs) make it possible to find approximate solutions to some of mathematical problems faster than classical computers. The inaccuracy of the solutions obtained by the QC is a consequence of physical and technological limitations: calculation errors are caused by thermal noise, a small number of computational elements - qubits and connections between them, which requires the decomposition of the problem and the use of heuristic algorithms.

The analysis of approaches to the solution of optimization problems on QC allows us to single out: quantum response and variational search of eigenvalues based on quantum logic gates as the general directions of development of the vast majority of algorithms for solving routing problems. The considered algorithms reduce the vehicle routing problem to a quadratic unconstrained binary optimization problem, which is isomorphic to the Hamilton-Ising model. In this form, the problem is suitable for embedding in QC, which finds an approximate solution that has the best statistical reliability or corresponds to the quantum state with the lowest energy.

As a separate class, vehicle routing algorithms for classical computers that use quantum computing to accelerate problem solving can be distinguished. For example, neural networks that calculate weighting factors using QC or an ant algorithm that calculates a pheromone trail in a hybrid cloud. It should be mentioned the quantum-inspired algorithms, which are based on software tools for the simulation of QC and the corresponding libraries and allow creating an effective class of algorithms for solving problems of vehicle routing.

Conclusions. Combining hardware quantum annealing with a number of software tools for calculating optimization problems for classical computers in a hybrid quantum-classical cloud service allows to obtain advantages in speed and accuracy of some types of complex optimization problems of a commercial scale, in particular, routing vehicles, which is already bringing substantial profits to a number of corporations.

 

Keywords: vehicle routing problem, quantum computer, annealing, combinatorial optimization, traveling salesman problem, clustering, qubit.

 

Cite as: Hulianitskyi L., Korolyov V., Khodzinskyi O. An Overview of Algorithms for Solving Vehicle Routing Problems in the Quantum-Classical Cloud. Cybernetics and Computer Technologies. 2023. 2. P. 23–31. https://doi.org/10.34229/2707-451X.23.2.3

 

References

           1.     250+ Early Quantum Applications https://www.dwavesys.com/learn/featured-applications/ (accessed: 26.01.2023)

           2.     Goodlabs: How We Built a Real-Time Quantum Liquidity Optimizer for Wholesale Payments. https://www.dwavesys.com/events-section/events/goodlabs-how-we-built-a-real-time-quantum-liquidity-optimizer-for-wholesale-payments/ (accessed: 26.01.2023)

           3.     D-Wave and Mastercard Take Quantum Leap into Future of Financial Services https://www.dwavesys.com/company/newsroom/press-release/d-wave-and-mastercard-take-quantum-leap-into-future-of-financial-services/ (accessed: 26.01.2023)

           4.     Quantum Computing Application Sees Real World Success at Pier 300 at The Port of Los Angeles https://www.prnewswire.com/news-releases/quantum-computing-application-sees-real-world-success-at-pier-300-at-the-port-of-los-angeles-301455106.html (accessed: 26.01.2023)

           5.     Logistics Optimization: Port of Los Angeles https://www.dwavesys.com/events-section/events/logistics-optimization-port-of-los-angeles/?d=04-12-2022 (accessed: 26.01.2023)

           6.     Quantum molecule unfolding https://www.quantumcomputinglab.cineca.it/en/2021/08/25/quantum-molecule-unfolding-2/ (accessed: 26.01.2023)

           7.     Menten AI is Reimagining Biology with Quantum-Powered Protein Design https://www.dwavesys.com/media/exqjbloj/dwave_menten-ai_case_story_v10.pdf (accessed: 26.01.2023)

           8.     Menten AI Battles COVID-19 with Quantum Peptide Therapeutics https://www.dwavesys.com/media/kjof1cdh/dwave_menten-ai_case_story-2_v4.pdf (accessed: 26.01.2023)

           9.     D-Wave Customer Applications | Qubits 2020 https://www.youtube.com/watch?v=oBUaffN7KMY (accessed: 26.01.2023)

       10.     Osaba E., Villar-Rodriguez E., Oregi I., A Systematic Literature Review of Quantum Computing for Routing Problems. IEEE Access, 2022, Vol. 10, pp. 55805-55817. https://doi.org/10.1109/ACCESS.2022.3177790

       11.     Lucas A. Ising formulations of many NP problems. Front. Physics. 2014. Vol. 2.  https://doi.org/10.3389/fphy.2014.00005

       12.     Feld S., Roch C., Gabor T., Seidel C., Neukart F., Galter I., Mauerer W., Linnhoff-Popien C. A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer. Front. ICT 2019. Vol. 6. https://doi.org/10.3389/fict.2019.00013

       13.     Harikrishnakumar R., Nannapaneni S., Nguyen N.H., Steck J.E., Behrman E.C. A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem. 2020. http://arxiv.org/abs/2005.12478v2

       14.     Kato T. On the Adibatic Theorem of Quantum Mechanics. Journal of the Physical Society of Japan. 1950. Vol. 5. No. 6. P. 435–439. https://doi.org/10.1143/JPSJ.5.435

       15.     Asfaw A. Learn Quantum Computation using Qiskit. URL: https://qiskit.org/textbook/ch-applications/qaoa.html (accessed: 26.01.2023)

       16.     How to show mathematically the equivalency between Ising Model and QUBO? https://quantumcomputing.stackexchange.com/questions/21564/how-to-show-mathematically-the-equivalency-between-ising-model-and-qubo?rq=1 (accessed: 26.01.2023)

       17.     Toth P., Vigo D. Vehicle Routing: Problems, Methods, and Applications, Second Edition, MOS-SIAM Series on Optimization 18. SIAM, Philadelphia. 2014. P. 481. ISBN 1611973589

       18.     Golden B.L., Raghavan S., Wasil E.A. (eds.). The Vehicle Routing Problem: latest advances and new challenges. 2008. Vol. 43. Springer Science & Business Media. ISBN 0387777776. https://doi.org/10.1007/978-0-387-77778-8

       19.     Hulianitskyi L.F., Kotkova А.А. The classification problem of vehicle routing problems. Naukovyy visnyk Uzhhorodsʹkoho universytetu. Seriya "Matematyka i informatyka". 2020. 1 (36). C. 73–84. (in Ukrainian) https://doi.org/10.24144/2616-7700.2020.1(36).73-84

       20.     Golden B., Wang X., Wasil E. The Evolution of the Vehicle Routing Problem – A Survey of VRP Research and Practice from 2005 to 2022. The Evolution of the Vehicle Routing Problem. Synthesis Lectures on Operations Research and Applications, Springer, Cham. 2023. P. 1–64. https://doi.org/10.1007/978-3-031-18716-2_1

       21.     Horbulin V.P., Hulianytskyi L.F., Sergienko I.V. Optimization of UAV Team Routes in the Presence of Alternative and Dynamic Depots. Cybern Syst Anal. 2020. 56 (2). P. 195–203. https://doi.org/10.1007/s10559-020-00235-8

       22.     Borowski M. New Hybrid Quantum Annealing Algorithms for Solving Vehicle Routing Problem. In: Krzhizhanovskaya V. et al. (eds). Computational Science – ICCS 2020. ICCS 2020. Lecture Notes in Computer Science. 2020. Vol. 12142. P. 546–561. Springer, Cham. https://doi.org/10.1007/978-3-030-50433-5_42

       23.     Martin E., Hans-Peter K., Jörg S., Xiaowei Xu A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press. 1996. P. 226–231. CiteSeerX 10.1.1.121.9220. ISBN 1-57735-004-9.

       24.     Irie H., Wongpaisarnsin G., Terabe M., Miki A., Taguchi S. Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity. In: Feld S., Linnhoff-Popien C. (eds) Quantum Technology and Optimization Problems. QTOP 2019. Lecture Notes in Computer Science, 2019. Vol. 11413. P. 145–156. Springer, Cham. https://doi.org/10.1007/978-3-030-14082-3_13

       25.     Vehicle Routing Optimization https://qiskit.org/documentation/optimization/tutorials/07_examples_vehicle_routing .html (accessed: 26.01.2023)

       26.     Korolyov V.Yu., Khodzinskyi O.M. Solving combinatorial optimization problems on quantum computers. Cybernetics and Computer Technologies. 2020. 2. P. 5–13. (in Ukrainian) https://doi.org/10.34229/2707-451X.20.2.1

       27.     Sanches F., Weinberg S., Ide T., Kamiya K. Short quantum circuits in reinforcement learning policies for the vehicle routing problem. Phys. Rev. A. 2022. 105. 062403. https://doi.org/10.1103/PhysRevA.105.062403

       28.     Gabor T., Feld S., Safi H., Phan T., Linnhoff-Popien C. Insights on Training Neural Networks for QUBO Tasks. ICSEW'20: Proceedings of the IEEE/ACM 42nd International Conference on Software Engineering Workshops. 2020 P. 436–441 https://doi.org/10.1145/3387940.

       29.     Gonzalez-Bermejo, S.; Alonso-Linaje, G.; Atchade-Adelomou, P. GPS: A New TSP Formulation for Its Generalizations Type QUBO. Mathematics. 2022. 3 (10). 416. https://doi.org/10.3390/math10030416

       30.     QUBO formulation of TSP and VRP in terms of the minimum number of necessary variables https://github.com/pifparfait/GPS (accessed: 26.01.2023)

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  FULL TEXT  |  Next

 

 

            Archive

 

© Website and Design. 2019-2024,

V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine,

National Academy of Sciences of Ukraine.