An Ant Colony Algorithm Based on Multiple-Grain Representation for the Traveling Salesman Problems

Ant colony optimization (ACO) is a population-based metaheuristic technique to effectively solve combination optimization problems. However, it is still an active research topic how to improve the performance of ACO algorithms. Though there are many algorithms to effectively solve traveling salesman problems (TSPs), there is an application bottleneck that the ACO algorithm costs too much time in order to get an optimal solution. To improve the time performance of ACO in solving large scale TSPs, a fast algorithm is presented in this paper. Firstly, a novel multiple-grain representation model of TSPs is proposed. Based on the model, a new algorithm for TSPs is presented, which mainly contains six phases, i.e. a granularity partition algorithm based on density clustering, an ACO algorithm based on the coarse grain，a connection algorithm between two granularities，an ACO algorithm in the same granularity, a fusion algorithm among granularities, and a subsection optimization algorithm regardless of granularities. The analysis of computation complexity and the experimental results for large number of TSPs demonstrate that the proposed algorithm can greatly improve the speed of convergence in contrast to the classical ACO algorithm, and is highly competitive in time performance compared with some latest elitist ACO algorithms.