Received 19.06.2024; Revised 30.07.2024; Accepted 10.09.2024

Published 24.09.2024; First Online 30.09.2024

https://doi.org/10.34229/2707-451X.24.3.4

Previous  |  FULL TEXT (in Ukrainian)  |  Next

 

MSC 90C27, 68Q12

About the Problem of Drone Routing

Leonid Hulianytskyi ^{1 *} ,   Natalia Byshovets ²,   Olena Zhdanova ^{2 *}

¹ V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv

² National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”

^* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it., This email address is being protected from spambots. You need JavaScript enabled to view it.

 

Introduction. Unmanned aerial vehicles (UAVs) are attracting considerable interest in a variety of areas, such as logistics, defence, search and rescue, agriculture, manufacturing and environmental monitoring. The effective use of these flexible resources requires the development of models and methods that ensure the creation of safe and efficient flight routes for UAVs.

The purpose of the paper is to study the current state of UAV routing problems, including an analysis of existing research in this field and systematization of scientific approaches and algorithms as well as the formalization of some practically important problems.

Results. A classification of UAV routing problems has been proposed based on various criteria, including the number of UAVs, the number of base locations, UAV recharging constraints, additional conditions, evaluation criteria, and the constancy of conditions. An analysis and classification of UAV routing problems are presented, highlighting the significance of these problems in various fields such as logistics, defense, agriculture, and others. Meaningful formulations of several interrelated practical UAV routing problems have been proposed, and their formalization has been carried out in the form of specific mathematical models.

Conclusions. The development of unmanned aerial vehicles (UAVs) is a dynamic and relevant area with a wide range of applications. The paper systemises scientific approaches and algorithms for optimising UAV routes, analyses and classifies routing problems according to various criteria. The proposed classification allows for a better understanding of the structure of the problems and the selection of appropriate methods for solving them. The main result is the formalisation of a number of practical UAV routing problems in the form of mathematical models, which allows developing effective algorithms for solving these problems, increasing the efficiency of UAVs in various fields, such as logistics, defence and agriculture.

 

Keywords: route optimization, unmanned aerial vehicle, drone, mathematical model, flight resource, combinatorial optimization, monitoring, logistics.

 

Cite as: Hulianytskyi L., Byshovets N., Zhdanova O. About the Problem of Drone Routing. Cybernetics and Computer Technologies. 2024. 3. P. 34–47. (in Ukrainian) https://doi.org/10.34229/2707-451X.24.3.4

 

