Optimizing tabu list size for the traveling salesman problem

Optimizing tabu list size for the traveling salesman problem

0.00 Avg rating0 Votes
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: ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.