Title :
Solving the traveling salesman problem with annealing-based heuristics: a computational study
Author :
Pepper, Joshua W. ; Golden, Bruce L. ; Wasil, Edward A.
Author_Institution :
Mitre Corp., McLean, VA, USA
fDate :
1/1/2002 12:00:00 AM
Abstract :
Recently, several general optimization algorithms based on the demon algorithm from statistical physics have been developed and tested on a few traveling salesman problems with encouraging results. In this paper, we conduct an extensive computational study of 11 annealing-based heuristics for the traveling salesman problem. We code versions of simulated annealing, threshold accepting, record-to-record travel and eight heuristics based on the demon algorithm. We apply each heuristic to 29 traveling salesman problems taken from a well-known online library, compare the results with respect to accuracy and running time and provide insights and suggestions for future work
Keywords :
mathematics computing; simulated annealing; travelling salesman problems; demon algorithm; heuristics; optimization; simulated annealing; threshold accepting; traveling salesman problems; Computational modeling; Genetic algorithms; Helium; Heuristic algorithms; Libraries; Neural networks; Physics; Simulated annealing; Testing; Traveling salesman problems;
Journal_Title :
Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on
DOI :
10.1109/3468.995530
