2023, випуск 2, c. 23-31
Одержано 21.06.2023; Виправлено 11.07.2023; Прийнято 25.07.2023
Надруковано 28.07.2023; Вперше Online 18.08.2023
https://doi.org/10.34229/2707-451X.23.2.3
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Огляд алгоритмів розв’язування задач маршрутизації у квантово-класичній хмарі
Л.Ф. Гуляницький * 
, В.Ю. Корольов , О.М. Ходзінський
Інститут кібернетики імені В.М. Глушкова НАН України, Київ
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Сподівання на вирішення проблеми лавиноподібного зростання вимог до обчислювальних потужностей, потрібних для розв’язування складних задач маршрутизації, та інших задач комбінаторної оптимізації, покладається на новітні квантові обчислювачі у розробку яких урядами і корпораціями вкладаються багатомільярдні інвестиції.
У статті розглянуто сучасні алгоритмів маршрутизації та виконано їх аналіз і верифікацію, якщо автори алгоритму надали відповідні тестові програми.
Мета роботи – розглянути сучасний стан розвитку сфери розробки алгоритмів маршрутизації для гібридних квантово-класичних хмар, проаналізувати їх та запропонувати класифікацію алгоритмів.
Результати. Сучасні квантові комп’ютери (КвК) дозволяють швидше знаходити наближені розв’язки низки математичних задач порівняно з класичними комп’ютерами. Неточність розв’язків отриманих на КвК є наслідком фізичних і технологічних обмежень: помилки обчислень викликані тепловими шумами, мала кількість обчислювальних елементів – кубітів і зв’язків між ними, що потребує виконання декомпозиції задачі та застосування евристичних алгоритмів.
Аналіз підходів до розв’язку оптимізаційних задач на КвК дозволяє виділити: квантовий відпал та варіаційний пошук власних значень на базі квантових логічних вентилів як загальні напрямки розробки переважної більшості алгоритмів розв’язування задач маршрутизації. Розглянуті алгоритми зводять задачу маршрутизації транспортних засобів до задачі квадратичної необмеженої бінарної оптимізації, яка є ізоморфною до моделі Гамільтона-Ізінга. У такому вигляді задача є придатною до вбудовування у КвК, який знаходить наближений розв’язок, що має найкращу статистичну достовірність або відповідає квантовому стану з найменшою енергією.
Як окремий клас можна виділити алгоритми маршрутизації транспортних засобів для класичних комп’ютерів, які використовують квантові обчислення для прискорення розв’язування задачі. Наприклад, нейромережі, що обчислюють вагові коефіцієнти за допомогою КвК або мурашиний алгоритм, який обчислює феромонний слід у гібридній хмарі. Слід згадати квантово-натхнені алгоритми, що базуються на програмних засобах симуляції КвК і відповідних бібліотеках та дозволяють створювати результативний клас алгоритмів розв’язування задач маршрутизації транспортних засобів.
Висновки. Об’єднання апаратного квантового відпалу з низкою програмних засобів для обчислення оптимізаційних задач для класичних комп’ютерів у гібридний квантово-класичний хмарний сервіс дозволяє отримати переваги у швидкості і точності деяких типів складних оптимізаційних задач комерційного масштабу, зокрема, маршрутизації транспортних засобів, що вже зараз приносить суттєвий прибуток низці корпорацій.
Ключові слова: маршрутизація транспортних засобів, квантовий комп’ютер, відпал, комбінаторна оптимізація, задача комівояжера, кластеризація, кубіт.
Цитувати так: Гуляницький Л.Ф., Корольов В.Ю., Ходзінський О.М. Огляд алгоритмів розв’язування задач маршрутизації у квантово-класичній хмарі. Cybernetics and Computer Technologies. 2023. 2. С. 23–31. https://doi.org/10.34229/2707-451X.23.2.3
Список літератури
1. 250+ Early Quantum Applications https://www.dwavesys.com/learn/featured-applications/ (звернення: 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/ (звернення: 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/ (звернення: 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 (звернення: 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 (звернення: 26.01.2023)
6. Quantum molecule unfolding https://www.quantumcomputinglab.cineca.it/en/2021/08/25/quantum-molecule-unfolding-2/ (звернення: 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 (звернення: 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 (звернення: 26.01.2023)
9. D-Wave Customer Applications | Qubits 2020 https://www.youtube.com/watch?v=oBUaffN7KMY (звернення: 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 (звернення: 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 (звернення: 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.
19. Гуляницький Л.Ф., Коткова А.А. До класифікації задач маршрутизації транспортних засобів. Науковий вісник Ужгородського університету. Серія "Математика і інформатика". 2020. 1 (36). C. 73–84. 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. Горбулін В.П., Гуляницький Л.Ф., Сергієнко І.В. Оптимізація маршрутів команди БПЛА за наявності альтернативних та динамічних депо. Кібернетика і системний аналіз. 2020. 2 (56). С. 31–41. http://nbuv.gov.ua/UJRN/KSA_2020_56_2_6
22. Borowski M. et al. 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 (звернення: 26.01.2023)
26. Корольов В.Ю., Ходзінський О.М. Розв'язування задач комбінаторної оптимізації на квантових комп'ютерах. Cybernetics and Computer Technologies. 2020. 2. С. 5–13. 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 (звернення: 26.01.2023)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна