novtexmechМехатроника, автоматизация, управлениеMekhatronika, Avtomatizatsiya, Upravlenie1684-64272619-1253Commercial Publisher «New Technologies»10.17587/mau.24.374-381novtexmech-1408Research ArticleДИНАМИКА, БАЛЛИСТИКА И УПРАВЛЕНИЕ ДВИЖЕНИЕМ ЛЕТАТЕЛЬНЫХ АППАРАТОВDYNAMICS, BALLISTICS AND CONTROL OF AIRCRAFTПланирование маршрутов полета БПЛА в задачах группового патрулирования протяженных территорийPlanning of UAV Flight Routes in the Problems of Group Patrolling of the Extended TerritoriesФилимоновА. Б.FilimonovA. B.

д-р техн. наук, проф.

Москва

Moscow, 119454

filimon_ab@mail.ruФилимоновН. Б.FilimonovN. B.

д-р техн. наук, проф.

Москва

Filimonov Nikolay B., Professor, Dr. Sc. Tech.

Moscow, 119991

nbfilimonov@mail.ruНгуенТ. К.NguyenТ. К.

аспирант

Москва

Moscow, 119454

congvietnam@mail.ruФамК. Ф.PhamQ. P.

студент

Москва

Moscow, 105005

hvktqs1421996@gmail.comМИРЭА — Российский технологический университет; Московский авиационный институт (научно-исследовательский университет)РоссияMIREA — Russian Technological University; Moscow Aviation Institute (National Research University)Russian FederationМосковский государственный университет им. М. В. Ломоносова; Московский государственный технический университет им. Н. Э. БауманаРоссияLomonosov Moscow State University; Bauman Moscow State Technical UniversityRussian FederationМИРЭА — Российский технологический университетРоссияMIREA — Russian Technological UniversityRussian FederationМосковский государственный технический университет им. Н. Э. БауманаРоссияBauman Moscow State Technical UniversityRussian Federation202309072023247374381Copyright © Commercial Publisher «New Technologies», 20232023Commercial Publisher «New Technologies»Commercial Publisher «New Technologies»https://mech.novtex.ru/jour/about/submissions#copyrightNoticehttps://mech.novtex.ru/jour/article/view/1408

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

Currently one of the promising areas of joint use of unmanned aerial vehicles (UAVs) is group air patrolling of large territories. Here the organization of patrolling assumes the solving the planning problem of routes flight of UAV group. The paper considers the problem of optimal planning of flight routes of the same type of UAVs during group patrolling of large territories. The territorial waters or narrow border areas of any State may serve as an example of such territories. It is suggested that the patrolled area has an elongated shape and is divided into a chain of adjacent patrol zones prescribed by a separate UAV. The drone’s flight route passes through adjacent zones. The flight task performed periodically by each drone consists in moving it to a given flight zone, collecting operational data and transmitting this data to a control point (center, station). The optimization aspect of UAV flight route planning is to minimize the maximum time required to complete flight tasks. The considered problem of group patrolling reduced to the multiple traveling salesman problem — one of the classic intractable combinatorial optimization problems. A brief analysis of modern methods for solving the multiple traveling salesman problem is given. Due to the lack of effective exact methods for solving this problem, it is natural to use approximate heuristic and metaheuristic methods focused on solving NP-hard optimization problems, reducing the full search and giving a solution close to the exact one. The multiple traveling salesman problem considered in this paper is reduced to the problem of integer linear programming, for the solution of which a genetic algorithm implemented in MATLAB based on the mathematical package Global Optimization Toolbox is proposed. An illustrative example of patrolling by three UAVs of an extended territory with 11 adjacent zones is considered. Computational experiments confirm the effectiveness of the algorithmic solutions proposed in the work.

