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

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна

 

УДК 519.8

Задачі маршрутизації транспортних засобів при застосуванні БПЛА

І.М. Ньорба

Інститут кібернетики імені В.М. Глушкова НАН України, Київ

Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути 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)

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна

 

 

 

© Вебсайт та оформлення. 2019-2022,

Інститут кібернетики імені В.М. Глушкова НАН України,

Національна академія наук України.