a-tutorial-on-tabu

A TUTORIAL ON TABU SEARCH1 2 1Alain Hertz , Eric Taillard , Dominique de Werra1 EPFL, Département de Mathématiques, MA-Ecublens, CH-1015 Lausanne2 Université de Montréal, Centre de Recherche sur les Transports, Montréal, Canada H3C 3J7Keywords:1. IntroductionEngineering and technology have been continuously providing examples of difficultoptimization problems. In this talk we shall present the tabu search technique which with itsvarious ingredients may be viewed as an engineer designed approach: no clean proof ofconvergence is known but the technique has shown a remarkable efficiency on many problems.The roots of tabu search go back to the 1970's; it was first presented in its present form byGlover [Glover, 1986]; the basic ideas have also been sketched by Hansen [Hansen 1986].Additional efforts of formalization are reported in [Glover, 1989], [de Werra & Hertz, 1989],[Glover, 1990]. Many computational experiments have shown that tabu search has now becomean established optimization technique which can compete with almost all known techniques andwhich - by its flexibility - can beat many classical procedures. Up to now, there is no formalexplanation of this good behavior. Recently, theoretical aspects of tabu search have beeninvestigated [Faigle & Kern, 1992], [Glover, 1992], [Fox, 1993].A didactic presentation of tabu search and a series of applications have been collected in arecent book [Glover, Taillard, Laguna & de Werra, 1992]. Its interest lies ...