Adaptive Tabu Search for Traveling Salesman Problems

One of the most intensively studied problems in computational mathematics and combinatorial optimization is the traveling salesman problem (TSP). The TSP is classified and considered as the class of the NP-complete combinatorial optimization problems. By literatures, many algorithms and approaches have been launched to solve such the TSP. However, no current algorithms can provide the exactly optimal solution of the TSP problem. This article proposes the application of adaptive tabu search (ATS), one of the most powerful AI search techniques, to solve the TSP problems. The ATS is tested against ten benchmark real-world TSP problems. Results obtained by the ATS will be compared with those obtained by the genetic algorithms (GA) and the tabu search (TS). As results, the ATS, TS, and GA can provide very satisfactory solutions for all TSP problems. Among them, the ATS outperforms other algorithms. Keywords—Adaptive tabu search, genetic algorithm, tabu search, traveling salesman problem.