2023, випуск 3, c. 44-58
Одержано 15.09.2023; Виправлено 24.09.2023; Прийнято 26.09.2023
Надруковано 29.09.2023; Вперше Online 19.10.2023
https://doi.org/10.34229/2707-451X.23.3.4
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Оптимізація маршрутів при плануванні місій гібридних транспортних систем "Дрон+Транспортний засіб"
Л.Ф. Гуляницький * 
, О.В. Рибальченко
Інститут кібернетики імені В.М. Глушкова НАН України, Київ
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. В контексті сучасних технологій та широкого застосування безпілотних літальних апаратів (БпЛА) у різних сферах діяльності, дослідження оптимізації планування їх місій набуває актуальності. Це зокрема стосується гібридних систем, де дрони інтегровані із наземним транспортом ("Дрон+Транспортний засіб").
У статті розглянуто аспекти оптимізації маршрутів місій дрона, який може бути транспортований спеціалізованим транспортним засобом, виконуючи місії розвідування чи обслуговування представлених цілей. Розроблено математичну модель, що дозволяє інтегрувати різні етапи планування, включаючи визначення можливого напряму руху транспортного засобу на основі даних, отриманих під час виконання місії дроном.
Мета роботи – розроблення і застосування математичних та програмно-алгоритмічних засобів, зокрема, на основі ідей ройового інтелекту, в плануванні операцій при обстеженні або обслуговуванні заданої множини об'єктів з використанням гібридних систем "Дрон+ Транспортний засіб".
Результати. Сформовано математичну модель проблеми маршрутизації гібридних систем типу "Дрон+ТЗ". Запропоновані, реалізовані та проаналізовані алгоритми жадібного типу, детермінованого локального пошуку та оптимізації мурашиними колоніями (ОМК) для розв'язування задачі. Проведено обчислювальний експеримент, який показав переваги алгоритму ОМК з точки швидкодії та ефективності, навіть для задач підвищеної розмірності.
Висновки. Пропонований підхід дозволив охопити декілька етапів планування місії гібридної системи "Дрон+ТЗ" агрегованою математичною моделлю. Розроблена математична модель дозволяє охоплювати і проблему вибору напряму подальшого руху транспорту, що знаходиться у певному місці, у залежності від аналізу результатів обстеження заданих цілей, у яких можуть знаходитися об'єкти для обстеження чи обслуговування. Для розв'язування сформульованої задачі комбінаторної оптимізації розроблено алгоритми жадібного типу, детермінованого локального пошуку та ОМК. Результати обчислювального експерименту продемонстрували перевагу алгоритму ОМК над комбінованим алгоритмом "жадібний алгоритм +детермінований локальний пошук".
Важливим подальшим напрямом досліджень є розробка і застосування моделей та алгоритмів маршрутизації, які враховують наявні на місцевості перешкоди. Розроблений математичний апарат дозволяє переходити до розгляду задач, у яких місця базування на маршруті транспорту не задаються, а визначаються у залежності від конфігурації цілей.
Ключові слова: безпілотні літальні апарати, гібридні системи, планування місій, оптимізація маршрутів, математичне моделювання, оптимізація мурашиними колоніями, логістика.
Цитувати так: Гуляницький Л.Ф., Рибальченко О.В. Оптимізація маршрутів при плануванні місій гібридних транспортних систем "Дрон+Транспортний засіб". Cybernetics and Computer Technologies. 2023. 3. С. 44–58. https://doi.org/10.34229/2707-451X.23.3.4
Список літератури
1. Thibbotuwawa A., Bocewicz G., Nielsen P., Banaszak, Z. Unmanned aerial vehicle routing problems: a literature review. Applied sciences. 2020. 10 (13). 4504. https://doi.org/10.3390/app10134504
2. Macrina G., Di Puglia Pugliese L., Guerriero F, Laporte G. Drone-aided routing: A literature review. Transportation Research Part C. 2020. 120. 102762 https://doi.org/10.1016/j.trc.2020.102762
3. Huang S.H., Huang Y.H., Blazquez C.A., Chen C.Y. Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm. Advanced Engineering Informatics. 2022. 51. 101536. https://doi.org/10.1016/j.aei.2022.101536
4. Abubakar A.I., Mollel M.S., Onireti O., Ozturk M., Ahmad I., Asad S.M., ..., Imran M.A. Coverage and throughput analysis of an energy efficient UAV base station positioning scheme. Computer Networks. 2023. 232. 109854. https://doi.org/10.1016/j.comnet.2023.109854
5. Liu X., Jing T., Hou L. An FW–GA Hybrid Algorithm Combined with Clustering for UAV Forest Fire Reconnaissance Task Assignment. Mathematics. 2023. 11 (10). 2400. https://doi.org/10.3390/math11102400
6. Li J., Zhao H., Wang H., Gu F., Wei J., Yin H., Ren B. Joint Optimization on Trajectory, Altitude, Velocity, and Link Scheduling for Minimum Mission Time in UAV-Aided Data Collection. IEEE Internet Things J. 2020. 7. P. 1464–1475. https://doi.org/10.1109/JIOT.2019.2955732
7. Li J., Xiong Y., She J. UAV path planning for target coverage task in dynamic environment. IEEE Internet of Things Journal. 2023. https://doi.org/10.1109/JIOT.2023.3277850
8. Kliushnikov I., Fesenko H., Kharchenko V., Illiashenko O., Morozova O. UAV fleet based accident monitoring systems with automatic battery replacement systems: Algorithms for justifying composition and use planning. International Journal of Safety and Security Engineering. 2021. 11 (4). P. 319–328. https://doi.org/10.18280/ijsse.110404
9. Rakhmetullina S., Zhomartkyzy G., Krak I., Kamelova A. Development of an Algorithm for Solving an Asymmetric Routing Problem Based on the Ant Colony Method. Cybernetics and Systems Analysis. 2023. 59. P. 526–534. https://doi.org/10.1007/s10559-023-00588-w
10. Ahn N., Kim S. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial and Management Optimization. 2022. 18 (3). P. 1651–1663. https://doi:10.3934/jimo.2021037
11. 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
12. Murray C.C., Chu A.G. The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies. 2015. 54. P. 86–109. https://doi.org/10.1016/j.trc.2015.03.005
13. Gonzalez-R P.L., Canca D., Andrade-Pineda J.L., Calle M., Leon-Blanco J.M. Truck-drone team logistics: A heuristic approach to multi-drop route planning. Transportation Research Part C: Emerging Technologies. 2020. 114. P. 657–680. https://doi.org/10.1016/j.trc.2020.02.030
14. Zhang S., Liu S., Xu W., Wang W. A novel multi-objective optimization model for the vehicle routing problem with drone delivery and dynamic flight endurance. Computers & Industrial Engineering. 2022. 173. 108679. https://doi.org/10.1016/j.cie.2022.108679
15. Yurek E.E., Ozmutlu H.C. Traveling salesman problem with drone under recharging policy. Computer Communications. 2021. 179. P. 35–49. https://doi.org/10.1016/j.comcom.2021.07.013
16. Meng S., Guo X., Li D., Liu G. The multi-visit drone routing problem for pickup and delivery services. Transportation Research Part E: Logistics and Transportation Review. 2023. 169. 102990. https://doi.org/10.1016/j.tre.2022.102990
17. Poikonen S., Golden B. The mothership and drone routing problem. INFORMS Journal on Computing. 2020. 32 (2). P. 249–262. https://doi.org/10.1287/ijoc.2018.0879
18. Murray C.C., Raj R. The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones. Transportation Research Part C: Emerging Technologies. 2020. 110. P. 368–398. https://doi.org/10.1016/j.trc.2019.11.003
19. Leon-Blanco J. M., Gonzalez-R P. L., Andrade-Pineda J. L., Canca D., Calle M. A multi-agent approach to the truck multi-drone routing problem. Expert Systems with Applications. 2022. 195. 116604. https://doi.org/10.1016/j.eswa.2022.116604
20. Poikonen S., Golden B., Poikonen S., Golden B. Multi-visit drone routing problem. Computers & Operations Research. 2020. 113. 104802. https://doi.org/10.1016/j.cor.2019.104802
21. Viloria R.D., Solano‐Charris E.L., Muñoz‐Villamizar A., Montoya‐Torres J.R. Unmanned aerial vehicles/drones in vehicle routing problems: a literature review. Int. Transactions in Operational Research. 2021. 28 (4). P. 1626–1657. http://dx.doi.org/10.1111/itor.12783
22. Luo Z., Poon M., Zhang Z., Liu Z., Lim A. The multi-visit traveling salesman problem with multi-drones. Transportation Research Part C: Emerging Technologies. 2021. 128. 103172. https://doi.org/10.1016/j.trc.2021.103172
23. Morandi N., Leus R., Matuschke J., Yaman H. The Traveling Salesman Problem with Drones: The Benefits of Retraversing the Arcs. Transportation Science. 2023. 57 (5). P. 1340–1358. https://doi.org/10.1287/trsc.2022.0230
24. Tamke F., Buscher U. The vehicle routing problem with drones and drone speed selection. Computers & Operations Research. 2023. 152. 106112. https://doi.org/10.1016/j.cor.2022.106112
25. Cengiz E., Yilmaz C., Kahraman H., Suiçmez Ç. Effects of Variable UAV Speed on Optimization of Travelling Salesman Problem with Drone (TSP-D). In: Smart Applications with Advanced Machine Learning and Human-Centred Problem Design. ICAIAME 2021. Engineering Cyber-Physical Systems and Critical Infrastructures. Springer, Cham. 2023. 1. https://doi.org/10.1007/978-3-031-09753-9_23
26. Jeong H.Y., Lee S. Collaborative Hybrid Delivery System: Drone Routing Problem Assisted by Truck. In: Dolgui, A., Bernard, A., Lemoine, D., von Cieminski, G., Romero, D. (eds) Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems. APMS 2021. IFIP Advances in Information and Communication Technology. Springer, Cham. 2021. 632. https://doi.org/10.1007/978-3-030-85906-0_4
27. Jeong H.Y., Lee S. Drone routing problem with truck: Optimization and quantitative analysis. Expert Systems with Applications. 2023. 227. 120260. https://doi.org/10.1016/j.eswa.2023.120260
28. Horbulin V.P., Hulianytsky L.F., Sergienko I.V. Optimization of UAV Team Routes in the Presence of Alternative and Dynamic Depots. Cybernetics and Systems Analysis. 2020. 56 (2). P. 195–203. https://doi.org/10.1007/s10559-020-00235-8
29. Wang Z., Sheu J.B. Vehicle routing problem with drones. Transportation research part B: methodological. 2019. 122. P. 350–364. https://doi.org/10.1016/j.trb.2019.03.005
30. Chung S.H., Sah B., Lee J. Optimization for Drone and Drone-truck Combined Operations: A Review of the State of the Art and Future Directions. Computers and Operations Research. 2020. 123. 105004. https://doi.org/10.1016/j.cor.2020.105004
31. Moshref-Javadi, M, Winkenbach M. Applications and Research avenues for drone-based models in logistics: A classification and review. Expert Systems with Applications. Expert Systems with Applications. 2021. 177. 114854. https://doi.org/10.1016/j.eswa.2021.114854
32. Гуляницький Л.Ф., Рибальченко О.В. Формалізація проблеми оптимізації місць базування та маршрутів групи БПЛА. Cybernetics and Computer Technologies. 2021. 4. С. 12–26. https://doi.org/10.34229/2707-451X.21.4.2
33. Loehr N.A. Combinatorics. Discrete Mathematics and its Applications (2nd Edition). N.Y: Chapman and Hall/CRC, 2017. 642 p.
34. Lenstra J.K., Kan A.R. Complexity of vehicle routing and scheduling problems. Networks. 1981. 11 (2). P. 221–227. https://doi.org/10.1002/net.3230110211
35. Handbook of Metaheuristics. Third Edition (Gendreau V., Potvin J.-Y., eds). Cham: Springer, 2019. 604 p.
36. Гуляницький Л.Ф., Мулеса О.Ю. Прикладні методи комбінаторної оптимізації. К.: Видавничо-поліграфічний центр "Київський університет", 2016. 142 с.
37. Snytyuk V.Y., Suprun O.O. Evolutionary techniques for complex objects clustering. IEEE 4th International Conference Actual Problems of Unmanned Aerial Vehicles Developments (APUAVD), October 17-19, 2017, Kyiv, Ukraine. P. 270–273. https://doi.org/10.1109/APUAVD.2017.83088
38. Stoyan, Y.G., Yakovlev S.V. Theory and Methods of Euclidian Combinatorial Optimization: Current Status and Prospects. Cybernetics and Systems Analysis. 2020. 56 (3). P. 366–379. https://doi.org/10.1007/s10559-020-00253-6
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна