Top

Published in:

2014 | OriginalPaper | Chapter

9. Tabu Search

Authors : Michel Gendreau, Jean-Yves Potvin

Published in: Search Methodologies

Publisher: Springer US

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This chapter is an introductory tutorial on tabu search. It emphasizes the basic mechanisms of this search method and illustrates their application on two classical combinatorial problems. Some more advanced concepts, like diversification and intensification, are also introduced. The chapter ends with useful tips for designing a successful tabu search implementation.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Swarm Intelligence

next chapter Simulated Annealing

Alba E (ed) (2005) Parallel metaheuristics: a new class of algorithms. Wiley, Hoboken

Anderson EJ, Glass CA, Potts CN (1997) Machine scheduling, in local search in combinatorial optimization. In: Aarts EHL, Lenstra JK (eds). Wiley, New York, pp 361–414

Ateme-Nguema B, Dao T-M (2009) Quantized Hopfield networks and tabu search for manufacturing cell formation problems. Int J Product Econ 121:88–98CrossRef

Battiti R, Tecchiolli G (1994) The reactive tabu search. ORSA J Comput 6:126–140CrossRef

Blum C, Blesa Aguilera MJ, Roli A, Sampels M (eds) (2008) Hybrid metaheuristics: an emerging approach to optimization. Springer, Berlin

Burke E, De Causmaecker P, Vanden Berghe G (1998) A Hybrid Tabu Search Algorithm for the Nurse Rostering Problem. In: Selected papers from the 2nd Asia Pacific conference on simulated evolution and learning, LNAI 1585. Springer, Berlin, Canberra, Australia, pp 187–194

Crainic TG, Gendreau M (1999) Towards an evolutionary method—cooperative multi-thread parallel tabu search heuristic hybrid. In: Voss S et al (eds) Meta-heuristics: advances and trends in local search paradigms for optimization. Kluwer, Norwell, pp 331–344CrossRef

Crainic TG, Gendreau M, Soriano P, Toulouse M (1993) A tabu search procedure for multicommodity location/allocation with balancing requirements. Ann Oper Res 41:359–383CrossRef

Crainic TG, Toulouse M, Gendreau M (1997) Toward a taxonomy of parallel tabu search heuristics. INFORMS J Comput 9:61–72CrossRef

Crainic TG, Gendreau M, Farvolden JM (2000) Simplex-based tabu search for the multicommodity capacitated fixed charge network design problem. INFORMS J Comput 12:223–236CrossRef

Crainic TG, Gendreau M, Rousseau L-M (eds) (2010) J Heuristics 16:235–535 (Special issue: Recent advances in metaheuristics)

Cung V-D, Martins SL, Ribeiro CC, Roucairol C (2002) Strategies for the parallel implementation of metaheuristics. In: Ribeiro CC, Hansen P (eds) Essays and surveys in metaheuristics. Kluwer, Norwell, pp 263–308CrossRef

de Werra D, Hertz A (1989) Tabu search techniques: a tutorial and an application to neural networks. OR Spektrum 11:131–141CrossRef

Doerner KF, Gendreau M, Greistorfer P, Gutjahr WJ, Hartl RF, Reimann M (eds) (2007) Metaheuristics: progress in complex systems optimization. Springer, New York

Dorigo M (1992) Optimization, learning and natural algorithms. PhD Dissertation, Departimento di Elettronica, Politecnico di Milano

Dueck G, Scheuer T (1990) Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing. J Comput Phys 90:161–175CrossRef

Fleurent C, Ferland JA (1996) Genetic and hybrid algorithms for graph colouring. Ann Oper Res 63:437–461CrossRef

Friden C, Hertz A, de Werra D (1989) STABULUS: a technique for finding stable sets in large graphs with tabu search. Computing 42:35–44CrossRef

Gandibleux X, Jaszkiewicz A, Freville A, Slowinski R (eds) (2000) J Heuristics 6:291–431 (Special issue: Multiple objective metaheuristics)

Gendreau M (2002) Recent advances in tabu search. In: Ribeiro CC, Hansen P (eds) Essays and surveys in metaheuristics. Kluwer, Norwell, pp 369–377CrossRef

Gendreau M, Soriano P, Salvail L (1993) Solving the maximum clique problem using a tabu search approach. Ann Oper Res 41:385–403CrossRef

Gendreau M, Hertz A, Laporte G (1994) A tabu search heuristic for the vehicle routing problem. Manage Sci 40:1276–1290CrossRef

Gendreau M, Guertin F, Potvin J-Y, Séguin R (2006) Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries. Transp Res C 14:157–174CrossRef

Glover F (1977) Heuristics for integer programming using surrogate constraints. Decis Sci 8:156–166CrossRef

Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 13:533–549CrossRef

Glover F (1989) Tabu search I. ORSA J Comput 1:190–206CrossRef

