Planning of UAV Flight Routes in the Problems of Group Patrolling of the Extended Territories

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.

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

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, pp. 229—255.

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

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, pp. 776—786.

5. Chentsov A. G. Extreme problems of routing and assignment distribution: questions of theory, Moscow-Izhevsk, RCD, 2008, 238 p. (in Russian)

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

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

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, pp. 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, pp. 499—515.

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

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

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

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

14. Bektas T. The multiple traveling salesman problem: an overview of formulations and solution procedures, Omega, 2006, vol. 34, no. 3, pp. 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, no. 4, pp. 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, pp. 1—24.

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

19. Kureychik V. M., Lagunova Yu. A. Problems about a traveling salesman. Overview and solution methods, Palmarium Academic Publishing, 2019, 60 p. (in Russian).

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

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

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

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, no. 3, pp. 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, pp. 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, pp. 1—13.

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

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, no. 1, pp. 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, no. 1, pp. 95—101.

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

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, pp. 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, no. 1, pp. 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, pp. 1—4.

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

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