Skip to content
Back to search results

Tabu Search — Local-Search Metaheuristic

Introduced by
Fred Glover
Year
1989
Type
Local-search metaheuristic
Font size

What does it do?

Tabu Search is a local-search metaheuristic introduced by Fred Glover in 1989 that uses a tabu list — a short-term memory of recently visited solutions — to prevent cycling and escape local optima.

By explicitly forbidding moves that reverse recent decisions, the algorithm explores the search space more broadly and, through long-term memory structures such as aspiration criteria, aims to approach the global optimum even in large, complex combinatorial problems.

The intuition behind the method

Imagine navigating a mountainous landscape in the dark, trying to find the highest peak. A simple local-search climber always steps uphill and gets stuck on the nearest hill it reaches. Tabu Search carries a notepad of recently visited spots and refuses to return to them, even if backtracking would seem tempting. This enforced amnesia about recent moves forces the search out of dead ends and into unexplored territory, allowing it to eventually discover much higher ground than a plain local search ever would.

History

Tabu Search was introduced by Fred Glover in a landmark 1989 paper in the ORSA Journal on Computing, where it was presented as a strategy to guide local search by exploiting memory of past moves. The foundational ideas were consolidated and extended in Glover and Laguna's 1997 Springer monograph, which established the canonical short-term tabu list, aspiration criteria, and long-term diversification and intensification strategies that remain central to the method today. Since its introduction Tabu Search has been applied extensively in operations research, scheduling, logistics, and combinatorial design, and it continues to be a standard benchmark metaheuristic alongside simulated annealing and genetic algorithms.

When to use it

Tabu Search is well suited to combinatorial and discrete optimization problems where the solution space is too large for exact methods and the problem structure allows a meaningful neighbourhood to be defined. Typical applications include scheduling, routing, assignment, and sequencing problems. It is particularly effective when the search landscape has many local optima that trap simpler methods. It does not require the objective function to be differentiable or continuous. The neighbourhood definition and tabu tenure must be adapted carefully to the specific problem; a poorly chosen neighbourhood or too short or too long a tenure can degrade performance significantly. At least several hundred — and ideally more than one thousand — iterations are needed for the search to explore the space adequately.

Limitations and considerations

  • Performance is sensitive to the neighbourhood definition and tabu tenure; poor choices can trap the search or make it cycle despite the tabu mechanism.
  • Requires a minimum iteration budget — typically more than 1 000 iterations — to explore the neighbourhood sufficiently; with too few iterations results are no better than simple local search.
  • The tabu list stores move attributes rather than full solutions, so the aspiration criterion is needed to prevent inadvertently blocking genuinely good moves.
  • Unlike exact solvers, Tabu Search offers no optimality guarantee and the result quality can vary across runs if the initial solution or neighbourhood is stochastic.

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Escapes local optima through the tabu mechanism without requiring gradient information.
  • Applicable to combinatorial, mixed-type, and even continuous problems — it does not assume normality or any distributional property.
  • Incorporates memory at multiple time scales (short-term tabu list, long-term diversification/intensification) enabling principled exploration of the search space.
  • Often finds high-quality solutions with relatively modest computational budgets compared with exact methods on large instances.

Applications

  • Job-shop and flow-shop scheduling — optimising the sequence of operations to minimise makespan or tardiness.
  • Vehicle routing — finding efficient delivery routes subject to capacity and time-window constraints.
  • Assignment and facility location — assigning tasks to resources or locating facilities to minimise cost.
  • Graph colouring, network design, and telecommunications — solving discrete structural optimisation problems.
  • Feature selection and hyperparameter search — exploring discrete configuration spaces in machine learning pipelines.

How it works

How it works

1

The search starts from an initial candidate solution, which can be constructed randomly or with a greedy heuristic. The tabu list is set up as an empty fixed-length queue, and the best solution found so far is recorded. The neighbourhood structure — the rule that defines which solutions are one step away from the current solution — must be defined in a way that is meaningful for the specific problem.

2

