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

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

1. Кузнецов Г. А., Кудрявцев И. В., Крылов Е. Д. Ретроспективный анализ, современное состояние и тенденции развития отечественных беспилотных летательных аппаратов // Инженерный журнал: наука и инновации. 2018. № 9 (81). С. 1—22.

2. Sargolzaei A., Abbaspour A., Crane C. D. Control of Cooperative Unmanned Aerial Vehicles: Review of Applications, Challenges, and Algorithms // Optimization, Learning, and Control for Interdependent Complex Networks. Advances in Intelligent Systems and Computing /Amini M. (eds). 2020. Vol. 1123. Springer, Cham. P. 229—255.

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

4. Kinney G., Hill R., Moore J. Devising a quick-running heuristic for an unmanned aerial vehicle (UAV) routing system // Journal of Operational Research Society. 2004. Vol. 56. P. 776—786.

5. Ченцов А. Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. Москва-Ижевск: РХД, 2008. 238 c.

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

7. Manyam S. G., Rasmussen S., Casbeer D. W., Kalya nam K., Manickam S. Multi-UAV Routing for Persistent Intelligence Surveillance & Reconnaissance Missions // 2017 International Conference on Unmanned Aircraft Systems (ICUAS), 2017. P. 573—580.

8. Liu Y., Zhong 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. Vol. 2019. P. 1—13.

9. Kappel K. S., Cabreira T. M., Marins J. L., de Brisolara L. B., Ferreira P. R. Strategies for Patrolling Missions with Multiple UAVs // Journal of Intelligent & Robotic Systems. 2020. Vol. 99. P. 499—515.

10. Вилков В. Б., Горшкова Е. Е., Черных А. К. Решение задачи нахождения оптимального маршрута патрулирования действующих лесных пожаров в заданном районе // Вестник СПб ун-та ГПС МЧС России. 2021. № 3. С. 90—98.

11. Chen Y., Shu Y., Hu M., Zhao X. Multi-UAV Cooperative Path Planning with Monitoring Privacy Preservation // Applied Sciences. 2022. 12(23). P. 1—16.

12. Иванов С. В. Методика построения субоптимальных маршрутов для группы беспилотных летательных аппаратов на основе биоинспирированных алгоритмов при наличии препятствий // Системы управления, связи и безопасности. 2022. № 2. С. 1—23.

13. Меламед И. И., Сергеев С. И., Сигал И. Х. Задача коммивояжера. I-III // Автоматика и телемеханика. 1989. № 9. С. 3—34; № 10. С.3—29; № 11. С. 3—26.

14. Bektas T. The multiple traveling salesman problem: an overview of formulations and solution procedures // Omega. 2006. Vol. 34, N. 3. P. 209—219.

15. The Traveling Salesman Problem and its Variations. In: Combinatorial Optimization // Algorithms and Combinatorics. Vol. 12. Ed. G. Gutin & A. P. Punnen. Springer US. 2007. 830 p.

16. Oberlin P. Rathinam S., Darbha S. Today’s Traveling Salesman Problem // IEEE Robotics & Automation Magazine. IEEE. 2010. Vol. 17, N. 4. P. 70—77.

17. Matai R., Singh S. P., Mittal M. L. Traveling Salesman Problem: An Over-view of Applications, Formulations, and Solution Approaches // Traveling Salesman Problem, Theory and Applications. 2010. P. 1—24.

18. Traveling salesman problem, theory and applications / Ed. D. Davendra. Intech Open, 2010. 338 p.

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

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

21. Discrete Optimization. The State of the Art / Ed. E. Boros, P. L. Hammer. Boston: Elsevier, 2005. 607 p.

22. Karp R. M. Reducibility among combinatorial problems. In Complexity of Computer Computations / Eds. R. E. Miller, J. W. Thatcher. Plenum Press, N. Y. and London: Springer, 1972. P. 85—103.

23. Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979. 338 p.

24. Blum C., Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison // ACM Computing Surveys. 2003. Vol. 35, N. 3. P. 268—308.

25. Kinney G., Hill R., Moore J. Devising a quick-running heuristic for an unmanned aerial vehicle routing system // Journal of Operational Research Society. 2004. Vol. 56. P. 776—786.

26. Handbook of Metaheuristics (Vol. 146 of International Series in Operations Research & Management Science). N. Y.: Springer, 2010. 648 p.

27. Yousefikhoshbakht M. Solving the Traveling Salesman Problem: A Modified Metaheuristic Algorithm // Complexity. Hindawi. 2021. Vol. 2021, February. P. 1—13.

28. Zhang T., Gruver W. A., Smith M. H. Team scheduling by genetic search // In Proceedings of the second international conference on intelligent processing and manufacturing of materials. 1999. Vol. 2. P. 839—844.

29. Carter A. E., Ragsdale C. T. A new approach to solving the multiple traveling salesperson problem using genetic algorithms // European journal of operational research. 2006. Vol. 175, N. 1. P. 246—257.

30. Singh A., Baghel A. S. A new grouping genetic algorithm approach to the multiple traveling salesperson problem // Soft Computing-A Fusion of Foundations, Methodologies and Applications. 2009. Vol. 13, N. 1. P. 95—101.

31. Kiraly A., Abonyi J. Optimization of MTSP by a Novel Representation Based Genetic Algorithm // K@ppen M., Schaefer G., Abraham A. (eds) Intelligent Computational Optimization in Engineering. Studies in Computational Intelligence, 2011. Vol. 366. Berlin: Springer. P. 241—269.

32. Sedighpour M., Yousefikhoshbakht M., Mahmoodi D. N. An Effective Genetic Algorithm for Solving the MTSP // Journal of Optimization in Industrial Engineering. 2012. Vol. 8. P. 73—79.

33. Yuan S., Skinner B., Huang S., Liu D. A new crossover approach for solving the MTSP using genetic algorithms // European Journal of Operational Research. 2013. Vol. 228, N. 1. P. 72—82.

34. Kaliaperumal R., Ramalingam A., Sripriya J. A modified two part chromosome crossover for solving MTSP using genetic algorithms // Proceedings of ICARCSET. N. Y., 2015. P. 1—4.

35. Bolaños R. I., Toro O. E. M., Mauricio G. E. A populationbased algorithm for the MTSP // Internat. Journal of Industrial Engineering Computayions. 2016. Vol. 7. P. 245—256.

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

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

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

39. John K. K. Integer programming: theory and practice. N. Y.: CRC Press, 2006. 336 p.