Traveling salesman problems (TSPs) are well-known combinatorial optimization problems, and most existing algorithms are challenging for solving TSPs when its scale is large. To improve the efficiency of solving large-scale TSPs, this work presents a novel adaptive layered clustering framework with improved genetic algorithm (ALC_IGA). The primary idea behind ALC_IGA is to break down a large-scale problem into a series of small-scale problems. First, the k-means and improved genetic algorithm are used to segment the large-scale TSPs layer by layer and generate the initial solution. Then, the developed two phases simplified $2$-opt algorithm is applied to further improve the quality of the initial solution. The analysis reveals that the computational complexity of the ALC_IGA is between O(nlog n) and O(n²). The results of numerical experiments on various TSP instances indicate that, in most situations, the ALC_IGA surpasses the state-of-the-art algorithms in convergence speed, stability, and solution quality. Specifically, the ALC_IGA can solve instances with 2 × 10⁵ nodes within 0.15h, 1.4 × 10⁶ nodes within 1h, and 2 × 10⁶ nodes in three dimensions within 1.5h.
No takes yet. Share an insight, caveat, or question.
Xu et al. (2023) studied this question.