A Comparative Study on Sub-route Merging Ways for Clustering Assisted Ant Colony Optimization to Solve Large-Scale Traveling Salesman Problem

Large-Scale Traveling Salesman Problem (TSP) has remained as a significantly challenging task for swarm intelligent optimization algorithms to solve due to their low effectiveness and efficiency in face of a huge number of cities. Clustering-Assisted Ant Colony Optimization (CA-ACO) has been considered as a promising way to solve large-scale TSP. It divides the cities into a number of clusters by using clustering algorithms and then optimizes the sub-route for each cluster of cities. Finally, it gets the optimal route of the entire TSP by merging all sub-routes. In this way, CA-ACO reduces the time and space complexity significantly and thus could solve large-scale TSP with high efficiency. Particularly, in CA-ACO, how to merge sub-routes makes significant influence on the quality of the complete route of the large-scale TSP. However, few studies have investigated such influence of sub-route merging ways. To fill this gap, this paper provides an in-depth investigation on the impact of different merging methods on the performance of CA-ACO in solving large-scale TSP. To this end, this paper develops six different merging methods, that is, sequential merging, pairwise merging, max-first merging, min-first merging, hierarchical merging, and probabilistic merging. Then, this paper embeds these merging methods into CA-ACO with five classical ACOs, namely Ant System (AS), Elitist AS (EAS), Rank-based AS (RAS), Max-Min AS (MMAS), and Ant Colony System (ACS) to solve large-scale TSP. Experiments conducted on six large-scale TSP instances with different numbers of clusters have demonstrated that the sequential merging method is the most effective one for CA-ACO to address large-scale TSP.