多无人机协同搜索多目标的多旅行商航路规划问题 (MTSP)是无人机协同作战的关键技术之一。在协同搜索背景下, 多架无人机从同一个基地出发搜索附近的可疑目标, 以最快速完成任务为目的, 建立MTSP模型, 提出一种聚类算法和遗传算法进行分步组合的优化算法。第一步, 利用K-means聚类算法将MTSP问题分解成多个独立的TSP问题; 第二步, 改进遗传算法, 引入2-opt算法作为优化算子, 重新设计选择算子和交叉算子, 分别求解多个TSP问题。通过具体算例验证了该算法的合理性, 并同常用的分组遗传算法比较, 分步组合优化算法具有更高的计算效率, 求解结果更为可靠, 尤其在求解大型MTSP问题时, 优势更为明显。

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.