2025, випуск 4, c. 29-36
Одержано 04.09.2025; Виправлено 04.11.2025; Прийнято 18.11.2025
Надруковано 08.12.2025; Вперше Online 15.12.2025
https://doi.org/10.34229/2707-451X.25.4.3
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Дворівневий алгоритм для задачі маршрутизації БПЛА з рухомими цілями
Н.М. Скибицький 
Київський національний університет імені Тараса Шевченка, Київ
Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Актуальність задач маршрутизації безпілотних літальних апаратів зростає на тлі розширення застосувань БПЛА у сфері оборони. На противагу галузі цивільної авіації зі статичними депо та цілями, предметна область оборони потребує маршрутизації БПЛА з динамічними цілями.
У загальному випадку, задачі переслідування рухомих цілей вивчає теорія диференційних ігор, але розв’язки, отримані в її межах, не завжди можливо застосувати у практичних реаліях. Як наслідок, виникає потреба у комбінаторному аналізі спрощених практичних випадків. Зокрема, у роботі розглядаються цілі з лінійним законом руху.
Запропоновано узагальнення дворівневого алгоритму для кластерної задачі комівояжера на задачу маршрутизації групи БПЛА з рухомими цілями. Також розглянуто кластеризації за положенням та напрямком руху цілей, проведено порівняльний аналіз.
Мета роботи – продемонструвати переваги дворівневого алгоритму над класичним. Дослідити та порівняти кластеризацію цілей за позицією та вектором руху. Встановити відповідність між практичними обмеженнями та оптимальним способом кластеризації.
Результати. Експериментально підтверджено перевагу запропонованого дворівневого методу над класичним алгоритмом у точності за умов доречної кластеризації цілей. Також встановлено оптимальність комбінованого способу кластеризації цілей у загальному випадку. Проведений порівняльний аналіз дозволяє обрати оптимальний метод кластеризації для конкретних практичних обмежень.
Висновки. Дворівневий алгоритм дозволяє прискорити досягнення заданого рівня оптимальності. Комбінована кластеризація цілей призводить до скорочення знайдених маршрутів.
Ключові слова: безпілотний літальний апарат, дрон, оптимізація маршрутів, методи кластеризації.
Цитувати так: Скибицький Н.М. Дворівневий алгоритм для задачі маршрутизації БПЛА з рухомими цілями. Cybernetics and Computer Technologies. 2025. 4. С. 29–36. https://doi.org/10.34229/2707-451X.25.4.3
Список літератури
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://arxiv.org/abs/2310.03222
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 (звернення: 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)
Попередня | ПОВНИЙ ТЕКСТ | Наступна