Solving the traveling salesman problem with annealing-based heuristics: a computational study

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 tr...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on systems, man and cybernetics. Part A, Systems and humans man and cybernetics. Part A, Systems and humans, 2002-01, Vol.32 (1), p.72-77
Main Authors: Pepper, J.W., Golden, B.L., Wasil, E.A.
Format: Article
Language:English
Subjects:
Algorithms
Annealing
Computation
Computational modeling
Genetic algorithms
Heuristic
Heuristic algorithms
Libraries
Neural networks
On-line systems
Physics
Running
Simulated annealing
Testing
Traveling salesman problem
Traveling salesman problems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1083-4427
2168-2216
1558-2426
2168-2232
DOI:10.1109/3468.995530