Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem. (English) Zbl 0705.90069

Malek, Miroslaw; Guruswamy, Mohan; Pandya, Mihir

Ann. Oper. Res. 21, 59-84 (1989).

Summary: 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 an 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.

MSC:

90C27	Combinatorial optimization
90-08	Computational methods for problems pertaining to operations research and mathematical programming
68W15	Distributed algorithms

Keywords:

search techniques; traveling salesman; simulated annealing; superlinear speedup; tabu search

References:

[1]	S. Kirkpatrick, C.D. Gelatt and M.P. Vechi, Optimization by simulated annealing, Science 220 (May 13, 1983) Number 4598. · Zbl 1225.90162
[2]	F. Glover, Tabu search, Center for Applied Artificial Intelligence, Graduate School of Business, University of Colorado, Boulder, 1988. · Zbl 0930.90083
[3]	E.L. Lawler, J.K. Lenstra and A.H.G. Rimnooy Kan, eds.,The Traveling Salesman Problem (North-Holland, 1985). · Zbl 0563.90075
[4]	R.L. Karg and G.L. Thompson, A heuristic approach to solving travelling-salesman problems, Management Science 10 (1964) 225–247.
[5]	G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, Solution of a large-scale travelling-salesman problem, Operations Research 2 (1954) 393–410.
[6]	N. Christofides and S. Eilon, An algorithm for vehicle dispatching problem, Operational Res. Q. 20 (1969) 309–318.
[7]	P. Krolak, W. Felts and G. Marble, A man-machine approach towards solving the travelling salesman problem, Communications of the Association for Computing Machinery 14 (1971) 327–334. · Zbl 0217.27302
[8]	S. Lin and B.W. Kernighan, An effective heuristic algorithm for the traveling salesman problem, Oper. Res. 21 (1973) 495–516. · Zbl 0256.90038
[9]	R.G. Parker and R.L. Rardin, The traveling salesman problem: an update of research, Naval Research Logistics Quarterly 30 (1983) 69–96. · Zbl 0521.90100
[10]	M. Padberg and G. Rinaldi, Optimization of a 532-city symmetric traveling salesman problem by branch and cut, Operations Research Letters 6, no. 1 (1987) 1–7. · Zbl 0618.90082
[11]	G.E. Hinton and T.J. Sejnowski, Learning and relearning in Boltzmann machines, in:Parallel Distributed Processing, Vol. 1 (MIT Press, 1986).
[12]	M. Held and R.M. Karp, The travelling salesman problem and minimum spanning trees, part I, Operations Research 18 (1970) 1138–1162; Part II, Mathematical Programming 1 (1971) 6–26. · Zbl 0226.90047
[13]	H. Schwetman,PPL Reference Manual, version 1.1 (Microelectronics and Computer Technology Corporation, 1985).
[14]	B.W. Kernighan and D.M. Ritchie,The C Programming Language (Prentice-Hall, 1978). · Zbl 0701.68014
[15]	M. Malek, M. Guruswamy, H. Owens and M. Pandya, A hybrid algorithm technique, Technical Report, Dept. of Computer Sciences, The University of Texas at Austin, TR-89-06, 1989.