Solving the traveling salesman problem with annealing-based heuristics: a computational study
IEEE Transactions on Systems Man and Cybernetics - Part A Systems and HumansPublished 1 January 2002
Joshua W. Pepper, Bruce Golden, Edward Wasil
Citations100
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper conducts an extensive computational study of 11 annealing-based heuristics for the traveling salesman problem, applying each heuristic to 29 traveling salesman problems taken from a well-known online library, and comparing the results with respect to accuracy and running time.
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
Computer Science
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
Modern heuristic techniques for combinatorial problems
2,623 Citations1993Colin R. Reeves
This chapter discusses combinatorial problems local and global optima heuristics, the tabu framework, and Evaluation of heuristic performance: analytical methods empirical testing statistical inference conclusions.
INFORMS Journal on ComputingTSPLIB—A Traveling Salesman Problem Library
2,570 Citations1991Gerhard Reinelt
This paper contains the description of a traveling salesman problem library (TSPLIB) which is meant to provide researchers with a broad set of test problems from various sources and with various properties.
Bell System Technical JournalComputer Solutions of the Traveling Salesman Problem
1,960 Citations1965Shen Lin
Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer and are based on a general heuristic approach believed to be of general applicability to various optimization problems.
Operations ResearchOptimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
1,468 Citations1989David S. Johnson, C. Aragon +2 more
This paper discusses annealing and its parameterized generic implementation, describes how this generic algorithm was adapted to the graph partitioning problem, and reports how well it compared to standard algorithms like the Kernighan-Lin algorithm.
Journal of Computational PhysicsThreshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing
1,245 Citations1990Gunter Dueck, Tobias Scheuer
A new general purpose algorithm for the solution of combinatorial optimization problems is presented, even simpler structured than the wellknown simulated annealing approach, and deterministic versions of the new heuristic turn out to perform nearly equally well.
Journal of Computational PhysicsNew Optimization Heuristics
743 Citations1993Gunter Dueck
The quality of the computational results obtained so far by RRT and GDA shows that the new algorithms behave equally well as TA and thus a fortiori better than SA.
Physical Review LettersMicrocanonical Monte Carlo Simulation
570 Citations1983Michael Creutz
A new algorithm for the simulation of statistical systems that produces a random walk through configurations of a constant total energy and is applicable to systems of both discrete and continuous variables.
Journal of HeuristicsDesigning and reporting on computational experiments with heuristic methods
442 Citations1995Richard S. Barr, Bruce Golden +3 more
The design of computational experiments to test heuristic methods and reporting guidelines for such experimentation are discussed and the goal is to promote thoughtful, well-planned, and extensive testing of heuristics and integrity in and reproducibility of the reported results.
Operations ResearchThe Traveling Salesman Problem: A Survey
404 Citations1968Mandell Bellmore, George L. Nemhauser
A survey and synthesis of research on the traveling salesman problem is given and a general classification of the solution techniques and a detailed description of some of the proven methods are given.
Handbooks in operations research and management scienceChapter 4 The traveling salesman problem
218 Citations1995Michael Jünger, Gerhard Reinelt +1 more
This chapter presents a self-contained introduction into algorithmic and computational aspects of the traveling salesman problem along with their theoretical prerequisites as seen from the point of view of an operations researcher who wants to solve practical instances.
MetaheuristicsMeta-Heuristics: An Overview
132 Citations1996Ibrahim H. Osman, James P. Kelly
The paper shall present brief overviews for the most successful meta-heuristics, and concludes with future directions in this growing area of research.
INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGYTraveling Salesman Problem: A Case Study
45 Citations2012Leena Jain, Mr. Amit Bhanot
This linear problem solved by open source software is presented for solving traveling salesman problem and assignment based integer linear formulation presented.
IEEE Transactions on Systems Man and Cybernetics - Part A Systems and HumansSee the forest before the trees: fine-tuned learning and its application to the traveling salesman problem
26 Citations1998Steven P. Coy, Bruce Golden +2 more
An extensive computational experiment is conducted to study the performance of fine-tuned-learning-based heuristics for the traveling salesman problem and concludes that it is a meritorious concept that deserves serious consideration by researchers solving difficult problems.
European Journal of Operational ResearchA computational study of smoothing heuristics for the traveling salesman problem
20 Citations2000Steven P. Coy, Bruce Golden +1 more
An extensive computational study is conducted to test the performance of eight smoothing heuristics for the traveling salesman problem and compares the solutions generated by the heuristic and provides insight into the behavior of the smoothingHeuristics.
Demon algorithms and their application to optimization problems
9 Citations2002Ian Wood, T. Downs
Four new general optimization algorithms based on the 'demon' algorithm from statistical physics and the simulated annealing (SA) optimization method are introduced that reduce the computation time per trial without significant effect on the quality of solutions found.
QUT ePrints (Queensland University of Technology)Fast optimization by Demon Algorithms
4 Citations1998Ian Wood, Dennis Tom
Four new general optimization algorithms based on the `demon' algorithm from statistical physics and the simulated annealing (SA) optimization method are introduced, which use a computationally simpler acceptance function, but can use any SAAnnealing schedule or move generation function.