Abstract
Over the last 15 years, hundreds of papers presenting applications of tabu search, a heuristic method originally proposed by (1986), to various combinatorial problems have appeared in the operations research literature: see, for example, (1997), (1993b), (1996), (2002), (2002) and (1999). In several cases, the methods described provide solutions very close to optimality and are among the most effective, if not the best, to tackle the difficult problems at hand. These successes have made tabu search extremely popular among those interested in finding good solutions to the large combinatorial problems encountered in many practical settings. Several papers, book chapters, special issues and books have surveyed the rich tabu search literature (a list of some of the most important references is provided at the end of this chapter). In spite of this abundant literature, there still seem to be many researchers who, while they are eager to apply tabu search to new problem settings, find it difficult to properly grasp the fundamental concepts of the method, its strengths and its limitations, and to come up with effective implementations. The purpose of this chapter is thus to focus on the fundamental concepts of tabu search.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anderson, E. J., Glass, C. A. and Potts, C. N., 1997, Machine scheduling, in: Local Search in Combinatorial Optimization, E. H. L. Aarts and J. K. Lenstra, eds, Wiley, New York, pp. 361–414.
Battiti, R. and Tecchiolli, G., 1994, The reactive tabu search, ORSA J. Comput. 6:126–140.
Burke, E., De Causmaecker, P. and Vanden Berghe, G., 1999, A hybrid tabu search algorithm for the nurse rostering problem, in: Simulated Evolution and Learning, Selected papers from the 2nd Asia-Pacific Conf. on Simulated Evolution and Learning, SEAL’ 98, B. McKay, X. Yao, C. S. Newton, J.-H. Kim and T. Furuhashi, eds, Lecture Notes in Artificial Intelligence, Vol. 1585, Springer, Berlin, pp. 187–194.
Crainic, T. G. and Gendreau, M., 1999, Towards an evolutionary method—cooperative multi-thread parallel tabu search heuristic hybrid, in: Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, S. Voss, S. Martello, I. H. Osman and C. Roucairol, eds, Kluwer, Dordrecht, pp. 331–344.
Crainic, T. G., Gendreau, M. and Farvolden, J. M., 2000, Simplex-based tabu search for the multicommodity capacitated fixed charge network design problem, INFORMS J. Comput. 12:223–236.
Crainic, T. G., Gendreau, M., Soriano, P. and Toulouse, M., 1993, A tabu search procedure for multicommodity location/allocation with balancing requirements, Ann. Oper. Res. 41:359–383.
Crainic, T. G., Toulouse, M. and Gendreau, M., 1997, Toward a taxonomy of parallel tabu search heuristics, INFORMS J. Comput. 9:61–72.
Cung, V.-D., Martins, S. L., Ribeiro, C. C. and Roucairol, C., 2002, Strategies for the parallel implementation of metaheuristics, in: Essays and Surveys in Metaheuristics, C. C. Ribeiro and P. Hansen, eds, Kluwer, Dordrecht, pp. 263–308.
Dorigo, M., 1992, Optimization, learning and natural algorithms, Ph.D. Dissertation, Departimento di Elettronica, Politecnico di Milano, Italy.
Dueck, G. and Scheuer, T., 1990, Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing, J. Comput. Phys. 90:161–175.
Fleurent, C. and Ferland, J. A., 1996, Genetic and hybrid algorithms for graph colouring, Ann. Oper. Res. 63:437–461.
Friden, C., Hertz, A. and de Werra, D., 1989, STABULUS: A technique for finding stable sets in large graphs with tabu search, Computing 42:35–44.
Gandibleux, X., Jaszkiewicz, A., Freville, A. and Slowinski, R., eds, 2000, J. Heuristics 6:291–431, Special issue: Multiple Objective Metaheuristics.
Gendreau, M., 2002, Recent advances in tabu search, in: Essays and Surveys in Metaheuristics, C. C. Ribeiro and P. Hansen, eds, Kluwer, Dordrecht, pp. 369–377.
Gendreau, M., Guertin, F., Potvin, J.-Y. and Taillard, É. D., 1999, Parallel tabu search for real-time vehicle routing and dispatching, Transport. Sci. 33:381–390.
Gendreau, M., Hertz, A. and Laporte, G., 1994, A tabu search heuristic for the vehicle routing problem, Manage. Sci. 40:1276–1290.
Gendreau, M., Soriano, P. and Salvail, L., 1993, Solving the maximum clique problem using a tabu search approach, Ann. Oper. Res. 41:385–403.
Glover, F., 1977, Heuristics for integer programming using surrogate constraints, Decision Sci. 8:156–166.
Glover, F., 1986, Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res. 13:533–549.
Glover, F., 1989, Tabu search—Part I, ORSA J. Comput. 1:190–206.
Glover, F., 1990, Tabu search—Part II, ORSA J. Comput. 2:4–32.
Glover, F., 1992, Ejection chains, reference structures and alternating path methods for traveling salesman problems, University of Colorado paper, shortened version published in Discr. Appl. Math. 65:223–253, 1996.
Glover, F. and Kochenberger, G. A., eds, 2003, Handbook of Metaheuristics, Kluwer, Boston.
Glover, F. and Laguna, M., 1993, Tabu search, in: Modern Heuristic Techniques for Combinatorial Problems, C. R. Reeves, ed., Blackwell, Oxford, pp. 70–150.
Glover, F. and Laguna, M., 1997, Tabu Search, Kluwer, Boston, MA.
Glover, F., Laguna, M., Taillard, É. D. and de Werra, D., eds, 1993a, Tabu Search, Annals of Operations Research, Vol. 41, Baltzer, Basel.
Glover, F., Taillard, É. D. and de Werra, D., 1993b, A user’s guide to tabu search, Ann. Oper. Res. 41:3–28.
Grünert, T., 2002, Lagrangean tabu search, in: Essays and Surveys in Meta-heuristics, C. C. Ribeiro and P. Hansen, eds, Kluwer, Dordrecht, pp. 379–397.
Hansen, P., 1986, The steepest ascent mildest descent heuristic for combinatorial programming, in: Proceedings of the Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy.
Hertz, A. and de Werra, D, 1987, Using tabu search for graph coloring, Computing 39:345–351.
Hertz, A. and de Werra, D., 1991, The tabu search metaheuristic: how we used it, Ann. Math. Artif. Intell. 1:111–121.
Holland, J. H., 1975, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI.
Kirkpatrick, S., Gelatt Jr., C. D. and Vecchi, M. P., 1983, Optimization by simulated annealing, Science 220:671–680.
Laporte, G. and Osman, I. H., eds, 1996, Metaheuristics in Combinatorial Optimization, Annals of Operations Research, Vol. 63, Baltzer, Basel.
Lokketangen, A. and Glover, F., 1996, Probabilistic move selection in tabu search for 0/1 mixed integer programming problems, in: Meta-Heuristics: Theory and Applications, I. H. Osman and J. P. Kelly, eds, Kluwer, Dordrecht, pp. 467–488.
Lokketangen, A. and Woodruff, D. L., 1996, Progressive hedging and tabu search applied to mixed integer (0, 1) multistage stochastic programming, J. Heuristics 2:111–128.
Nilsson, N. J., 1980, Principles of Artificial Intelligence, Morgan Kaufmann, Los Altos, CA.
Osman, I. H. and Kelly, J. P., eds, 1996, Meta-Heuristics: Theory and Applications, Kluwer, Boston, MA.
Pardalos, P. M. and Resende, M. G. C., eds, 2002, Handbook of Applied Optimization, Oxford University Press, New York.
Pesant, G. and Gendreau, M., 1999, A constraint programming framework for local search methods, J. Heuristics 5:255–280.
Ribeiro, C. C. and Hansen, P., eds, 2002, Essays and Surveys in Metaheuristics, Kluwer, Norwell, MA.
Rochat, Y. and Taillard, É. D., 1995, Probabilistic diversification and intensification in local search for vehicle routing, J. Heuristics 1:147–167.
Rolland, E., 1996, A tabu search method for constrained real-number search: applications to portfolio selection, Working Paper, The Gary Anderson Graduate School of Management, University of California, Riverside.
Skorin-Kapov, J., 1990, Tabu search applied to the quadratic assignment problem, ORSA J. Comput. 2:33–45.
Soriano, P. and Gendreau, M., 1996, Diversification strategies in tabu search algorithms for the maximum clique problems, Ann. Oper. Res. 63:189–207.
Soriano, P. and Gendreau, M., 1997, Fondements et applications des méthodes de recherche avec tabous, RAIRO (Recherche opérationnelle) 31:133–159.
Taillard, É. D., 1990, Some efficient heuristic methods for the flow shop sequencing problem, Eur. J. Oper. Res. 47:65–74.
Taillard, É. D., 1991, Robust taboo search for the quadratic assignment problem, Parallel Comput. 17:443–455.
Vaessens, R. J. M., Aarts E. H. L. and Lenstra, J. K., 1996, Job shop scheduling by local search, INFORMS J. Comput. 8:302–317.
Voss, S., Martello, S., Osman, I. H. and Roucairol, C., eds, 1999, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer, Boston, MA.
de Werra, D. and Hertz, A., 1989, Tabu search techniques: a tutorial and an application to neural networks, OR Spektrum 11:131–141.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer Science+Business Media, LLC
About this chapter
Cite this chapter
Gendreau, M., Potvin, JY. (2005). Tabu Search. In: Burke, E.K., Kendall, G. (eds) Search Methodologies. Springer, Boston, MA. https://doi.org/10.1007/0-387-28356-0_6
Download citation
DOI: https://doi.org/10.1007/0-387-28356-0_6
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-23460-1
Online ISBN: 978-0-387-28356-2
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)