A Hybrid Algorithm Based on Tabu Search and K-Means for Solving the Traveling Salesman Problem

In this paper, we propose an approach to solve the symmetric Traveling Salesman Problem (TSP) by combining the K-means clustering technique and tabu search (TS). In this hybrid approach, we first apply the K-means algorithm to group cities into several clusters. Then we use tabu search to explore the solution space to optimise the path within each cluster. This avoids getting stuck in local optima and allows us to explore new, potentially better solutions. Finally, to combine the solutions from the different clusters, we apply a recombination technique that randomly selects a cluster from the list of clusters, then calculates the distance between one end of this cluster and the ends of the other clusters. It then chooses the smallest distance between the previously calculated distances, and recombines the two clusters to obtain a new cluster. The operation is repeated until all the clusters have been reunited. The experiments, carried out on instances taken from the TSPLIB library [15, 17], show that the hybrid approach proposed in this way provides a significant improvement in terms of the length of the path travelled and the travel time, compared with methods based solely on K-means or tabu search.