Ant colony algorithm for large scale TSP

Abstract

Ant colony algorithm (ACA) has a good solving efficiency to solve the small and medium TSP (Traveling Salesman Problem), but it is difficult to realize overall optimum and takes long time when being applied to large-scale TSP. The paper puts forward self-adaptive DBSCAN (density-based spatial clustering of applications with noise) ACA which can divide the large-scale TSP into several small and medium-scale TSP by local clustering, and then make use of ACA to solve the smaller scale TSP. The experimental result in large-scale TSP indicates the algorithm can improve the convergence rate and reduce the algorithm's dependence on artificial experience.