×

A user’s guide to tabu search. (English) Zbl 0772.90063

Summary: We describe the main features of tabu search, emphasizing a perspective for guiding a user to understand basic implementation principles for solving combinatorial or nonlinear problems. We also identify recent developments and extensions that have contributed to increasing the efficiency of the method. One of the useful aspects of tabu search is the ability to adapt a rudimentary prototype implementation to encompass additional model elements, such as new types of constraints and objective functions. Similarly, the method itself can be evolved to varying levels of sophistication. We provide several examples of discrete optimization problems to illustrate the strategic concerns of tabu search, and to show how they may be exploited in various contexts. Our presentation is motivated by the emergence of an extensive literature of computational results, which demonstrates that a well-tuned implementation makes it possible to obtain solutions of high quality for difficult problems, yielding outcomes in some settings that have not been matched by other known techniques.

MSC:

90C27 Combinatorial optimization
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming

Software:

Tabu search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R.E. Burkard, Quadratic assignment problems, Eur. J. Oper. Res. 15(1984)283–289. · Zbl 0526.90064 · doi:10.1016/0377-2217(84)90093-6
[2] J. Chakrapani and J. Skorin-Kapov, Massively parallel tabu search for quadratic assignment problem, Ann. Oper. Res. (1993), this volume. · Zbl 0775.90288
[3] Committee on the Next Decade of Operations Research (Condor), Operations research: The next decade, Oper. Res. 36(1988).
[4] D. Costa, A tabu search algorithm for computing an operational time table, Working Paper, Département de Mathématiques, École Polytechnique Fédérale de Lausanne, Switzerland (1990).
[5] F. Dammeyer and S. Voss, Dynamic tabu list management using the reverse elimination method, Ann. Oper Res. (1993), this volume. · Zbl 0775.90290
[6] C.N. Fiechter, A parallel tabu search algorithm for large scale traveling salesman problems, Working Paper 90/1, Département de Mathématiques, Ècole Polythechnique Fédérale de Lausanne, Switzerland (1990).
[7] G. Finke, R.E. Burkard and F. Rendl, Quadratic assignment problems, Ann. Discr. Math. 31(1987)61–82. · Zbl 0607.90026
[8] A. Frieze, J. Yadegas, S. El-Horbaty and D. Parkinson, Algorithms for assignment problems on an array processor, Parallel Comp. 11(1989)151–162. · Zbl 0678.68023 · doi:10.1016/0167-8191(89)90025-2
[9] B. Gavish, Manifold search techniques applied to the quadratic assignment problem, Technical Report, Owen Graduate School of Management, Vanderbilt University (1991).
[10] M. Gendreau, A. Hertz and G. Laporte, New intersection and post-optimization procedures for the traveling salesman problem, CRT-708, Centre de Recherche sur les Transports, Université de Montréal (1990).
[11] M. Gendreau, A. Hertz and G. Laporte, A tabu search heuristics for the vehicle routing problem, CRT-777, Centre de Recherche sur les Transports, Université de Montréal (1991) to appear in Manag. Sci.
[12] F. Glover, Heuristics for integer programming using surrogate constraints, Dec. Sci. 8(1977)156–166. · doi:10.1111/j.1540-5915.1977.tb01074.x
[13] F. Glover, Future paths for integer programming and links to artificial intelligence, Comp. Oper. Res. 13(1986)533–549. · Zbl 0615.90083 · doi:10.1016/0305-0548(86)90048-1
[14] F. Glover, Tabu search-Part I, ORSA J. Comput. 1(1989)190–206.
[15] F. Glover, Candidate list strategies and tabu search, CAAI Research Report, University of Colorado, Boulder (July 1989).
[16] F. Glover, Tabu search-Part II, ORSA J. Comput. 2(1990)4–32.
[17] F. Glover, Tabu search for nonlinear and parametric optimization (with links to genetic algorithms), Technical Report, Graduate School of Business and Administration, University of Colorado at Boulder (1991), to appear in Discr. Appl. Math.
[18] F. Glover, R. Glover and D. Klingman, The threshold assignment algorithm, Math. Progr. Study 26(1986)12–37. · Zbl 0605.90099
[19] F. Glover, D. Klingman and N. Phillips, A network related nuclear power plant model with an intelligent branch and bound solution approach, Ann. Oper. Res. 21(1990)317–332. · Zbl 0704.90054 · doi:10.1007/BF02022105
[20] P. Hansen, The steepest ascent mildest descent heuristic for combinatorial programming,Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy (1986).
[21] P. Hansen and B. Jaumard, Algorithms for the maximum satisfiability problem, Computing 44(1990)279–303. · Zbl 0716.68077 · doi:10.1007/BF02241270
[22] A. Hertz and D. de Werra, Using tabu search technique for graph coloring, Computing 39(1987)345–451. · Zbl 0626.68051 · doi:10.1007/BF02239976
[23] A. Hertz and D. de Werra, Informatique et Horaires Scolaires, Output 12(1989)53–56.
[24] D. Johnson, Local optimization and the traveling salesman problem,Proc. 17th Annual Colloquim on Automata, Languages and Programming (Springer, 1990) pp. 446–461. · Zbl 0766.90079
[25] J.P. Kelly, B.L. Golden and A.A. Assad, Large-scale controlled rounding using tabu search with strategic oscillation, Ann. Oper. Res. (1993), this volume. · Zbl 0775.90291
[26] J. Knox, The application of tabu search to the symmetric traveling salesman problem, Ph.D. thesis, Graduate School of Business, University of Colorado. · Zbl 0814.90124
[27] A. Kohlen and D. Pesch, Genetic local search in combinatorial optimization, to appear in Discr. Appl. Math. (1991).
[28] M. Laguna, J.W. Barnes and F. Glover, Tabu search methods for a single machine scheduling problem, J. Int. Manufacturing 2(1991)63–74. · doi:10.1007/BF01471219
[29] M. Laguna and F. Glover, Integrating target analysis and tabu search for improved scheduling systems, School of Business, University of Colorado, Boulder (1991), to appear in Expert Systems with Application: An International Journal. · Zbl 0791.68152
[30] S. Lin and B.W. Kernighan, An effective heuristic algorithm for the traveling salesman problem, Oper. Res. 21(1973)498–516. · Zbl 0256.90038 · doi:10.1287/opre.21.2.498
[31] M. Malek, M. Guruswamy, H. Owens and M. Pandya, Serial and parallel search techniques for the traveling salesman problem, Ann. Oper. Res. (1989). · Zbl 0705.90069
[32] E.L. Mooney and R.L. Rardin, Tabu search for a class of scheduling problems, Ann. Oper. Res. (1993), this volume. · Zbl 0775.90237
[33] H. Muhlenbein, Parallel genetic algorithms and combinatorial optimization, to appear in SIAM J. Optim. (1991).
[34] I.H. Osman, Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Ann. Oper. Res. (1993), this volume. · Zbl 0775.90153
[35] P.S. Ow and T.E. Morton, Filtered beam search in scheduling, Int. J. Prod. Res. 26(1988)35–62. · doi:10.1080/00207548808947840
[36] E. Rolland and H. Pirkul, Heuristic search for graph partitioning,31st Joint National TIMS/ORSA Meeting, Nashville, TN (1991). · Zbl 0813.90123
[37] F. Semet and I. Loewenton, The traveling salesman problem under accessibility constraints, Report ORWP 92/02, DMA, EPFL (1992).
[38] F. Semet and E. Taillard, Solving real-life VRPS efficiently using TS, Ann. Oper. Res. (1993), this volume.
[39] J. Skorin-Kapov, Extensions of a tabu search adaptation to the quadratic assignment problem, Harriman School Working Paper HAR-90-006, State University of New York at Stony Brook (1990). · Zbl 0752.90054
[40] E. Taillard, Parallel tabu search for the jobshop scheduling problem, Research Report ORWP 89/11, EPFL, DMA Lausanne, Switzerland (1989).
[41] E. Taillard, Some efficient heuristic methods for the flowshop sequencing problem, Euro. J. Oper. Res. 47(1990)65–79. · Zbl 0702.90043 · doi:10.1016/0377-2217(90)90090-X
[42] E. Taillard, Robust taboo search for the quadratic assignment problem, Parallel Comp. 17(1991)443–455. · doi:10.1016/S0167-8191(05)80147-4
[43] N. Ulder, E, Aarts, H.-J. Bandelt, P. van Laarhoven and E. Pesch, Genetic local search algorithms for the traveling salesman problem,Proc. 1st Int. Workshop on Parallel Problem Solving, ed. Schwefel and Manner, Lecture Notes in Computer Science 496(1991) pp. 109–116.
[44] D. de Werra and A. Hertz, Tabu search tehcniques: A tutorial and an application to neural networks, OR Spectrum (1989)131–141. · Zbl 0672.90089
[45] D. Whitley, T. Starkweather and D. Fuguay, Scheduling problems and traveling salesman: The genetic edge recombinition operator,Proc. 3rd Int. Conf. of Genetic Algorithms, Fairfax, VA (1989).
[46] D.L. Woodruff and E. Zemel, Hashing vectors for tabu search, Ann. Oper. Res. (1993), this volume. · Zbl 0775.90294
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.