Hybrid discrete coati optimization algorithm for solving large-scale multiple traveling salesman problem

The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem and is also categorized as NP-hard problem. The Multiple Traveling Salesmen Problem (MTSP) represents a variant of TSP, which is more complex and holds greater practical significance compared to TSP. MTSP has found widespread applications in various domains such as robotics, transportation, and networking. Similarly, MTSP is a NP-hard problem. The optimization objective of the MTSP is to minimize the sum of the path lengths for all traveling salesmen. To address this issue, this paper a hybrid discrete coati optimization algorithm (HDCOA) is proposed. Initially, a sector division method is employed to pre-allocate city nodes to each salesman. When the number of nodes allocated to each salesman exceeds 150, the K -Nearest Neighbors (KNN) algorithm is introduced to further divide these city nodes into smaller-scale problems. Besides the classical swap, shift, and 2-opt operators used for solving, aiming to overcome the limitation of the basic discrete COA, which is prone to getting trapped in local optima, this paper designs an operator named Destroy and Rebuilding (R&D). This operator achieves escape from local optima by eliminating the longest undirected edge in the path. This paper not only solves the planar MTSP problem with city counts ranging from 51 to 18, 512, but also conducts simulation experiments using 7342 real-world cities on Earth as MTSP cases. The scale of this paper far exceeds that of known literature. Extensive experimental results demonstrate that the proposed algorithm exhibits excellent competitiveness in solving TSP and MTSP. The source code of the algorithm is accessible at https://ww2.mathworks.cn/matlabcentral/fileexchange/178504-hdcoa .