группа БПЛАпатрулированиепланирование маршрутов полетацелочисленное линейное про- граммированиегенетический алгоритмсреда программирования MATLABUAV grouppatrollingflight routes planninginteger linear programminggenetic algorithmMATLAB programming environmentReferencesКузнецов Г. А., Кудрявцев И. В., Крылов Е. Д. Ретроспективный анализ, современное состояние и тенденции развития отечественных беспилотных летательных аппаратов // Инженерный журнал: наука и инновации. 2018. № 9 (81). С. 1—22.Kuznetsov G. A., Kudryavtsev I. V., Krylov E. D. Retrospective analysis, current state and development trends of domestic unmanned aerial vehicles, Engineering Journal: Science and Innovation, 2018, no.9 (81), pp. 1—22 (in Russian).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.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, pp. 229—255.Филимонов А. Б., Филимонов Н. Б. Оптимальная маршрутизация полетов БПЛА при групповом патрулировании территорий // Journal of Advanced Research in Technical Science. 2023. Iss. 34. P. 49—55.Filimonov A. B., Filimonov N. B. Optimal Routing by UAV Flights in Group Patrolling of the Territory, Journal of Advanced Research in Technical Science, 2023, iss. 34, pp. 49—55 (in Russian).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.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, pp. 776—786.Ченцов А. Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. Москва-Ижевск: РХД, 2008. 238 c.Chentsov A. G. Extreme problems of routing and assignment distribution: questions of theory, Moscow-Izhevsk, RCD, 2008, 238 p. (in Russian)Садыков М. Ф., Горячев М. П. Система воздушного патрулирования и управления транспортными потоками // Вестник НЦ БЖД. 2017. № 1 (31). С. 59—65.Sadykov M. F., Goryachev M. P. The system of air patrol and traffic flow management, Bulletin of the National Railways, 2017, no. 1 (31), pp. 59—65 (in Russian).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.Manyam S. G., Rasmussen S., Casbeer D. W., Kalyanam K., Manickam S. Multi-UAV Routing for Persistent Intelligence Surveillance & Reconnaissance Missions, 2017 Internat. Conf. on Unmanned Aircraft Systems (ICUAS), 2017, pp. 573—580.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.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, pp. 1—13.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.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, pp. 499—515.Вилков В. Б., Горшкова Е. Е., Черных А. К. Решение задачи нахождения оптимального маршрута патрулирования действующих лесных пожаров в заданном районе // Вестник СПб ун-та ГПС МЧС России. 2021. № 3. С. 90—98.Vilkov V. B., Gorshkova E. E., Chernykh A. K. The solution of the problem of finding the optimal route for patrolling existing forest fires in a given area, Bulletin of the St Petersburg University GPS of the Ministry of Emergency Situations of Russia, 2021, no. 3, pp. 90—98 (in Russian).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.Chen Y., Shu Y., Hu M., Zhao X. Multi-UAV Cooperative Path Planning with Monitoring Privacy Preservation, Applied Sciences, 2022, vol. 12, no. 23, pp. 1—16.Иванов С. В. Методика построения субоптимальных маршрутов для группы беспилотных летательных аппаратов на основе биоинспирированных алгоритмов при наличии препятствий // Системы управления, связи и безопасности. 2022. № 2. С. 1—23.Ivanov S. V. Methodology for constructing suboptimal routes for a group of unmanned aerial vehicles based on bioinspired algorithms in the presence of obstacles, Control systems, communications and security, 2022, no. 2, pp. 1—23 (in Russian).Меламед И. И., Сергеев С. И., Сигал И. Х. Задача коммивояжера. I-III // Автоматика и телемеханика. 1989. № 9. С. 3—34; № 10. С.3—29; № 11. С. 3—26.Melamed I. I., Sergeev S. I., Sigal I. H. The traveling salesman’s task. I-III, Automation and Telemechanics, 1989, no. 9, pp. 3—34; no. 10, pp. 3—29; no. 11, pp. 3—26 (in Russian).Bektas T. The multiple traveling salesman problem: an overview of formulations and solution procedures // Omega. 2006. Vol. 34, N. 3. P. 209—219.Bektas T. The multiple traveling salesman problem: an overview of formulations and solution procedures, Omega, 2006, vol. 34, no. 3, pp. 209—219.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.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.Oberlin P. Rathinam S., Darbha S. Today’s Traveling Salesman Problem // IEEE Robotics & Automation Magazine. IEEE. 2010. Vol. 17, N. 4. P. 70—77.Oberlin P. Rathinam S., Darbha S. Today’s Traveling Salesman Problem, IEEE Robotics & Automation Magazine, IEEE, 2010, vol. 17, no. 4, pp. 70—77.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.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, pp. 1—24.Traveling salesman problem, theory and applications / Ed. D. Davendra. Intech Open, 2010. 338 p.Davendra D. ed. Traveling salesman problem, theory and applications, Intech Open, 2010, 338 p.Курейчик В. М., Лагунова Ю. А. Задачи о коммивояжере. Обзор и методы решения. Palmarium Academic Publishing, 2019. 60 cKureychik V. M., Lagunova Yu. A. Problems about a traveling salesman. Overview and solution methods, Palmarium Academic Publishing, 2019, 60 p. (in Russian).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.Cheikhrouhou O., Khoufi I. A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy, Comput. Sci. Rev., 2021, vol. 40, no. 100369, pp. 76.Discrete Optimization. The State of the Art / Ed. E. Boros, P. L. Hammer. Boston: Elsevier, 2005. 607 p.Boros E., Hammer P. L. ed. Discrete Optimization. The State of the Art, Boston, Elsevier, 2005, 607 p.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.Karp R. M. Reducibility among combinatorial problems, Complexity of Computer Computations, R. E. Miller, J. W. Thatcher Eds., Plenum Press, N. Y. and London, Springer, 1972, pp. 85—103.Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979. 338 p.Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, 1979, 338 p.Blum C., Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison // ACM Computing Surveys. 2003. Vol. 35, N. 3. P. 268—308.Blum C., Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison, ACM Computing Surveys, 2003, vol. 35, no. 3, pp. 268—308.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.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, pp. 776—786.Handbook of Metaheuristics (Vol. 146 of International Series in Operations Research & Management Science). N. Y.: Springer, 2010. 648 p.Handbook of Metaheuristics (Vol. 146 of International Series in Operations Research & Management Science), N. Y., Springer, 2010, 648 p.Yousefikhoshbakht M. Solving the Traveling Salesman Problem: A Modified Metaheuristic Algorithm // Complexity. Hindawi. 2021. Vol. 2021, February. P. 1—13.Yousefikhoshbakht M. Solving the Traveling Salesman Problem: A Modified Metaheuristic Algorithm, Complexity. Hindawi, 2021, vol. 2021, February, pp. 1—13.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.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, pp. 839—844.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.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, no. 1, pp. 246—257.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.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, no. 1, pp. 95—101.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.Kiraly A., Abonyi J. Optimization of MTSP by a Novel Representation Based Genetic Algorithm, Intelligent Computational Optimization in Engineering. Studies in Computational Intelligence, K@ppen M., Schaefer G., Abraham A. (eds), 2011, vol. 366, Berlin, Springer, pp. 241—269.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.Sedighpour M., Yousefikhoshbakht M., Mahmoodi D. N. An Effective Genetic Algorithm for Solving the MTSP, Journal of Optimization in Industrial Engineering, 2012, vol. 8, pp. 73—79.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.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, no. 1, pp. 72—82.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.Kaliaperumal R., Ramalingam A., Sripriya J. A modified two part chromosome crossover for solving MTSP using genetic algorithms, Proceedings of ICARCSET. N. Y., 2015, pp. 1—4.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.Bolaños R. I., Toro O. E. M., Mauricio G. E. A population- based algorithm for the MTSP, Internat. Journal of Industrial Engineering Computayions, 2016, vol. 7, pp. 245—256.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.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, no. 2, pp. 491—503.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.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, pp. 326—329.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.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.John K. K. Integer programming: theory and practice. N. Y.: CRC Press, 2006. 336 p.John K. K. Integer programming: theory and practice, N. Y., CRC Press, 2006, 336 p.

The authors declare that there are no conflicts of interest present.