Optimization of UAV Flight Routes during Group Patrolling of Extended Territories as a Multiple Task of a Traveling Salesman with Several Depots

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.

1. 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).

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, 2019, vol. 2019, p. 13.

3. Melekhin V. B., Hachumov M. V. Planning for an Autonomous Unmanned Aerial Vehicle of Effective Routes to Fly Over Targets, Aviation and Space Instrument Engineering, 2020, no 4, pp. 3—14 (in Russian).

4. Kureychik V. M., Lagunova Yu. A. Problems About a Traveling Salesman. Overview and Solution Methods, Palmarium Academic Publishing, 2019, 60 p. (in Russian).

5. 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, p. 76.

6. 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).

7. Filimonov A. B., Filimonov N. B., Nguyen T. K., Pham Q. P. Planning of UAV Flight Routes in the Problems of Group Patrolling of Extended Territories, Mekhatronika, Avtomatizatsiya, Upravlenie, 2023, vol. 24, no. 7, pp. 374—381 (in Russian).

8. Filimonov A. B., Filimonov N. B. Optimal Routing by UAV Flights in Group Patrolling of the Territory, Journal of Advanced Research in Natural Science, 2023, iss. 19, pp. 1—15 (in Russian).

9. Filimonov A. B., Filimonov N. B. The task of group patrolling of extended territories with multiple depots, Journal of Advanced Research in Technical Science, 2023, iss. 37, pp. 42—51 (in Russian).

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

11. Melamed I. I., Sergeev S. I., Sigal I. K. The Traveling Salesman Problem. Issues in Theory, Autom. Remote Control, 1989, vol. 50, no. 9, pp. 1147—1173 (in Russian).

12. Ho W. A Multi-Depot Travelling Salesman Problem and its Iterative and Integrated Approaches, Int. J. Operational Research. 2006, vol. 1, no. 4, pp. 382—396.

13. Semenov S. S., Pedan A. V., Volovikov V. S., Klimov I. S. Analysis of the complexity of various algorithmic approaches for solving the traveling salesman problem, Control systems, communications and security, 2017, no 1, pp. 116—131 (in Russian).

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, pp. 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, no. 2, pp. 491—503.

16. Kureichik V. M., Logunova J. A. The Genetic Algorithm Application Prospects Analysis for the Traveling Salesman Problem Solution, Informacionnye tehnologii, 2018, vol. 24, no. 11, pp. 691—697 (in Russian).

17. Ghoseiri K., Ghannadpour S. A Hybrid Genetic Algorithm for Multi-Depot Homogenous Locomotive Assignment with Time Windows, Appl. Soft Comput., 2010, vol. 10, pp. 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, pp. 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, pp. 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, pp. 326—329.

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

22. Shevchenko V. N., Zolotykh N. Yu. Linear and Integer Linear Programming, Nizhny Novgorod, Publ. house NGU, 2004, 154 p. (in Russian).

23. Savelyev M. V., Engibaryan I. A. Solving Problems of Integer Programming Based on Genetic Algorithms, Izvestiya vuzov. North Caucasian region natural sciences. Application, 2005, no. 9, pp. 18—21 (in Russian).

24. Liu Y., Li H., Chen H. A Genetic Algorithm for Solving Linear Integer Bilevel Programming Problems, 2018 14th International Conference on Computational Intelligence and Security (CIS), Hangzhou, China, 2018, pp. 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), pp. 1—13.

26. Filimonov A. B., Nguyen T. K. Patrolling of Extended Territories by UAV, In the collection: Theoretical and Practical Aspects of the Development of Modern Science: Theory, Methodology, Practice. articles based on the materials of the X Internat. Scientific and Practical Conf., Ufa, Publ. house of LLC SIC "Bulletin of Science", 2023, pp. 25—34 (in Russian).

27. Pham Q. P. Optimization of UAV Flight Routes for Group Border Patrol Using Genetic Algorithm, Journal of Advanced Research in Technical Science, 2024, iss. 40, pp. 28—35 (in Russian).