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

Volume

32

Issue

1

fYear

2002

fDate

1/1/2002 12:00:00 AM

Firstpage

72

Lastpage

77

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;

fLanguage

English

Journal_Title

Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on

Publisher

ieee

ISSN

1083-4427

Type

jour

DOI

10.1109/3468.995530

Filename

995530