K-DSA for the multiple traveling salesman problem  

作　　者：TONG Sheng QU Hong XUE Junjie 

机构地区：[1]Air Traffic Control and Navigation College,Air Force Engineering University,Xi’an 710051,China

出　　处：《Journal of Systems Engineering and Electronics》2023年第6期1614-1625,共12页系统工程与电子技术（英文版）

基　　金：the Natural Science Basic Research Program of Shaanxi(2021JQ-368).

摘　　要：Aimed at a multiple traveling salesman problem(MTSP)with multiple depots and closed paths,this paper proposes a k-means clustering donkey and a smuggler algorithm(KDSA).The algorithm first uses the k-means clustering method to divide all cities into several categories based on the center of various samples;the large-scale MTSP is divided into multiple separate traveling salesman problems(TSPs),and the TSP is solved through the DSA.The proposed algorithm adopts a solution strategy of clustering first and then carrying out,which can not only greatly reduce the search space of the algorithm but also make the search space more fully explored so that the optimal solution of the problem can be more quickly obtained.The experimental results from solving several test cases in the TSPLIB database show that compared with other related intelligent algorithms,the K-DSA has good solving performance and computational efficiency in MTSPs of different scales,especially with large-scale MTSP and when the convergence speed is faster;thus,the advantages of this algorithm are more obvious compared to other algorithms.

关 键 词：k-means clustering donkey and smuggler algorithm(DSA) multiple traveling salesman problem(MTSP) multiple depots and closed paths. 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]