Tabu Search
Tabu search (TS) is an iterative procedure designed for the solution of
optimization problems. TS was invented by Glover
and has been used to solve a wide range of hard optimization problems such
as job shop scheduling, graph colouring (related), the Travelling Salesman
Problem (TSP) and the capacitated arc routing problem. A good description
of the technique can be found here
or here.
An overview of the TS approach to scheduling problems can be found in:
J. W. Barnes, M. Laguna and F. Glover
Intelligent
Scheduling Systems, D. E. Brown and W. T. Scherer (Eds.),
Kluwer Academic Publishers, pp. 101-127 (1995).
TS has been applied to the network
design problem. For a description of the technique and its application
to a number of problem domains read Tabu Search,
the book. A large number of references to TS can be found here.
Battiti's description of Reactive Tabu Search (RTS) can be found here.
A number of TS papers related to telecommunications can be found here.
Laguna's publications on TS can be found here.
A thesis comparing various heuristic search techniques for object recognition
can be found here.
Publications
-
Fred
Glover and Manuel
Laguna, Tabu
Search, Kluwer Academic Publishers,
Boston, ISBN 0-7923-9965-X, July 1997, 408 pp.
-
The Annals of Operational
Research frequently publishes articles on TS.
Researchers
-
Fred
Glover, principal researcher at University of Colorado.
-
Manuel Laguna,
principal researcher at University of Colorado.
-
James
Kelly, principal researcher at University of Colorado.
-
Ross James,
researcher at University of Canterbury, NZ.
-
Anthony
Vannelli, researcher at the University of Waterloo, CA.
-
Chae Y.
Lee, researcher at KAIST, Korea
-
Roberto Battiti,
University of Trento, Italy.
-
Roland Hübscher,
post-doctoral researcher at Georgia Institute of Technology, USA.
-
Eric Taillard, ant search, tabu
search applied to scheduling and routing problems.
-
Jiefeng Xu, several
problem domains of interest.
-
Yves Rochat,
doing a PhD looking at vehicle routing, see his TS demo.
-
Curt Hjorring, did
a PhD looking at vehicle routing comparing GA, TS.
-
Giorgio Giacinto,
a PhD student looking at classification/pattern recognition problems.
-
Daniel Kobler,
a PhD student at EPFL.
-
Martin Zachariasen, a PhD
student at the University of Copenhagen, Denmark.
Groups
-
University of Colorado Business
School, USA.
-
University of Trento, Italy
-
(EPFL) Ecole Polytechnique Federale De Lausanne,
Switzerland
-
(IDSIA) Istituto Dalle Molle di Studi sull'Intelligenza
Artificiale, Lugano, Switzerland
-
Politechnico of Milan, Italy
-
University of East Anglia,
Mathematical Algorithms Group (MAG)
Links
-
Bibliography including
TS references at the University of East Anglia, England
This page is under construction.
More information will be added as it becomes available.