In this study, we focus on the path-planning problem of unmanned aerial vehicles (UAVs) deployed for inspection missions at target points. The goal is to visit each target point, provide revisits to important target points, and ultimately meet the monitoring requirements with regular and stable monitoring frequencies. Herein, we present MTSP-R, a novel variant of the multiple traveling salesmen problem (MTSP), in which revisits to important target points are allowed. We address the path-planning problem of multi-UAV in two stages. First, we propose a nearest insertion algorithm with revisits (NIA-R) to determine the number of required UAVs and initial inspection paths. We then propose an improved genetic algorithm (IGA) with two-part chromosome encoding to further optimize the inspection paths of the UAVs. The simulation results demonstrate that the IGA can effectively overcome the shortcomings of the original genetic algorithm, providing shorter paths for multiple UAVs and more stable monitoring frequencies for the target points.

1. [1] P. Stockel, P. Wallrath, R. Herschel, and N. Pohl, “Detection and monitoring of people in collapsed buildings using a rotating radar on a UAV,” IEEE Trans. on Radar Systems, Vol.2, pp. 13-23, 2024. https://doi.org/10.1109/TRS.2023.3342368
2. [2] Y. Wan, Y. Zhong, A. Ma, and L. Zhang, “An accurate UAV 3-D path planning method for disaster emergency response based on an improved multiobjective swarm intelligence algorithm,” IEEE Trans. on Cybernetics, Vol.53, No.4, pp. 2658-2671, 2023. https://doi.org/10.1109/TCYB.2022.3170580
3. [3] R. G. Ribeiro, L. P. Cota, T. A. M. Euzébio, J. A. Ramírez, and F. G. Guimarães, “Unmanned-aerial-vehicle routing problem with mobile charging stations for assisting search and rescue missions in postdisaster scenarios,” IEEE Trans. on Systems, Man, and Cybernetics: Systems, Vol.52, No.11, pp. 6682-6696, 2022. https://doi.org/10.1109/TSMC.2021.3088776
4. [4] H. Zhang, L. Dou, B. Xin, R. Zhang, and Q. Wang, “Reconnaissance and confirmation task planning of multiple fixed-wing UAVs with specific payloads: A comparison study,” J. Adv. Comput. Intell. Intell. Inform., Vol.26, No.4, pp. 570-580, 2022. https://doi.org/10.20965/jaciii.2022.p0570
5. [5] K. Harikumar, J. Senthilnath, and S. Sundaram, “Multi-UAV Oxyrrhis Marina-inspired search and dynamic formation control for forest firefighting,” IEEE Trans. on Automation Science and Engineering, Vol.16, No.2, pp. 863-873, 2019. https://doi.org/10.1109/TASE.2018.2867614
6. [6] B. Wang, B. Xin, Y. Ding, and Y. Li, “Research on the messenger UAV mission planning based on sampling transformation algorithm,” J. Adv. Comput. Intell. Intell. Inform., Vol.28, No.3, pp. 475-483, 2024. https://doi.org/10.20965/jaciii.2024.p0475
7. [7] Z. Xin, J. Li, J. Li, and C. Liu, “Collaborative search and package delivery strategy for UAV swarms under area restrictions,” J. Adv. Comput. Intell. Intell. Inform., Vol.27, No.5, pp. 932-941, 2023. https://doi.org/10.20965/jaciii.2023.p0932
8. [8] W. Wu, J. Xu, and Y. Sun, “Integrate assignment of multiple heterogeneous unmanned aerial vehicles performing dynamic disaster inspection and validation task with Dubins path,” IEEE Trans. on Aerospace and Electronic Systems, Vol.59, No.4, pp. 4018-4032, 2023. https://doi.org/10.1109/TAES.2023.3235864
9. [9] S. Rajan, K. Sundar, and N. Gautam, “Routing problem for unmanned aerial vehicle patrolling missions – A progressive hedging algorithm,” Computers & Operations Research, Vol.142, Article No.105702, 2022. https://doi.org/10.1016/j.cor.2022.105702
10. [10] J. Li, Y. Xiong, J. She, and M. Wu, “A path planning method for sweep coverage with multiple UAVs,” IEEE Internet of Things J., Vol.7, No.9, pp. 8967-8978, 2020. https://doi.org/10.1109/JIOT.2020.2999083
11. [11] N. Bartolini, A. Coletta, G. Maselli, and A. Khalifeh, “A multi-trip task assignment for early target inspection in squads of aerial drones,” IEEE Trans. on Mobile Computing, Vol.20, No.11, pp. 3099-3116, 2021. https://doi.org/10.1109/TMC.2020.2994529
12. [12] W. Wang, C. Fang, and T. Liu, “Multiperiod unmanned aerial vehicles path planning with dynamic emergency priorities for geohazards monitoring,” IEEE Trans. on Industrial Informatics, Vol.18, No.12, pp. 8851-8859, 2022. https://doi.org/10.1109/TII.2022.3153031
13. [13] J. Li, X. Liu, G. Han, S. Cao, and X. Wang, “TaskPOI priority-based energy balanced multi-UAVs cooperative trajectory planning algorithm in 6G networks,” IEEE Trans. on Green Communications and Networking, Vol.7, No.2, pp. 1052-1065, 2023. https://doi.org/10.1109/TGCN.2022.3187097
14. [14] Q. Guo, W. Xu, J. Peng, H. Li, and Z. Xiang, “Persistent monitoring for points of interests with different priorities using multiple UAVs,” 2022 IEEE 28th Int. Conf. on Parallel and Distributed Systems (ICPADS), pp. 427-434, 2023. https://doi.org/10.1109/ICPADS56603.2022.00062
15. [15] Y. Shu, Y. Chen, M. Hu, H. Wu, and X. Zhao, “UAV path planning based on simultaneous optimization of monitoring frequency and security,” 2022 34th Chinese Control and Decision Conf. (CCDC), pp. 3808-3814, 2022. https://doi.org/10.1109/CCDC55256.2022.10033575
16. [16] L. Feng and J. Katupitiya, “UAV-based persistent full area coverage with dynamic priorities,” Robotics and Autonomous Systems, Vol.157, Article No.104244, 2022. https://doi.org/10.1016/j.robot.2022.104244
17. [17] Y. Shao and X. Xu, “Three-dimensional multi-UAV trajectory design for cooperative video inspection and uploading,” IEEE Trans. on Vehicular Technology, Vol.72, No.10, pp. 13547-13558, 2023. https://doi.org/10.1109/TVT.2023.3277482
18. [18] C. Liu, Y. Guo, N. Li, B. Zhou, and W. Zhao, “Multiuser oriented multi-UAV mission assignment with cooperative information sharing,” IEEE Wireless Communications Letters, Vol.10, No.4, pp. 907-911, 2021. https://doi.org/10.1109/LWC.2020.3041707
19. [19] D. Scott, S. G. Manyam, D. W. Casbeer, and M. Kumar, “A Lagrangian algorithm for multiple depot traveling salesman problem with revisit period constraints,” IEEE Trans. on Automation Science and Engineering, Vol.20, No.1, pp. 690-702, 2023. https://doi.org/10.1109/TASE.2022.3181512
20. [20] P. Bouman, N. Agatz, and M. Schmidt, “Dynamic programming approaches for the traveling salesman problem with drone,” Networks, Vol.72, No.4, pp. 528-542, 2018. https://doi.org/10.1002/net.21864
21. [21] M. M. Alipour and S. N. Razavi, “A new local search heuristic based on nearest insertion into the convex hull for solving Euclidean TSP,” Int. J. of Operational Research, Vol.34, No.3, pp. 409-429, 2019. https://doi.org/10.1504/IJOR.2019.098314
22. [22] L. Liu, W. Li, K. Li, and X. Zou, “A coordinated production and transportation scheduling problem with minimum sum of order delivery times,” J. of Heuristics, Vol.26, No.1, pp. 33-58, 2020. https://doi.org/10.1007/s10732-019-09420-1
23. [23] E. O. Asani et al., “A novel insertion solution for the travelling salesman problem,” Computers, Materials & Continua, Vol.79, No.1, pp. 1581-1597, 2024. https://doi.org/10.32604/cmc.2024.047898
24. [24] X.-A. Dou, Q. Yang, P.-L. Xu, X.-D. Gao, and Z.-Y. Lu, “Comparative study on different encoding strategies for multiple traveling salesmen problem,” 2023 IEEE Int. Conf. on Systems, Man, and Cybernetics (SMC), pp. 1437-1442, 2023. https://doi.org/10.1109/SMC53992.2023.10394521
25. [25] J. Xie and J. Chen, “Multiregional coverage path planning for multiple energy constrained UAVs,” IEEE Trans. on Intelligent Transportation Systems, Vol.23, No.10, pp. 17366-17381, 2022. https://doi.org/10.1109/TITS.2022.3160402
26. [26] B. Xin, H. Wang, and M. Li, “Multi-robot cooperative multi-area coverage based on circular coding genetic algorithm,” J. Adv. Comput. Intell. Intell. Inform., Vol.27, No.6, pp. 1183-1191, 2023. https://doi.org/10.20965/jaciii.2023.p1183
27. [27] S. Mahmoudinazlou and C. Kwon, “A hybrid genetic algorithm for the min-max Multiple Traveling Salesman Problem,” Computers & Operations Research, Vol.162, Article No.106455, 2024. https://doi.org/10.1016/j.cor.2023.106455
28. [28] F. Yan, J. Chu, J. Hu, and X. Zhu, “Cooperative task allocation with simultaneous arrival and resource constraint for multi-UAV using a genetic algorithm,” Expert Systems with Applications, Vol.245, Article No.123023, 2024. https://doi.org/10.1016/j.eswa.2023.123023
29. [29] J. Fu, G. Sun, J. Liu, W. Yao, and L. Wu, “On hierarchical multi-UAV Dubins traveling salesman problem paths in a complex obstacle environment,” IEEE Trans. on Cybernetics, Vol.54, No.1, pp. 123-135, 2024. https://doi.org/10.1109/TCYB.2023.3265926
30. [30] S. Han, K. Zhu, M. Zhou, and X. Liu, “Joint deployment optimization and flight trajectory planning for UAV assisted IoT data collection: A bilevel optimization approach,” IEEE Trans. on Intelligent Transportation Systems, Vol.23, No.11, pp. 21492-21504, 2022. https://doi.org/10.1109/TITS.2022.3180288