The path planning of large-scale Multiple Traveling Salesman Problem (MTSP) is one of the key technologies in multi-UAV cooperative combat.In cooperative search, multiple UAVs set out from the same depot to scout the suspicious targets nearby.To finish the search task as soon as possible, we build a MTSP model and put forward an optimized algorithm, which combines the clustering algorithm with the genetic algorithm.First, the large-scale MTSP is divided into multiple separate TSPs by using the K-means clustering algorithm.Second, we optimize the genetic algorithm, take in the 2-opt algorithm as the optimization operator, redesign the selection operator and the crossover operator, and solve the multiple TSPs separately.Simulations have verified the rationality of the new algorithm.The comparison between the new algorithm and traditional grouping genetic algorithm shows that the new algorithm has higher computational efficiency and can get more reliable results, especially for solving the large-scale MTSP.