Using K-means Radius Particle Swarm Optimization for the Travelling Salesman Problem
Mana Anantathanavit, Mud-Armeen Munlin · IETE Technical Review · 2015
The travelling salesman problem (TSP) is a well-known established scheduling problem. We propose a novel method to solve the TSP using the divide-and-conquer strategy. We employ K-means to cluster the sub-cities and then solve a sequence of sub-cities in a given order and merge them by the radius particle swarm optimization (RPSO). The RPSO incorporates adaptive mutation to avoid the impact of the bound of the solution. In addition, a local search procedure is embedded into the RPSO to accelerate the convergence and improve the solution. The performance of our proposed method is tested on a number of instances from the travelling salesman problem library (TSPLIB). Computational results and comparisons have demonstrated the effectiveness of the method.