Glover F (1990) Tabu search II. ORSA J Comput 2:4–32CrossRef

Glover F (1992) Ejection chains, reference structures and alternating path methods for traveling salesman problems. University of Colorado Report (Shortened version published in Discret Appl Math 65:223–253, 1996)

Glover F, Kochenberger GA (eds) (2003) Handbook of metaheuristics. Kluwer, Norwell

Glover F, Laguna M (1993) Tabu search. In: Reeves CR (ed) Modern heuristic techniques for combinatorial problems. Halsted Press, New York, pp 70–150

Glover F, Laguna M (1997) Tabu search. Kluwer, NorwellCrossRef

Glover F, Laguna M, Taillard ED, de Werra D (eds) (1993) Tabu search. Ann Oper Res 41, Baltzer Science, Basel, pp 1–490

Glover F, Taillard ED, de Werra D (1993) A user’s guide to tabu search. Ann Oper Res 41:3–28CrossRef

Grünert T (2002) Lagrangean tabu search. In: Ribeiro CC, Hansen P (eds) Essays and surveys in metaheuristics. Kluwer, Norwell, pp 379–397CrossRef

Hertz A, de Werra D (1987) Using tabu search for graph coloring. Computing 39:345–351CrossRef

Hertz A, de Werra D (1991) The tabu search metaheuristic: how we used it. Ann Math Artif Intell 1:111–121CrossRef

Hindsberger M, Vidal RVV (2000) Tabu search—a guided tour. Control Cybern 29:631–651

Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor

Ibaraki T, Nonobe K, Yagiura M (eds) (2005) Metaheuristics: progress as real problem solvers. Springer, New York

Jaziri W (2008) Local search techniques: focus on tabu search. In-Teh, CroatiaCrossRef

Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680CrossRef

Laporte G, Osman IH (eds) (1996) Metaheuristics in combinatorial optimization. Ann Oper Res 63, Baltzer Science, Basel, pp 1–630

Lokketangen A, Glover F (1996) Probabilistic move selection in tabu search for 0/1 mixed integer programming problems. In: Osman IH, Kelly JP (eds) Meta-heuristics: theory and applications. Kluwer, Norwell, pp 467–488CrossRef

Lokketangen A, Woodruff DL (1996) Progressive hedging and tabu search applied to mixed integer (0,1) multistage stochastic programming. J Heuristics 2:111–128CrossRef

Nilsson NJ (1980) Principles of artificial intelligence. Morgan Kaufmann, Los Altos

Osman IH, Kelly JP (eds) (1996) Meta-heuristics: theory and applications. Kluwer, Norwell

Pardalos PM, Resende MGC (eds) (2002) Handbook of applied optimization. Oxford University Press, New York

Pesant G, Gendreau M (1999) A constraint programming framework for local search methods. J Heuristics 5:255–280CrossRef

Rego C, Alidaee B (eds) (2005) Metaheuristic optimization via memory and evolution: tabu search and scatter search. Kluwer, Norwell

Resende MGC, de Sousa JP (eds) (2004) Metaheuristics: computer decision-making, Kluwer, Norwell

Ribeiro CC, Hansen P (eds) (2002) Essays and surveys in metaheuristics. Kluwer, Norwell

Rochat Y, Taillard ED (1995) Probabilistic diversification and intensification in local search for vehicle routing. J Heuristics 1:147–167CrossRef

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–45CrossRef

Soriano P, Gendreau M (1996) Diversification strategies in tabu search algorithms for the maximum clique problems. Ann Oper Res 63:189–207CrossRef

Soriano P, Gendreau M (1997) Fondements et applications des méthodes de recherche avec tabous. RAIRO—Recherche Opérationnelle 31:133–159

Taillard ED (1990) Some efficient heuristic methods for the flow shop sequencing problem. Eur J Oper Res 47:65–74CrossRef

Taillard ED (1991) Robust taboo search for the quadratic assignment problem. Parallel Comput 17:443–455CrossRef

Vaessens RJM, Aarts EHL, Lenstra JK (1996) Job shop scheduling by local search. INFORMS J Comput 8:302–317CrossRef

Voss S, Martello S, Osman IH, Roucairol C (eds) (1999) Meta-heuristics: advances and trends in local search paradigms for optimization. Kluwer, Norwell

Wang Y, Li L, Ni J, Huang S (2009) Feature selection using tabu search with long-term memories and probabilistic neural networks. Pattern Recognit Lett 30:661–670CrossRef

Title: Tabu Search
Authors: Michel Gendreau
Jean-Yves Potvin
Publisher: Springer US
Book: Search Methodologies
Print ISBN: 978-1-4614-6939-1

Electronic ISBN: 978-1-4614-6940-7

Copyright Year: 2014
DOI: https://doi.org/10.1007/978-1-4614-6940-7_9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner