2025, issue 4, p. 29-36
Received 04.09.2025; Revised 04.11.2025; Accepted 18.11.2025
Published 08.12.2025; First Online 15.12.2025
https://doi.org/10.34229/2707-451X.25.4.3
Previous | FULL TEXT (in Ukrainian) | Next
Two-Level Algorithm for the UAV Routing Problem with Moving Targets
Nikita Skybytskyi 
Taras Shevchenko National University of Kyiv, Kyiv
Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. UAV routing problems gain relevance considering expanding uses in the defense industry. Contrary to the civil aviation with static depots and end users, the problems arising in defense require drone routing with moving targets.
The theory of differential games has extensively studied the problems related to pursuit of dynamic targets in the general case, but the resulting solutions are difficult to apply in practical scenarios. Hence combinatorial methods are needed for simplified practical models. In particular, we consider all targets to be moving with a constant velocity vector.
This article proposes a two-level algorithm for the problem of routing a group of UAVs with moving targets. We compare different clustering methods, including clustering by position, velocity, and a combined approach.
The purpose of the article is to show the superiority of a two-level algorithm over the classical algorithm in solution quality under certain conditions. Additionally, we establish the necessity of the combined clustering methods in the general case and predict a correspondence between optimal clustering methods and practical routing scenarios.
Results. We established that a two-level algorithm is better than the original algorithm under clustering conditions. We developed software that can be used to solve instances of the UAVRP with moving targets.
Conclusions. A two-level algorithm improves the process of routing a group of UAVs in pursuit of a group of moving targets. A combined clustering strategy proved superior for total route length minimization.
Keywords: unmanned aerial vehicle, drone, route optimization, clustering methods.
Cite as: Skybytskyi N. Two-Level Algorithm for the UAV Routing Problem with Moving Targets. Cybernetics and Computer Technologies. 2025. 4. P. 29–36. (in Ukrainian) https://doi.org/10.34229/2707-451X.25.4.3
References
1. Hulianytskyi L., Byshovets N., Zhdanova O. About the Problem of Drone Routing. Cybernetics and Computer Technologies, 2024. 3. P. 34–47. http://dx.doi.org/10.34229/2707-451X.24.3.4
2. Long Y. et al. Dynamic Truck–UAV Collaboration and Integrated Route Planning for Resilient Urban Emergency Response. IEEE Transactions on Engineering Management. 2024. Vol. 71. P. 9826–9838. http://dx.doi.org/10.1109/TEM.2023.3299693
3. Arsie A., Frazzoli E. Efficient routing of multiple vehicles with no explicit communications. International Journal of Robust and Nonlinear Control. 2007. No. 2. P. 154–164. http://dx.doi.org/10.1002/rnc.1258
4. 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. No. 2. P. 195–203. http://dx.doi.org/10.1007/s10559-020-00235-8
5. Friedman A. Differential games. Dover Publications, 2013. 368 p.
6. Isaacs R. Differential games: a mathematical theory with applications to warfare and pursuit, control and optimization. Dover Publications, 2012. 741 p.
7. Kucherenko Yu., Naumenko M., Kuznetsova M. Analysis Experience Use Unbeatural Vehicle Apparatus And Determination Their Further Development During Conduct Netset Central Operations. Systems of Arms and Military Equipment. 2018. No. 1. P. 25–30. http://dx.doi.org/10.30748/soivt.2018.53.03
8. Ding C., Cheng Y., He M. Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale TSPs. Tsinghua Science and Technology. 2007. No. 4. P. 459–465. https://doi.org/10.1016/S1007-0214(07)70068-8
9. Kuo R. J. et al. Applying NSGA-II to vehicle routing problem with drones considering makespan and carbon emission. Expert Systems with Applications. 2023. No. 221. P. 119777. https://doi.org/10.1016/j.eswa.2023.119777
10. Frieze A., Pegden W. The bright side of simple heuristics for the TSP. arXiv preprint, 2023. https://doi.org/10.37236/12651
11. Arora S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM. 1998. No. 5. P. 753–782. http://dx.doi.org/10.1145/290179.290180
12. Ran X. et al. Comprehensive survey on hierarchical clustering algorithms and the recent developments. Artificial Intelligence Review. 2023. No. 8. P. 8219–8264. http://doi.org/10.1007/s10462-022-10366-3
13. Vásconez J.P. et. al. Smart Delivery Assignment through Machine Learning and the Hungarian Algorithm. Smart Cities. 2024. No. 3. P. 1109–1125. https://doi.org/10.3390/smartcities7030047
14. Clustered pursuit generated test suite. GitHub. https://github.com/nika-skybytska/clustered-pursuit/blob/f64acb39a5b23a902e2cae7f6f8d69ae316fd0fb/tests/generated_suite.json (accessed: 30.08.2025)
15. Benlakhdar S., Rziza M., Thami R.O. In-depth Analysis of von Mises Distribution Models: Understanding Theory, Applications, and Future Directions. Statistics, Optimization & Information Computing. 2024. No. 4. P. 1210–1230. https://doi.org/10.19139/soic-2310-5070-1919
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next