А. Б. Филимонов, д-р техн. наук, проф.,
Москва.
Moscow, 119454;
Moscow, 125993.
Н. Б. Филимонов, д-р техн. наук, проф.,
Москва.
Moscow, 119991;
Moscow, 105005.
Т. К. Нгуен, студент,
Москва.
Moscow, 119454.
К. Ф. Фам, студент,
Москва.
Moscow, 105005.
Одной из перспективных сфер совместного использования беспилотных летательных аппаратов (БПЛА) является групповое воздушное патрулирование больших территорий. Важным этапом организации данного процесса является планирование полетов БПЛА. В работе рассматривается задача оптимального планирования маршрутов полета группы БПЛА при патрулировании территорий большой протяженности с несколькими депо — пунктами базирования беспилотников. Примером таких территорий могут служить труднодоступные территориальные воды или узкие приграничные участки (побережье, горные и лесные массивы) какого-либо государства. Предполагается, что патрулируемая территория имеет вытянутую форму и может быть разбита на цепочку смежных зон патрулирования, предписанных отдельным БПЛА. Маршрут полета беспилотника проходит через смежные зоны. Полетное задание, выполняемое периодически каждым беспилотником, состоит в его перемещении в заданную полетную зону, сборе и передаче оперативных данных в пункт управления. Оптимизационный аспект планирования маршрутов полета БПЛА состоит в минимизации максимальной длины маршрута при облете всех патрулируемых зон. Рассматриваемая задача математически формализуется как множественная задача коммивояжера (МЗК) с несколькими депо. Поскольку она относится к классу NP-трудных задач комбинаторной оптимизации, то практический интерес представляют приближенные эвристические и метаэвристические подходы к ее решению. Предлагается метаэвтристический метод решения МЗК с применением генетических алгоритмов. В качестве модельных примеров рассмотрены задачи патрулирования сухопутной и морской границ Вьетнама, решение которых получено в среде MATLAB с использованием математического пакета Global Optimization Toolbox.
One of the promising areas of joint use of unmanned aerial vehicles (UAVs) is the group air patrol of large territories. An important stage in the organization of this process is the planning of UAV flights. The paper considers the problem of optimal planning of flight routes for a group of UAVs when patrolling large-scale territories with several depots based on drones. An example of such territories can be hard-to-reach territorial waters or narrow border areas (coast, mountain and forest masses) of a State. It is assumed that the patrolled area has an elongated shape and can be 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 and transmitting operational data to the control center. The optimization aspect of UAV flight route planning is to minimize the maximum route length when flying over all patrolled zones. The problem under consideration is mathematically formalized as a multiple traveling salesman problem (MZK) with several depots. Since it belongs to the class of NP-hard combinatorial optimization problems, approximate heuristic and metaheuristic approaches to its solution are of practical interest. A metaheutristic method for solving MZK using genetic algorithms is proposed. As model examples, the tasks of patrolling the land and sea borders of Vietnam are considered, the solution of which was obtained in the MATLAB environment using the Global Optimization Toolbox mathematical package.
The authors declare that there are no conflicts of interest present.