2021, випуск 4, c. 27-34
Одержано 13.12.2021; Виправлено 18.12.2021; Прийнято 21.12.2021
Надруковано 30.12.2021; Вперше Online 27.01.2022
https://doi.org/10.34229/2707-451X.21.4.3
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Задачі маршрутизації транспортних засобів при застосуванні БПЛА
І.М. Ньорба
Інститут кібернетики імені В.М. Глушкова НАН України, Київ
Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Протягом останніх років використання безпілотних літальних апаратів (БПЛА) стрімко зростає. Спочатку вони були впроваджені для військових цілей, за останні кілька років безпілотні літальні апарати та супутні технології успішно перейшли на цілий ряд нових цивільних застосувань, таких як доставка, логістика, спостереження, розваги тощо. Також вони відкрили нові можливості, наприклад, дозволити працювати у складних або небезпечних зонах. БПЛА має потенціал у вирішенні проблеми з повітряною мобільністю, дозволяючи змінити транспорт і логістику в майбутньому. Поєднання БПЛА із традиційними наземними транспортними засобами може вирішити проблему з доставкою “останньої милі” досягнувши значних покращень у витратах на розповсюдження та швидкості над доставкою транспортними засобами. Однією із найбільших проблем їх застосування є планування маршрутів БПЛА з урахуванням низки обмежень, серед яких затрати часу, відстані чи затрати енергії, вага вантажу, вплив зовнішніх і екологічних умов (такі як напрям вітру чи перешкоди), час автономної роботи БПЛА та вимоги до попиту користувачів, яких потрібно відвідати. Отже, це виявило необхідність класифікації різних видів досліджень та вивчення загальних характеристик досліджуваної області.Ця стаття має на меті допомогти у визначенні основних тем і нових напрямків досліджень, а також надає опублікований огляд поточного стану та внеску в галузь проблеми маршрутизації БПЛА, а також загальну категоризацію задачі маршрутизації транспортних засобів (ЗМТЗ).
Мета роботи. Аналізується науковий внесок у проблеми маршрутизації БПЛА для визначення основних характеристик цих проблем, а також тенденцій дослідження та останніх удосконалень.
Результати. Джерела класифіковано відповідно до сфер застосування БПЛА; згадано методи, які включають точні, евристичні, метаевристичні та змішані алгоритми.
Висновки. Подано огляд робіт щодо проблем маршрутизації з використанням БПЛА та задач, які вони породжують, тенденцій дослідження та останніх розробок.
Ключові слова: безпілотний літальний апарат, маршрутизація, транспортний засіб, оптимізація.
Цитувати так: Ньорба І.М. Задачі маршрутизації транспортних засобів при застосуванні БПЛА. Cybernetics and Computer Technologies. 2021. 4. С. 27–34. https://doi.org/10.34229/2707-451X.21.4.3
Список літератури
1. Gupta R., Kumari A., Tanwar S., Kumar, N. Blockchain-envisioned softwarized multi-swarming uavs to tackle covid-19 situations. IEEE Network. 2020. 35 (2). P. 160–167. https://doi.org/10.1109/MNET.011.2000439
2. Erdelj M., Natalizio E. UAV-assisted disaster management: Applications and open issues. In Proceedings of the 2016 International Conference on Computing, Networking and Communications (ICNC). Kauai, HI, USA, 15–18 February 2016. P. 1–5. https://doi.org/10.1109/ICCNC.2016.7440563
3. Mozaffari M., Saad W., Bennis M., Nam Y., Debbah M. A Tutorial on UAVs for Wireless Networks: Applications, Challenges, and Open Problems. arXiv 2018, arXiv: 1803.00680. https://doi.org/10.1109/COMST.2019.2902862
4. Fernández-Caramés T.M., Blanco-Novoa O., Froiz-Míguez I., Fraga-Lamas P. Towards an Autonomous Industry 4.0 Warehouse: A UAV and Blockchain-Based System for Inventory and Traceability Applications in Big Data-Driven Supply Chain Management. Sensors 2019. 19. 2394. https://doi.org/10.3390/s19102394
5. Гуляницький Л.Ф., Коткова А.А. До класифікації задач маршрутизації транспортних засобів. Науковий вісник Ужгородського університету. Серія "Математика і інформатика". 2020. 1 (36). C. 73–84. https://doi.org/10.24144/2616-7700.2020.1(36).73-84
6. Rodrigues A.J., Lima G. L. A metaheuristic to support the distribution of COVID-19 vaccines. Published in SciELO - Scientific Electronic Library Online. 2021. 31. e20210031. https://www.redalyc.org/journal/3967/396766539025/movil/ (звернення: 14.12.2021)
7. Bocewicz G., Nielsen P., Banaszak Z., Thibbotuwawa A. A Declarative Modelling Framework for Routing of Multiple UAVs in a System with Mobile Battery Swapping Stations. In International Conference on Intelligent Systems in Production Engineering and Maintenance; Springer: Berlin, Germany, 2019. P. 429–441. https://doi.org/10.1007/978-3-319-97490-3_42
8. Dorling K., Heinrichs J., Messier G.G., Magierowski S. Vehicle Routing Problems for Drone Delivery. IEEE Trans. Syst. Man, Cybern. Syst. 2016. 47. P. 70–85. https://doi.org/10.1109/TSMC.2016.2582745
9. Ehsan T., Vahid K. Enhanced intelligent water drops and cuckoo search algorithms for solving the capacitated vehicle routing problem. Information Sciences. 2016. 334. P. 354–378. https://doi.org/10.1016/j.ins.2015.11.036
10. Ilker K., Nursel O. An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows. Computers & Industrial Engineering. 2015. 86. P. 60–68. https://doi.org/10.1016/j.cie.2014.10.014
11. Yao C., Chen S., Yang Z.. Vehicle Routing Problem with Flexible Time Window. A Bi-level Approach. arXiv:2109.03539v1 [eess.SY] 8 Sep 2021. https://arxiv.org/abs/2109.03539 (звернення: 14.12.2021)
12. Montoya-Torres J.R., Franco J.L., Isaza S.N., Jim´enez H.F., Herazo-Padilla N. A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering. 2015. 79. P. 115–129. https://doi.org/10.1016/j.cie.2014.10.029
13. Sung I., Nielsen P. Zoning a Service Area of Unmanned Aerial Vehicles for Package Delivery Services. J. Intell. Robot. Syst. 2019. 97. P. 719–731. https://doi.org/10.1007/s10846-019-01045-7
14. Mohammad M.-J., Seokcheon L. The customer-centric, multi-commodity vehicle routing problem with split delivery. Expert Systems with Applications. 2016. 56. P. 335–348. https://doi.org/10.1016/j.eswa.2016.03.030
15. Gendreau M., Laporte G., Séguin R. Stochastic vehicle routing. Eur. J. Oper. Res. 1996. 88. P. 3–12. https://doi.org/10.1016/0377-2217(95)00050-X
16. 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
17. Zhou T., Zhang J., Shi J., Liu Z., Huang J. Multidepot UAV Routing Problem with Weapon Configuration and Time Window. Jornal of Advanced Transportation. May, 2018. P.3. https://doi.org/10.1155/2018/7318207
18. Ropke S., Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science. 2006. 40 (4). P. 455–472. https://doi.org/10.1287/trsc.1050.0135
19. Torres-Sanchez J., López-Granados F., Peña J.M. An automatic object-based method for optimal thresholding in UAV images: application for vegetation detection in herbaceous crops. Computers and Electronics in Agriculture. 2015. 114. P. 43–52. https://doi.org/10.1016/j.compag.2015.03.019
20. Qin W.-C., Qiu B.-J., Xue X.-Y., Chen C., Xu Z.-F., Zhou Q.-Q. Droplet deposition and control effect of insecticides sprayed with an unmanned aerial vehicle against plant hoppers. Crop Protection. 2016. 85. P. 79–88. https://doi.org/10.1016/j.cropro.2016.03.018
21. Гнатієнко Г.М., Домрачев В.М., Єрмак В.В., Сайко В.Г. Технології використання дронів у агрокібернетиці. В кн.: Ідеї академіка В.М. Глушкова і сучасні проблеми теоретичної кібернетики. Мат. IX Всеукр. наук.-практ. конф. «Глушковські читання» (Київ, 2020 р.). 2020. C.43–46.
22. Palagin O., Romanov V., Galelyuka I., Hrusha V., Voronenko O. Wireless Smart Biosensor for Sensor Networks in Ecological Monitoring. Proceeding of the 9th IEEE International conference on "Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications", IDAACS'2017. Bucharest, Romania. September 21–23, 2017. Р. 679 – 683. https://doi.org/10.1109/IDAACS.2017.8095177
23. Luo H., Niu Y., Zhu M., Hu Y., Ma H. Optimization of Pesticide Spraying Tasks via Multi-UAVs Using Genetic Algorithm. Mathematical Problems in Engineering. November 12, 2017. https://doi.org/10.1155/2017/7139157
24. Edison E., Shima T. Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms. Computers & Operations Research. 2011. 38 (1). P. 340 – 356. https://doi.org/10.1016/j.cor.2010.06.001
25. Lin S.-W., Yu V.F. A simulated annealing heuristic for the team orienteering problem with time windows. European Journal of Operational Research. 2012. 217 (1). P. 94–107. https://doi.org/10.1016/j.ejor.2011.08.024
26. Wang A., Ji X., Wu D., Bai X., Ding N., Pang J., Chen S., Chen X., Fang D. GuideLoc: UAV-Assisted Multitarget Localization System for Disaster Rescue. Mobile Inormation Systems. March, 2017. https://doi.org/10.1155/2017/1267608
27. Pehlivanoglu Y.V. A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV. Aerospace Science and Technology. 16 (1). P. 47–55. https://doi.org/10.1016/j.ast.2011.02.006
28. Birk A., Wiggerich B., Bülow H., Pfingsthorn M., Schwertfeger S. Safety, security, and rescue missions with an unmanned aerial vehicle (UAV): aerial mosaicking and autonomous flight at the 2009 european land robots trials (ELROB) and the 2010 response robot evaluation exercises (RREE). Journal of Intelligent and Robotic Systems: Theory and Applications. 2011. 64 (1). P. 57 – 76. https://doi.org/10.1007/s10846-011-9546-8
29. Rahman E.U., Zhang Y., Ahmad S., Ahmad H.I., Jobaer S. Autonomous vision-based primary distribution systems porcelain insulators inspection using UAVs. Sensors. 2021. 21 (3). P. 974. https://doi.org/10.3390/s21030974
30. Lee Y.S., Park J.W., Barolli L. A localization algorithm based on AOA for ad-hoc sensor networks. Mobile Information Systems. 2012. 8 (1). P. 61 – 72. https://doi.org/10.1155/2012/986327
31. Fan X., Huang C., Fu B., Wen S., Chen X, UAV-Assisted Data Dissemination in Delay-Constrained VANETs. Mathematical Problems in Engineering. Octovber, 2018. https://doi.org/10.1155/2018/8548301
32. Cunha F., Villas L., Boukerche A. et al. Data communication in VANETs: protocols, applications and challenges. Ad Hoc Networks. 2016. 44. P. 90 – 103. https://doi.org/10.1016/j.adhoc.2016.02.017
33. Boussa I., Lepagnot J., Siarry P. A survey on optimization metaheuristics. Information Sciences. An International Journal. 2013. 237. P. 82–117. https://doi.org/10.1016/j.ins.2013.02.041
34. Li X., Clerc M. Swarm Intelligence. In: Handbook of Metaheuristics. Third Edition (Ed. M. Gendreau, J-Y. Potvin). Springer International Publishing AG, 2019. P. 353 – 384. https://doi.org/10.1007/978-3-319-91086-4_11
35. Wang X., Poikonen S., Golden B. The vehicle routing problem with drones: several worst-case results. Optimization Letters. 2017. 11 (4). P. 679 – 697. https://doi.org/10.1007/s11590-016-1035-3
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна