Optymalizacja tras pojazdów z wykorzystaniem algorytmów kwantowych

• Autorzy: Rudnicka Zofia , Pręgowska Agnieszka

Identyfikatory

DOI

10.24423/9788365550590.ch7

Warianty tytułu

EN

The application of quantum computing to the optimization of vehicle routes

• Języki publikacji: PL

Abstrakty

PL

Problem marszrutyzacji (optymalizacji trasy) jest kwintesencją problemu optymalizacji kombinatorycznej w badaniach operacyjnych, który ma głębokie implikacje dla logistyki, zarządzania łańcuchem dostaw i systemów transportowych. Jego celem jest określenie najbardziej efektywnych tras dla floty pojazdów do obsługi grupy klientów, biorąc pod uwagę różnego rodzaju ograniczenie, takie jak pojemność pojazdu, okna czasu dostawy i długość trasy. Skuteczne rozwiązanie problemów marszruty ma kluczowe znaczenie dla minimalizacji kosztów operacyjnych, skrócenia czasu dostaw i łagodzenia wpływu na środowisko. Jednakże złożoność tego typu obliczeń rośnie wykładniczo wraz z liczbą klientów i pojazdów, co sprawia, że znalezienie optymalnych rozwiązań w rozsądnych ramach czasowych dla klasycznych algorytmów staje się wyzwaniem obliczeniowym. Z drugiej strony, obliczenia kwantowe, oferują nowatorski paradygmat rozwiązywania złożonych problemów optymalizacyjnych, takich jak problem marszrutyzacji. W artykule zbadano zastosowanie algorytmów kwantowych do optymalizacji tras pojazdów, koncentrując się na ich potencjale w zakresie przezwyciężania ograniczeń klasycznych metod w obsłudze eksplozji kombinatorycznej charakterystycznej dla problemów marszrutyzacji. Zaproponowano podejście hybrydowe, łączące algorytm przybliżonej optymalizacji kwantowej z algorytmem optymalizacji za pomocą roju cząstek. Analizowano zagadnienie związane z wyznaczeniem optymalnych tras pojazdów, które miały obsłużyć 250 klientów. W implementacji kwantowego algorytmu optymalizacyjnego wykorzystano łącznie 251 kubitów. Uzyskane wyniki pokazują, że przy wykorzystaniu metod hybrydowych można skutecznie planować trasy pojazdów.

EN

The vehicle routing problem (VRP) is a quintessential combinatorial optimization problem in operations research that has profound implications for logistics, supply chain management, and transportation systems. Its goal is to determine the most efficient routes for a fleet of vehicles to serve a group of customers, considering various constraints such as vehicle capacity, delivery time windows, and route length. Effectively solving VRP is crucial to minimizing operational costs, reducing delivery times, and mitigating environmental impacts. However, the complexity of this type of computation increases exponentially with the number of customers and vehicles, which makes finding optimal solutions within a reasonable time frame for classical algorithms a computational challenge. On the other hand, quantum computing (QC) offers a novel paradigm for solving complex optimization problems, such as the routing problem. In this paper, the QC application for vehicle route optimization, with a special emphasis on their potential to overcome the limitations of classical methods in handling the combinatorial explosion VRP characteristic has been studied. A hybrid approach was proposed combining an approximate quantum optimization algorithm with a particle swarm optimization algorithm. The problem of determining optimal vehicle routes to serve 250 customers was analyzed. A total of 251 qubits were used to implement the quantum optimization algorithm. The results obtained show that vehicle routes can be effectively planned using hybrid methods.

Słowa kluczowe

PL

obliczenia kwantowe; problem wyznaczania tras pojazdów; algorytm przybliżonej optymalizacji kwantowej

EN

quantum computing; vehicle routing problem; quantum approximate optimization algorithm

• Wydawca: Instytut Podstawowych Problemów Techniki PAN
• Czasopismo: IPPT Reports on Fundamental Technological Research
• Rocznik: 2024
• Tom: nr 2
• Strony: 97--128
• Opis fizyczny: Bibliogr. 24 poz., rys., tab.

Twórcy

autor

Rudnicka Zofia

• Instytut Podstawowych Problemów Techniki Polskiej Akademii Nauk, Warszawa

• https://orcid.org/0000-0001-9073-7644

autor

Pręgowska Agnieszka

• Instytut Podstawowych Problemów Techniki Polskiej Akademii Nauk, Warszawa

• https://orcid.org/0000-0001-9163-9931

Bibliografia

• 1. Y. Zheng, L. Gao, W. Li, Vehicle Routing and scheduling of flex-route transit under a dynamic operating environment, Discrete Dynamics in Nature and Society, 2021, 1–10, 2021, doi: https://doi.org/10.1155/2021/6669567.
• 2. N. Xie, X. Lee, D. Cai, Y. Saito, N. Asai, H.C. Lau, A feasibility-preserved quantum approximate solver for the capacitated vehicle routing problem, Quantum Information Processing, 23, 291, 2024, doi: https://doi.org/10.1007/s11128-024-04497-5.
• 3. A. Montanaro, Quantum algorithms: an overview, npj Quantum Information, 2, 1, 15023, 2016, doi: https://doi.org/10.1038/npjqi.2015.23.
• 4. T. Monz et al., Realization of a scalable Shor algorithm, Science, 351, 6277, 1068–1070, 2016, doi: https://doi.org/10.1126/science.aad9480.
• 5. D. Qiu, L. Luo, L. Xiao, Distributed Grover’s algorithm, Theoretical Computer Science, 993, 114461, 2024, doi: https://doi.org/10.1016/j.tcs.2024.114461.
• 6. K. Blekos et al., A review on Quantum Approximate Optimization Algorithm and its variants, Physics Reports, 1068, 1–66, 2024, doi: https://doi.org/10.1016/j.physrep.2024.03.002.
• 7. B. Tasseff et al., On the emerging potential of quantum annealing hardware for combinatorial optimization, Journal of Heuristics, 30, 5–6, 325–358, 2024, doi: https://doi.org/10.1007/s10732-024-09530-5.
• 8. J. Hosoda, S.J. Maher, Y. Shinano, J.C. Villumsen, A parallel branch-and-bound heuristic for the integrated long-haul and local vehicle routing problem on an adaptive transportation network, Computers & Operations Research, 165, 106570, 2024, doi: https://doi.org/10.1016/j.cor.2024.106570.
• 9. J. Zhao, M. Poon, V.Y.F. Tan, Z. Zhang, A hybrid genetic search and dynamic programming-based split algorithm for the multi-trip time-dependent vehicle routing problem, European Journal of Operational Research, 317, 3, 921–935, 2024, doi: https://doi.org/10.1016/j.ejor.2024.04.011.
• 10. X. Ren, A. Froger, O. Jabali, G. Liang, A competitive heuristic algorithm for vehicle routing problems with drones, European Journal of Operational Research, 318, 2,
• 11. E. Osaba, E. Villar-Rodriguez, I. Oregi, A systematic literature review of quantum computing for routing problems, IEEE Access, 10, 55805–55817, 2022, doi: https://doi.org/10.1109/ACCESS.2022.3177790.
• 12. J. Holliday, B. Morgan, H. Churchill, K. Luu, Hybrid quantum tabu search for solving the vehicle routing problem, arXiv, 2024, doi: https://doi.org/10.48550/arXiv.2404.13203.
• 13. D. Eichhorn, M. Schweikart, N. Poser, F. Fiand, B. Poggel, J.M. Lorenz, Hybrid meta-solving for practical quantum computing, arXiv, 2024, doi: https://doi.org/10.48550/arXiv.2405.09115.
• 14. S. Harwood, C. Gambella, D. Trenev, A. Simonetto, D. Bernal Neira, D. Greenberg, Formulating and solving routing problems on quantum computers, IEEE Transactions on Quantum Engineering, 2, 1–17, 2021, doi: https://doi.org/10.1109/TQE.2021.3049230.
• 15. N. Mohanty, B.K. Behera, C. Ferrie, Solving the vehicle routing problem via quantum support vector machines, Quantum Machine Intelligence, 6, 34, 2024, doi: https://doi.org/10.1007/s42484-024-00161-4.
• 16. K. Blekos et al., A review on Quantum Approximate Optimization Algorithm and its variants, Physics Reports, 1068, 1–66, 2024, doi: https://doi.org/10.1016/j.physrep.2024.03.002.
• 17. V. Akshay, D. Rabinovich, E. Campos, J. Biamonte, Parameter concentrations in quantum approximate optimization, Physical Review A, 104, L010401, 2021, doi: https://doi.org/10.1103/PhysRevA.104.L010401.
• 18. L. Zhou, S.-T. Wang, S. Choi, H. Pichler, M.D. Lukin, Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices, Physical Review X, 10, 021067, 2020, doi: https://doi.org/10.1103/PhysRevX.10.021067.
• 19. D. Wang, D. Tan, L. Liu, Particle swarm optimization algorithm: An overview, Soft Computing, 22, 387–408, 2018, doi: https://doi.org/10.1007/s00500-016-2474-6.
• 20. T.M. Shami, A.A. El-Saleh, M. Alswaitti, Q. Al-Tashi, M.A. Summakieh, S. Mirjalili, Particle swarm optimization: A comprehensive survey, IEEE Access, 10, 10031– 10061, 2022, doi: https://doi.org/10.1109/ACCESS.2022.3142859.
• 21. D.P. Kingma, J. Ba, Adam: A method for stochastic optimization, arXiv, 2014, doi: https://doi.org/10.48550/arXiv.1412.6980.
• 22. Quantum Programming Software – PennyLane, https://pennylane.ai/.
• 23. SciPy – Fundamental algorithms for scientific computing in Python, https://scipy.org/.
• 24. C. Roch, S. Langer, The capacitated vehicle routing problem, Digitale Welt, 3, 2, 30–33, 2019, doi: https://doi.org/10.1007/s42354-019-0165-z.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).