2021, issue 4, p. 27-34
Received 13.12.2021; Revised 18.12.2021; Accepted 21.12.2021
Published 30.12.2021; First Online 27.01.2022
https://doi.org/10.34229/2707-451X.21.4.3
Previous | FULL TEXT (in Ukrainian) | Next
Vehicle Routing Problem When Using UAVs
Iryna Norba
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. In recent years, the use of unmanned aerial vehicles (UAVs) is growing rapidly. Initially introduced for military purposes, drones and related technologies have been successfully switched to a number of new civilian applications in the last few years, such as delivery, logistics, surveillance, entertainment, and more. They also opened up new opportunities, such as working in difficult or dangerous areas. The UAV has the potential to solve the problem of air mobility, allowing to change transport and logistics in the future. Combining UAVs with traditional land vehicles can solve the last-mile delivery problem by achieving significant improvements in distribution costs and speed of vehicle delivery. One of the biggest challenges is to plan UAV routes with a number of constraints, including time, distance or energy costs, cargo weight, environmental and environmental conditions (such as wind direction or obstacles), UAV battery life, and demand requirements. users you want to visit. Thus, it revealed the need to classify different types of research and study the general characteristics of the study area. This article aims to help identify the main topics and new areas of research, as well as provides a published overview of the current state and contribution to the problem of UAV routing, as well as a general categorization of the problem of vehicle routing (VRP).
The purpose of the paper is to analyze the scientific contributions to the problem of UAV routing to determine the main characteristics of these problems, as well as trends in research and recent improvements.
Results. Sources are classified according to the areas of application of UAVs; methods that include exact, heuristic, metaheuristic, and mixed algorithms are mentioned.
Conclusions. An overview of the work on routing problems using UAVs and the tasks they generate, trends in research and recent developments.
Keywords: Unmanned aerial vehicle, routing, vehicle, optimization.
Cite as: Norba I. Vehicle Routing Problem When Using UAVs. Cybernetics and Computer Technologies. 2021. 4. P. 27–34. (in Ukrainian) https://doi.org/10.34229/2707-451X.21.4.3
References
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. Hulianytskyi L.F., Kotkova A.A. To the classification of vehicle routing tasks. Scientific Bulletin of Uzhhorod University. Series "Mathematics and Informatics". 2020. 1 (36). P. 73–84. (in Ukrainian) 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. Gnatiyenko G.M., Umrachev V.M., Yermak V.V., Saiko V.G. Technologies of using drones in agrocaliber. In the book: Ideas of Academician V.M. Glushkov and modern problems of theoretical cybernetics. Mathematical IX All-Ukrainian scientific-practical conference "Glushkovsky Readings" (Kyiv, 2020). 2020. P. 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)
Previous | FULL TEXT (in Ukrainian) | Next