Tabu search performance on the symmetric traveling salesman problem

This paper describes tabu search and its application to the symmetric TSP, which is a classic combinatorial optimization problem. The performance of tabu search is compared to the K-OPT procedure using six test problems drawn from the literature. Although K-OPT is not the fastest TSP solution method, it is widely recognized as a performance benchmark. The primary features of both the tabu search and K-OPT computer programs are described. Additional comments about tabu search in general and some factors which influence the performance of tabu search are provided.