From the current solution, all moves in the defined neighbourhood are generated and evaluated against the objective function. Each move corresponds to a small perturbation, such as swapping two elements in a sequence or flipping a binary variable. The neighbourhood must be rich enough to allow meaningful exploration but small enough to be tractable within each iteration.

3

Each candidate move is tested against the tabu list. If the move — or the attribute that characterises it — appears on the list, it is classified as tabu and is forbidden, unless it satisfies an aspiration criterion: typically, if the resulting solution would be better than the best solution found so far, the tabu status is overridden and the move is permitted. This aspiration mechanism gives the algorithm flexibility without abandoning its anti-cycling discipline.

4

Among all non-tabu moves (and any tabu moves that pass the aspiration criterion), the best-performing move is selected and executed, even if it worsens the objective value. This willingness to accept deterioration is what enables the algorithm to escape local optima, which is the defining trait of Tabu Search compared with simple hill climbing.

5

After the move is executed, the tabu list is updated by adding the reverse of the move just made (or its characterising attribute), and the oldest entry is removed if the list is full, maintaining its fixed length — the tabu tenure. If the new solution is better than the best recorded solution, the best solution is updated. Optional long-term memory structures can track solution frequency or recency to guide diversification into less-visited regions or intensification around promising ones.

6

The algorithm continues iterating until a stopping criterion is met: a maximum number of iterations, a target objective value, or a fixed count of iterations without improvement. The best solution found throughout the entire search is returned as the result. Choosing an adequate iteration budget is critical — too few iterations prevent sufficient neighbourhood exploration.

Common pitfalls

  • Setting the tabu tenure too short allows cycling to recur, defeating the purpose of the tabu mechanism; tenure should be tuned for the problem size.
  • Setting the tenure too long over-restricts the search and prevents the algorithm from revisiting regions that may contain improvements.
  • Running fewer than approximately 1 000 iterations means the search has not explored enough of the neighbourhood — if compute is limited, fall back to simulated annealing which can produce useful results faster with fewer iterations.
  • Using a neighbourhood that is too narrow (e.g., only single-swap moves on a complex structure) leads to a shallow search; ensure the neighbourhood is rich enough to connect all promising regions of the solution space.
  • Ignoring the aspiration criterion can permanently block moves to the global optimum if that move happens to be tabu; always implement at least the standard best-solution override.

Frequently asked questions

How is Tabu Search different from simulated annealing?

Both methods accept worsening moves to escape local optima, but they differ in mechanism. Simulated annealing accepts worse moves probabilistically, guided by a cooling temperature parameter. Tabu Search accepts the best available non-tabu move deterministically, guided by explicit memory of recent moves. Tabu Search is generally more effective on structured combinatorial problems; simulated annealing can be easier to tune on problems with continuous or near-continuous landscapes and is preferable when the iteration budget is small (below roughly 1 000 iterations).

How long should the tabu list be?

Tabu tenure — the number of iterations a move remains forbidden — is problem-dependent. A commonly cited starting point is a tenure proportional to the square root of the problem size, but this should be tuned empirically. Too short a tenure allows cycling; too long a tenure over-restricts the search. Adaptive or randomised tenure strategies can reduce sensitivity to this choice.

Does Tabu Search guarantee finding the global optimum?

No. Tabu Search is a metaheuristic and provides no optimality guarantee. It aims to find high-quality solutions efficiently, but the result depends on the neighbourhood structure, tenure, number of iterations, and the initial solution. For an optimality guarantee, an exact method such as integer programming is required, though exact methods may be computationally infeasible for large instances.

What is an aspiration criterion and why is it necessary?

An aspiration criterion is a rule that overrides the tabu status of a move under special conditions. The most common criterion is: if executing a tabu move would yield a solution better than the best solution found so far, the tabu restriction is lifted and the move is allowed. Without this override, the tabu mechanism could permanently block the path to the global optimum if that path runs through a recently visited move.

Related methods

Sources

  1. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    Open publication reference
    Copied.
  2. Glover, F. & Laguna, M. (1997). Tabu Search. Springer.

    ISBN: 9780792349907
    Copied.