Оптимизация маршрутов полета БПЛА при групповом патрулировании протяженных территорий как множественная задача коммивояжера с несколькими депо

Одной из перспективных сфер совместного использования беспилотных летательных аппаратов (БПЛА) является групповое воздушное патрулирование больших территорий. Важным этапом организации данного процесса является планирование полетов БПЛА. В работе рассматривается задача оптимального планирования маршрутов полета группы БПЛА при патрулировании территорий большой протяженности с несколькими депо — пунктами базирования беспилотников. Примером таких территорий могут служить труднодоступные территориальные воды или узкие приграничные участки (побережье, горные и лесные массивы) какого-либо государства. Предполагается, что патрулируемая территория имеет вытянутую форму и может быть разбита на цепочку смежных зон патрулирования, предписанных отдельным БПЛА. Маршрут полета беспилотника проходит через смежные зоны. Полетное задание, выполняемое периодически каждым беспилотником, состоит в его перемещении в заданную полетную зону, сборе и передаче оперативных данных в пункт управления. Оптимизационный аспект планирования маршрутов полета БПЛА состоит в минимизации максимальной длины маршрута при облете всех патрулируемых зон. Рассматриваемая задача математически формализуется как множественная задача коммивояжера (МЗК) с несколькими депо. Поскольку она относится к классу NP-трудных задач комбинаторной оптимизации, то практический интерес представляют приближенные эвристические и метаэвристические подходы к ее решению. Предлагается метаэвтристический метод решения МЗК с применением генетических алгоритмов. В качестве модельных примеров рассмотрены задачи патрулирования сухопутной и морской границ Вьетнама, решение которых получено в среде MATLAB с использованием математического пакета Global Optimization Toolbox.

1. Садыков М. Ф., Горячев М. П. Система воздушного патрулирования и управления транспортными потоками // Вестник НЦ БЖД. 2017. № 1 (31). С. 59—65.

2. Liu Y., Zhong Liu Z., Shi J., Wu G., Chen C. Optimization of Base Location and Patrol Routes for UAV in Border Intelligence, Surveillance and Reconnaissance // Journal of Advanced Transportation Vol. 2019. 2019. P. 13.

3. Мелехин В. Б., Хачумов М. В. Планирование автономным беспилотным летательным аппаратом эффективных маршрутов облета целей // Авиакосмическое приборостроение. 2020. № 4. С. 3—14.

4. Курейчик В. М., Лагунова Ю. А. Задачи о коммивояжере. Обзор и методы решения. Palmarium Academic Publishing, 2019. 60 c.

5. Cheikhrouhou O., Khoufi I. A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy // Comput. Sci. Rev. 2021. Vol. 40, N. 100369. P. 76.

6. Филимонов А. Б., Филимонов Н. Б. Оптимальная маршрутизация полетов БПЛА при групповом патрулировании территорий // Journal of Advanced Research in Technical Science. 2023. Iss. 34. P. 49—55.

7. Filimonov A. B., Filimonov N. B., Pham Q. P. Planning of Drones Flight of Routes when Group Patrolling of Large Extended Territories // 2023 V International Conference on Control in Technical Systems (CTS). Saint Petersburg, RF. 2023. P. 228—231.

8. Филимонов А. Б., Филимонов Н. Б., Нгуен Т. К., Фам К. Ф. Планирование маршрутов полета БПЛА в задачах группового патрулирования протяженных территорий // Мехатроника, автоматизация, управление. 2023. Т. 24, № 7. С. 374—381.

9. Филимонов А. Б., Филимонов Н. Б. Задача группового патрулирования протяженных территорий с множеством депо // Journal of Advanced Research in Technical Science. 2023. Iss. 37. P. 42—51.

10. Laporte G., Nobert Y., Arpin D. Optimal Solutions to Capacitated Multi Depot Vehicle Routing Problems // Congressus Numerantium. 1984. Vol. 44. P. 283—292.

11. Меламед И. И., Сергеев С. И., Сигал И. Х. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика. 1989. Вып. 9. С. 3—33.

12. Ho W. A Multi-Depot Travelling Salesman Problem and its Iterative and Integrated Approaches // Int. J. Operational Research. 2006. Vol. 1, N. 4. P. 382—396.

13. Семенов С. С., Педан А. В., Воловиков В. С., Климов И. С. Анализ трудоемкости различных алгоритмических подходов для решения задачи коммивояжера // Системы управления, связи и безопасности. 2017. № 1. С. 116—131.

14. Zhang T., Gruver W. A., Smith M. H. Team Scheduling by Genetic Search // Proceedings of the second international conference on intelligent processing and manufacturing of materials. 1999. Vol. 2. P. 839—844.

15. Singh D. R., Singh M. K., Singh T., Prasad R. Genetic Algorithm for Solving MTSP using a New Crossover and Population Generation // Computación y Sistemas. 2018. Vol. 22, N. 2. P. 491—503.

16. Курейчик В. М., Логунова Ю. А. Анализ перспективности применения генетического алгоритма при решении задачи коммивояжера // Информационные технологии. 2018. Т. 24, № 11. С. 691—697.

17. Ghoseiri K., Ghannadpour S. A Hybrid Genetic Algorithm for Multi-Depot Homogenous Locomotive Assignment with Time Windows // Appl. Soft Comput. 2010. Vol. 10. P. 53—65.

18. Karakatič S., Podgorelec V. A Survey of Genetic Algorithms for Solving Multi Depot Vehicle Routing Problem // Applied Soft Computing. 2015. Vol. 27. P. 519—532.

19. Campuzano G., Obreque C., Aguayo M. M. Accelerating the Miller—Tucker—Zemlin Model for the Asymmetric Traveling Salesman Problem // Expert Systems with Applications. 2020. Vol. 148. P. 113229.

20. Miller C. E., Tucker A. W., Zemlin R. A. Integer Programming Formulations and Traveling Salesman Problems // Journal of the Assoc. Comput., Mach. 1960. Vol. 7. P. 326—329.

21. John K. K. Integer Programming: Theory and Practice, N. Y.: CRC Press, 2006. 336 p.

22. Шевченко В. Н., Золотых Н. Ю. Линейное и целочисленное линейное программирование. Нижний Новгород: Изд-во НГУ им. Н. И. Лобачевского, 2004. 154 с.

23. Савельев М. В., Енгибарян И. А. Решение задач целочисленного программирования на основе генетических алгоритмов // Известия вузов. Северо-кавказский регион естественные науки. Приложение. 2005. № 9. С. 18—21.

24. Liu Y., Li H., Chen H. A Genetic Algorithm for Sol ving Linear Integer Bilevel Programming Problems // 2018 14th International Conference on Computational Intelligence and Security (CIS). Hangzhou, China. 2018. P. 40—44.

25. Liu Y., Liu Z., Shi J., Wu G., Chen C. Optimization of Base Location and Patrol Routes for Unmanned Aerial Vehicles in Border Intelligence, Surveillance and Reconnaissance // Journal of Advanced Transportation. 2019. Vol. 2019(6). P. 1—13.

26. Филимонов А. Б., Нгуен Т. К. Патрулирование протяженных территорий беспилотными летательными аппаратами // Теоретические и практические аспекты развития современной науки: теория, методология, практика. Сб. науч. статей по материалам X Междунар. науч.-практ. конф. Уфа: Вестник науки, 2023. С. 25—34.

27. Фам К. Ф. Оптимизация генетическим алгоритмом маршрутов полета при групповом пограничном патрулировании // Journal of Advanced Research in Technical Science. 2024. Iss. 40. P. 28—35.