References

           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.     Kucukoglu I., Dewil R., Cattrysse D. The electric vehicle routing problem and its variations: A literature review. Computers & Industrial Engineering. 2021. 161. 107650. https://doi.org/10.1016/j.cie.2021.107650

           3.     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. Vol. 54. P. 86–109. https://doi.org/10.1016/j.trc.2015.03.005

           4.     Murray C.C., Raj R. The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones. Transportation Research Part C: Emerging Technologies. 2020. Vol. 110. P. 368–398. https://doi.org/10.1016/j.trc.2019.11.003

           5.     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

           6.     Wang X., Poikonen, S., Golden B. The vehicle routing problem with drones: several worst-case results. Optimization Letters. 2017. 11. P. 679–697. https://doi.org/10.1007/s11590-016-1035-3

           7.     Wang Z., Sheu J.B. Vehicle routing problem with drones. Transportation research part B: methodological. 2019. Vol. 122. P. 350–364. http://dx.doi.org/10.1016/j.trb.2019.03.005

           8.     Kuo R.J, Lu S.H., Lai P.Y., Mara S.T.W. Vehicle routing problem with drones considering time windows. Expert Systems with Applications. 2021. 191. 116264. http://dx.doi.org/10.1016/j.eswa.2021.116264

           9.     Jeong H.Y., Lee S. Collaborative hybrid delivery system: Drone routing problem assisted by truck. In Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems: IFIP WG 5.7 International Conference, APMS 2021, Nantes, France, September 5–9, 2021, Proceedings, Part III. Springer Int. Publ. 2021. P. 33–42. https://doi.org/10.1007/978-3-030-85906-0_4

       10.     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

       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. In The Evolution of the Vehicle Routing Problem: A Survey of VRP Research and Practice from 2005 to 2022. Cham: Springer Nature Switzerland, 2023. P. 1–64. https://doi.org/10.1007/978-3-031-18716-2

       12.     Horbulin V.P., Hulianytskyi 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

       13.     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

       14.     Yakici E. Solving location and routing problem for UAVs. Computers & Industrial Engineering. 2016. 102. P. 294–301. https://doi.org/10.1016/j.cie.2016.10.029

       15.     Furini F., Persiani C.A., Toth P. The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace. Transportation Research Part B: Methodological. 2016. 90. P. 38–55. https://doi.org/10.1016/j.trb.2016.04.009

       16.     Alakbarov Z., Bekirova L. UAV Swarm Systems. Journal of Intelligent & Robotic Systems. 2020. 98 (1). P. 19–43. http://dx.doi.org/10.36962/PAHTEI34112023-274

       17.     Morandi N., Leus R., Yaman H. The Orienteering Problem with Drones. Transportation Research Part C: Emerging Technologies. 2020. 111. P. 210–230. http://dx.doi.org/10.1287/trsc.2023.0003

       18.     Stodola P., Kutěj L. Multi-Depot Vehicle Routing Problem with Drones: Mathematical Formulation, Solution Algorithm and Experiments. Computers & Operations Research. 2020. 112. 104768. http://dx.doi.org/10.2139/ssrn.4429473

       19.     Xiang H., Liu X., Song X., Zhou W. UAV Path Planning Based on Enhanced PSO-GA. International Journal of Advanced Robotic Systems. 2020. 17 (1). P. 271–282. http://dx.doi.org/10.1007/978-981-99-9119-8_25

       20.     Schermer D., Moeini M., Wendt O. A Matheuristic for the Vehicle Routing Problem with Drones and Its Variants. Computers & Operations Research. 2020. 111. 106536. http://dx.doi.org/10.1016/j.trc.2019.06.016

       21.     Wang X., Poikonen S., Golden B. The vehicle routing problem with drones: several worst-case results. Optimization Letters. 2017. 11. P. 679–697. https://doi.org/10.1007/s11590-016-1035-3

       22.     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

       23.     Kuo R.J, Lu S.H., Lai P.Y., Mara S.T.W. Vehicle routing problem with drones considering time windows. Expert Systems with Applications. 2022. 191. 116264. https://doi.org/10.1016/j.eswa.2021.116264

       24.     Jeong H.Y., Lee S. Collaborative hybrid delivery system: Drone routing problem assisted by truck. In Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems: IFIP WG 5.7 International Conference, APMS 2021, Nantes, France, September 5–9, 2021, Proceedings, Part III. Springer Int. Publ. 2021. P. 33–42. https://doi.org/10.1007/978-3-030-85906-0_4

       25.     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

       26.     Horbulin V.P., Hulianytskyi L.F., Sergienko I.V. Planning of Logistics Missions of the “UAV+Vehicle” Hybrid Systems. Cybern Syst Anal. 2023. 59. P. 733–742. https://doi.org/10.1007/s10559-023-00609-8

       27.     Hulianytskyi L., Rybalchenko O. Route Optimization in Mission Planning for Hybrid DRONE+VEHICLE Transport Systems. Cybernetics and Computer Technologies. 2023. 3. P. 44–58. (in Ukrainian) https://doi.org/10.34229/2707-451X.23.3.4

       28.     Poikonen S., Golden B. The Mothership and Drone Routing Problem. European Journal of Operational Research. 2019. 277 (2). P. 690–703. http://dx.doi.org/10.1287/ijoc.2018.0879

       29.     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

       30.     Kyriakakis N.A., Stamadianos T., Marinaki M., Marinakis Y. The electric vehicle routing problem with drones: An energy minimization approach for aerial deliveries. Cleaner Logistics and Supply Chain. 2022. 4. 100041. https://doi.org/10.1016/j.clscn.2022.100041

       31.     Guerriero F., Surace R., Loscrí V., Natalizio E. A Multi-Objective Approach for Unmanned Aerial Vehicle Routing Problem with Soft Time Windows Constraints. Applied Mathematical Modelling. 2014. 38 (3). P. 839–852. https://doi.org/10.1016/j.apm.2013.07.002

       32.     Kim D., Lee K., Moon I. Stochastic Facility Location Model for Drones Considering Uncertain Flight Distance. Computers & Industrial Engineering. 2019. 128. https://link.springer.com/article/10.1007%2Fs10479-018-3114-6

       33.     Ermagun A., Tajik N. Multiple-Drones-Multiple-Trucks Routing Problem for Disruption Assessment. Transportation Research Record Journal of the Transportation Research Board. 2022. 2677 (34). P. 139–150. https://doi.org/10.1177/03611981221108378

       34.     Braekers K., Ramaekers K., Nieuwenhuyse I.V. The Vehicle Routing Problem: State of the Art Classification and Review. Computers & Industrial Engineering. 2016. 99 (1). P. 300–313. https://doi.org/10.1016/j.cie.2015.12.007

       35.     Guerrero J.A., Bestaoui Y. UAV Path Planning for Structure Inspection in Windy Environments. Journal of Intelligent & Robotic Systems. 2013. 69 (1). P. 297–311. https://doi.org/10.1007/s10846-012-9778-2

       36.     Kim S.J., Lim G.J., Cho J., Côté M.J. Drone-Aided Healthcare Services for Patients with Chronic Diseases in Rural Areas. Journal of Intelligent & Robotic Systems. 2017. 88 (1). P. 163–180. https://doi.org/10.1007/s10846-017-0548-z

       37.     Manyam S.G., Rathinam S., Darbha S. GPS Denied UAV Routing with Communication Constraints. Journal of Intelligent & Robotic Systems. 2016. 84 (1). P. 691–703. https://doi.org/10.1007/s10846-016-0343-2

       38.     Habib D., Jamal H., Khan S.A. Employing Multiple Unmanned Aerial Vehicles for Co-Operative Path Planning. International Journal of Advanced Robotic Systems. 2013. 10 (5). 235. https://doi.org/10.5772/56286

       39.     Horbulin V.P., Mosov S.P. Drone swarms are the culmination of the droneization of wars. Visnyk Natsionalnoi akademii nauk Ukrainy. 2024. No. 3. P. 3–11. (in Ukrainian) https://doi.org/10.15407/visn2024.03.003

       40.     Liu W., Zhang T., Huang S., Li K. A hybrid optimization framework for UAV reconnaissance mission planning. Computers & Industrial Engineering. 2022. 173. 108653. https://doi.org/10.1016/j.cie.2022.108653

       41.     Kim D., Moon I. Scheduling‐Location Problem with Drones. Computers & Industrial Engineering. 2020. 139. http://dx.doi.org/10.1111/itor.13423

       42.     Blufstein M., Lera-Romero G., Soulignac F.J. Decremental State-Space Relaxations for the Basic Traveling Salesman Problem with a Drone. INFORMS Journal on Computing. 2024. 32 (2). P. 353–369. https://doi.org/10.1287/ijoc.2019.0931

       43.     Skorobogatov G., Barrado C., Salamí E. Multiple UAV Systems: A Survey. Unmanned Systems. 2019. 08 (1). P. 1–14. https://doi.org/10.1142/S2301385020500090

       44.     Gugan G., Haque A. Path Planning for Autonomous Drones: Challenges and Future Directions. Drones. 2023. 7. 169. https://doi.org/10.3390/drones7030169

       45.     Hajjama A., Créput J.-C., Koukam A. From the TSP to the Dynamic VRP: An Application of Neural Networks in Population Based Metaheuristic. Metaheuristics for Dynamic Optimization. 2012. https://doi.org/10.1007/978-3-642-30665-5_11

       46.     Tamke F., Buscher U. A Branch-and-Cut Algorithm for the Vehicle Routing Problem with Drones. Transportation Research Part C: Emerging Technologies. 2021. 115. 102615. http://dx.doi.org/10.1016/j.trb.2020.11.011

       47.     Kitjacharoenchai P., Ventresca M., Moshref-Javadi M., Lee S., Tanchoco J.M.A., Brunese P.A. Multiple Traveling Salesman Problem with Drones: Mathematical Model and Heuristic Approach. European Journal of Operational Research. 2019. 272 (3). P. 855–868. https://doi.org/10.1016/j.cie.2019.01.020

       48.     Schermer D., Moeini M., Wendt O. The Traveling Salesman Drone Station Location Problem. Transportation Science. 2020. 53 (1). P. 123–137. https://www.researchgate.net/publication/333804560_The_Traveling_Salesman_Drone_Station_Location_Problem

       49.     Li H., Feilong W., Zhan Z. Drone Routing Problem with Swarm Synchronization. Operations Research Letters. 2023. 48 (4). P. 380–386. https://doi.org/10.1016/j.orl.2020.03.008

       50.     Kitjacharoenchai P., Lee S. Vehicle Routing Problem with Drones for Last Mile Delivery. Procedia Manufacturing. 2019. 39. P. 314–324. https://doi.org/10.1016/j.promfg.2020.01.338

       51.     Houming F., Yueguang Z., Panjun T. Multi-Depot Electric Vehicle Routing Problem with Drones under Time-Dependent Networks. Journal of Intelligent and Connected Vehicles. 2023. 4 (1). P. 1–17. https://doi.org/10.13587/j.cnki.jieem.2023.02.013

       52.     Hulianytskyi L., Rybalchenko O. Optimization of decisions when planning a UAV group mission with alternative depots. Selected Papers of the III International Scientific Symposium “Intelligent Solutions” (IntSol-2023). Symposium Proceedings, September 27–28, 2023, Kyiv, Ukraine. CEUR Workshop Proceedings. 2023. Vol. 3538. P. 245–256. https://ceur-ws.org/Vol-3538/Paper_22.pdf

       53.     Tong B., Wang J., Wang X., Zhou F., Mao X., Zheng W. Optimal Route Planning for Truck–Drone Delivery Using Variable Neighborhood Tabu Search Algorithm. Applied Sciences. 2022. 12 (1). 529. https://doi.org/10.3390/app12010529

       54.     Pisinger D., Ropke S. A General Heuristic for Vehicle Routing Problems. Computers & Operations Research. 2007. 34 (8). P. 2403–2435. https://doi.org/10.1016/j.cor.2005.09.012

       55.     Liu Y.-Q., Han J., Zhang Y., Li Y., Jiang T. Multivisit Drone-Vehicle Routing Problem with Simultaneous Pickup and Delivery Considering No-Fly Zones. Discrete Dynamics in Nature and Society. 2023. https://doi.org/10.1155/2023/1183764

       56.     Baldacci R., Bartolini E., Laporte G. Some Applications of the Generalized Vehicle Routing Problem. Journal of the Operational Research Society. 2010. 61 (7). P. 1072–1077. https://doi.org/10.1057/jors.2009.51

       57.     Moadab A., Farajzadeh F., Valilai O.F. Drone Routing Problem Model for Last-Mile Delivery Using the Public Transportation Capacity as Moving Charging Stations. Scientific Reports. 2022. 12 (1). 7220. https://doi.org/10.1038/s41598-022-10408-4

       58.     Campbell J.F., Corberán Á., Plana I., Martínez P.S. The Multi‐Purpose K‐Drones General Routing Problem. Journal of the Operational Research Society. 2022. 73 (1). P. 13–28. https://doi.org/10.1002/net.22176

       59.     Elghitani F. Dynamic UAV Routing for Multi-Access Edge Computing. IEEE Transactions on Vehicular Technology, PP(99). 2024. P. 1–11. https://doi.org/10.1109/TVT.2024.3360253

       60.     Xu Y., Che C. A Brief Review of the Intelligent Algorithm for Traveling Salesman Problem in UAV Route Planning. 2019 IEEE 9th International Conference on Electronics Information and Emergency Communication (ICEIEC). 2019. P. 1–6. https://doi.org/10.1109/ICEIEC.2019.8784651

       61.     Klein D.J., Venkateswaran S., Isaacs J.T. Localization with Sparse Acoustic Sensor Network Using UAVs as Information-Seeking Data Mules. ACM Transactions on Sensor Networks. 2013. 9 (3). P. 1–29. https://doi.org/10.1145/2480730.2480733

       62.     Arsie A., Frazzoli E. Efficient Routing of Multiple Vehicles with No Explicit Communications. International Journal of Robust and Nonlinear Control. 2018. 28 (2). P. 375–395. https://doi.org/10.1002/rnc.1258

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  FULL TEXT (in Ukrainian)  |  Next