Article ID: | iaor1999424 |
Country: | United Kingdom |
Volume: | 25 |
Issue: | 2 |
Start Page Number: | 91 |
End Page Number: | 97 |
Publication Date: | Feb 1998 |
Journal: | Computers and Operations Research |
Authors: | Evans James R., Tsubakitani Shigeru |
Keywords: | heuristics |
We study the problem of optimizing the size of the tabu list when applying tabu search with a short term memory function to the symmetric traveling salesman problem. Two types of local search heuristics are used: the 2-opt and 3-opt heuristics. Fifty test problems of 20, 50, and 100 nodes are generated randomly in the unit square. The sizes of the tabu list tested range from 1 to 150 depending on the problem size and the local search heuristic used. We identified the best tabu list size for each combination of problem size and heuristic within a given computational time limit. This study reveals that good tabu list sizes are smaller than generally believed and that smaller neighborhoods require larger tabu list sizes to be effective.