The application of tabu search to the symmetric traveling salesman problem

Tabu search is a heuristic search strategy which is used to guide the repeated application of other simple heuristics in the search for optimal or near optimal solutions to combinatorial optimization problems. A key element of tabu search is the tabu list which is used to prevent cycling. The most recent actions of the search, are recorded on the tabu list and is used to prevent the reversal of those actions, if they will not produce better results. This strategy of flexible restrictions combined with various length memory functions allows tabu search to efficiently identify good solutions. This paper describes the application of tabu search to the symmetric traveling salesman problem (TSP). The values of desirable parameter settings are presented along with the methods used to identify them. A comparison based on solution quality and computational efficiency is made between tabu search and other general heuristic search strategies, such as simulated annealing and genetic algorithms.