Using k-means clustering to improve the efficiency of ant colony optimization for the traveling salesman problem

Ant colony optimization (ACO) is a quite mature optimization algorithm for combinational problems, but it still attracts many researchers trying to raise its efficiency and/or performance. Some of them endeavor to speed up or improve ACO by choosing more suitable parameters of iteration or update formulas. This work tries to introduce k-means clustering to enhance the efficiency of ACO for the traveling salesman problem. First, the city locations are clustered into two or more groups according to k-means clustering. Second, ACO is separately applied to these groups of cities. Finally, an appropriate connection technique is used to join these groups; every two groups are connected until all groups are connected into a single route. Experimental results show that the computational cost of multiple groups divided by k-means clustering can be reduced to below 32 percent of the time run by the original group, and even multiple groups contribute to raising the performance in a particular distribution of cities.