Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem
Annals of Operations ResearchPublished 1 December 1989
Miroslaw Malek, Mohan Guruswamy, Mihir Pandya, Howard Owens
Citations198
SJR quartileQ1
SJR score1.09
SNIP1.62
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
Results indicate that tabu search consistently outperforms simulated annealing with respect to computation time while giving comparable solutions to traveling salesman problem problems.
Abstract
This paper describes serial and parallel implementations of two different search techniques applied to the traveling salesman problem. A novel approach has been taken to parallelize simulated annealing and the results are compared with the traditional annealing algorithm. This approach uses abbreviated cooling schedule and achieves a superlinear speedup. Also a new search technique, called tabu search, has been adapted to execute in a parallel computing environment. Comparison between simulated annealing and tabu search indicate that tabu search consistently outperforms simulated annealing with respect to computation time while giving comparable solutions. Examples include 25, 33, 42, 50, 57, 75 and 100 city problems.
Keywords
Computer ScienceEngineering
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.
Operations ResearchAn Effective Heuristic Algorithm for the Traveling-Salesman Problem
3,797 Citations1973Simon Lin, Brian W. Kernighan
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems.
The Traveling Salesman Problem
1,622 Citations2019Lawrence Snyder, Zuo‐Jun Max Shen
Operations ResearchThe Traveling-Salesman Problem and Minimum Spanning Trees
1,443 Citations1970Michael Held, Richard M. Karp
It is shown that maxπwπ = C* precisely when a certain well-known linear program has an optimal solution in integers.
Solution of a Large-Scale Traveling-Salesman Problem
1,273 Citations2009Vašek Chvátal, William J. Cook +3 more
The RAND Corporation in the early 1950s contained “what may have been the most remarkable group of mathematicians working on optimization ever assembled”: Arrow, Bellman, Dantzig, Flood, Ford, Fulkerson, Gale, Johnson, Nash, Orchard-Hays, Robinson, Shapley, Simon, Wagner, and other household names.
Journal of the Operational Research SocietyAn Algorithm for the Vehicle-dispatching Problem
699 Citations1969N.D. Christofides, Samuel Eilon
The vehicle-scheduling problem involves the design of several vehicle tours to meet a given set of requirements for customers with known locations, subject to a capacity constraint for the vehicles and a distance constraint for vehicles.
Operations Research LettersOptimization of a 532-city symmetric traveling salesman problem by branch and cut
392 Citations1987Manfred Padberg, Giovanni Rinaldi
Management ScienceA Heuristic Approach to Solving Travelling Salesman Problems
210 Citations1964Robert L. Karg, Gerald L. Thompson
A code for solving travelling salesman problem employing heuristic ideas and numerical experience with the code is described as well as weaknesses and strengths of the method.
Communications of the ACMA man-machine approach toward solving the traveling salesman problem
139 Citations1971Patrick D. Krolak, Wayne Felts +1 more
A computer-aided heuristic technique which uses only a modest amount of computer time in real time to solve large point problems and can be taught to inexperienced persons and their results are similar to those of the authors'
Practica Oto-Rhino-LaryngologicaDer Saccus endolymphaticus bei Entzündungsprozessen
129 Citations2009J.P. Secrétan
Naval Research Logistics QuarterlyThe traveling salesman problem: An update of research
37 Citations1983Robert Parker, R. Rardin
This article presents a review of attacks on the traveling salesman problem for problems defined on weighted and unweighted graphs and includes some aspects of nonexact algorithms with major interest confined to the establishment of worst-case bounds.
Administration & SocietyThe Microelectronics and Computer Technology Corporation
33 Citations1989Kathleen M. Buyers, D. R. Palmer
An interim assessment of the Microelectronics and Computer Technology Corporation (MCC) approaches this task from three perspectives: a descriptive review of MCC's origins and development of the National Cooperative Research Act of 1984, an empirical study of what is new and distinctive about MCC and an assessment of its future prospects as a private corporation and as a de facto instrument of U.S. foreign economic policy.
A Hybrid Algorithm Technique
17 Citations1989Miroslaw Malek, Mohan Guruswamy +2 more
This paper describes mixing of simulated annealing and tabu search algorithms into a new hybrid search algorithm applied to the traveling salesman problem and indicates consistently better results.