Optimization of UAV Flight Routes during Group Patrolling of Extended Territories as a Multiple Task of a Traveling Salesman with Several Depots
Alexander B. Filimonov, Н. Б. Филимонов, Т. К. Nguyen, Quoc-Hung Pham · Mekhatronika Avtomatizatsiya Upravlenie · 2024
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.