Using K-means Radius Particle Swarm Optimization for the Travelling Salesman Problem

ABSTRACT

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.

Keywords:

• Clustering
• Particle swarm optimization
• Radius particle swarm optimization
• The travelling salesman problem

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Notes on contributors

M. Anantathanavit

M. Anantathanavit received Master of Science degree in 2011 from Ramkhamhaeng University, Thailand. Currently he is a PhD candidate at the Faculty of Information Science and Technology, Mahanakorn University of Technology (MUT), Thailand. His research interests are metaheuristic and optimization algorithm.

E-mail: [email protected].

M. Munlin

M. Munlin is Assistant Professor at the Faculty of Information Science and Technology, Mahanakorn University of Technology (MUT), Thailand. He obtained his Bachelor degree in Physics from the Prince of Songkla University, Thailand and Ph.D. in Computer Science from the School of Computer Studies, University of Leeds, UK. He teaches several courses in Computer Science. His research area is advanced optimization algorithms, CAD/CAM, solid modelling, five-axis CNC, computer graphics, and computer vision.

E-mail: [email protected].