Tabu Search


The basic concept of Tabu Search as described by Glover (1986) is "a meta-heuristic superimposed on another heuristic. The overall approach is to avoid entrainment in cycles by forbidding or penalizing moves which take the solution, in the next iteration, to points in the solution space previously visited ( hence "tabu"). The Tabu search is fairly new, Glover attributes it's origin to about 1977 (see Glover, 1977). The method is still actively researched, and is continuing to evolve and improve. The Tabu method was partly motivated by the observation that human behavior appears to operate with a random element that leads to inconsistent behavior given similar circumstances. As Glover points out, the resulting tendency to deviate from a charted course, might be regretted as a source of error but can also prove to be source of gain. The Tabu method operates in this way with the exception that new courses are not chosen randomly. Instead the Tabu search proceeds according to the supposition that there is no point in accepting a new (poor) solution unless it is to avoid a path already investigated. This insures new regions of a problems solution space will be investigated in with the goal of avoiding local minima and ultimately finding the desired solution.

The Tabu search begins by marching to a local minima. To avoid retracing the steps used, the method records recent moves in one or more Tabu lists. The original intent of the list was not to prevent a previous move from being repeated, but rather to insure it was not reversed. The Tabu lists are historical in nature and form the Tabu search memory. The role of the memory can change as the algorithm proceeds. At initialization the goal is make a coarse examination of the solution space, known as 'diversification', but as candidate locations are identified the search is more focused to produce local optimal solutions in a process of 'intensification'. In many cases the differences between the various implementations of the Tabu method have to do with the size, variability, and adaptability of the Tabu memory to a particular problem domain.

Application Domain

The Tabu search has traditionally been used on combinatorial optimization problems. The technique is straightforwardly applied to continuous functions by choosing a discrete encoding of the problem. Many of the applications in the literature involve integer programming problems, scheduling, routing, traveling salesman and related problems.


Reactive Tabu Search R. Battiti, C source for Reactive Tabu Search



R. Battiti, "Reactive search: Toward self-tuning heuristics", In V. J. Rayward-Smith, editor, Modern Heuristic Search Methods, chapter 4, pages 61--83. John Wiley and Sons Ltd, 1996.

R. Battiti and G. Tecchiolli, "Simulated annealing and tabu search in the long run: a comparison on qap tasks", Computer Math. Applic., 28(6):1--8, 1994.

A M. Dell'Amico , A M. Trubian, "Applying Tabu Search to the Job-shop Scheduling Problem", J Annals of Ops. Res., 41, 1993

Glover F.," Future paths for Integer Programming and Links to Artificial Intelligence", Computers and Operations Research, 5:533-549, 1986.

Glover F., "Tabu Search: A Tutorial", Interfaces, 20(4):74-94,1990.

Glover, F. and D. de Werra,Tabu Search, Baltzer Science Publishers, 199

Glover F., and Laguna M., Tabu Search, in Modern Heuristic Techniques for Combinatorial Problems, C.R. Reeves, editor, John Wiley & Sons, Inc, 1993

A Hertz, "Finding a Feasible Course Schedule Using Tabu Search", Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, 35, 1992

A M. Laguna, A J. W. Barnes, A F. Glover, "Tabu Search Methodology for a Single Machine Scheduling Problem", J. of Int. Manufacturing, 2, 63-74, 1991

A M. Laguna, A J. L. Gonzalez-Velarde, "A Search Heuristic for Just-in-time Scheduling in Parallel Machines", J. of Int. Manu., 2, 253-260, 1991

A S. C. S. Porto, A C.C. Ribeiro , "Parallel Tabu Search Message-Passing Synchronous Strategies for Task Scheduling under Precedence Constraints", Journal of Heuristics, V 1, 1995

A S. C. S. Porto, A C.C. Ribeiro, "A Tabu Search Approach to Task Scheduling on Heterogeneous Processors under Precedence Constraints", International Journal of High-Speed Computing, 7(2), 1995

A M. Widmer, "The Job-shop Scheduling with Tooling Constraints: A Tabu Search Approach", J. Opt. Res. S, 42, 75-82, 1991

A M. Widmer, A A. Hertz, "A New Heuristic Method for the Flow Shop Sequencing Problem", Euro. J. Opt. Res., 41, 186-193, 1989

Miscellaneous Links

Reactive Tabu Search R. Battiti, Reactive Tabu Search papers

Global Optimization Survey - Main Page
Sandia National Laboratories

This page maintained by
Last modified: March 10, 1997