2023, issue 3, p. 44-58
Received 15.09.2023; Revised 24.09.2023; Accepted 26.09.2023
Published 29.09.2023; First Online 19.10.2023
https://doi.org/10.34229/2707-451X.23.3.4
Previous | FULL TEXT (in Ukrainian) | Next
Route Optimization in Mission Planning for Hybrid DRONE+VEHICLE Transport Systems
Leonid Hulianytskyi *
, Oleg Rybalchenko
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 the context of modern technologies and the widespread use of unmanned aerial vehicles (UAVs) in various fields of activity, the study of optimizing their mission planning becomes increasingly relevant. This is particularly true for hybrid systems where UAVs are integrated with ground transportation ("Drone+Vehicle").
The article deals with the aspects of optimizing the mission routes of a drone that can be transported by a specialized vehicle, performing reconnaissance or maintenance missions for the presented targets. A mathematical model has been developed that allows integrating various planning stages, including determining the direction of the vehicle based on the data obtained during the drone's mission.
The purpose of the paper is development and application of mathematical and software-algorithmic tools, in particular, based on the ideas of swarm intelligence, in planning operations for the inspection or maintenance of a given set of objects using hybrid systems "Drone+Vehicle".
Results. A mathematical model of the problem of routing hybrid systems of the "Drone+Vehicle" type has been formed. Greedy type algorithms, deterministic local search and ant colony optimization (ACO) to solve the problem are proposed, implemented and analyzed. A computational experiment has been conducted to demonstrate the advantages of the AMC algorithm in terms of speed and efficiency, even for problems of high dimensionality.
Conclusions. The proposed approach allows to cover several stages of planning the mission of a hybrid "Drone+Vehicle" system with an aggregated mathematical model. The developed mathematical model also covers the problem of choosing the direction of further movement of a vehicle located in a certain place, depending on the analysis of the results of the inspection of specified targets that may contain objects for inspection or maintenance. To solve the formulated combinatorial optimization problem, greedy type, deterministic local search, and OMC algorithms have been developed. The results of the computational experiment demonstrate the superiority of the OMC algorithm over the combined "greedy + deterministic local search" algorithm.
An important future direction of research is the development and application of routing models and algorithms that take into account the obstacles present on the ground. The developed mathematical apparatus allows to move on to consider problems in which the locations of the vehicle's base on the route are not specified but are determined depending on the configuration of the targets.
Keywords: unmanned aerial vehicles, hybrid systems, mission planning, route optimization, mathematcal modeling, ant colony optimization, logistics.
Cite as: 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
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. 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. Hulianytskyi L.F., Rybalchenko O.V. Formalization of the problem of optimizing the base locations and routes of the UAV group. Cybernetics and Computer Technologies. 2021. 4. P. 12–26. (in Ukrainian) 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. Hulianitskyi L.F., Mulesa O.Y. Applied methods of combinatorial optimization. Kyiv: Kyiv University Publishing and Printing Center, 2016. 142 p. (in Ukrainian)
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)
Previous | FULL TEXT (in Ukrainian) | Next