HDCOA

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 an 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 an 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 proposes a hybrid discrete coati optimization algorithm (HDCOA). 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 7,342 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..Please cite the associated research paper：Zhu, Lun, et al. "Hybrid discrete coati optimization algorithm for solving large-scale multiple traveling salesman problem." Ain Shams Engineering Journal 16 (2025): 103637.

This algorithm can solve the problem of multiple traveling salesman in 20000 city nodes, and the path diagram of the "d18512" case is shown in the figure.