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
An Overview of Algorithms for Solving Vehicle Routing Problems in the Quantum-Classical Cloud
Leonid Hulianitskyi *
, Vyacheslav Korolyov , Oleksandr Khodzinskyi
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)