Tabu Search — Local-Search Metaheuristic
Tabu Search (Tabu Search Metaheuristic) · Also known as: Tabu Araması (Tabu Search), TS, tabu metaheuristic
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.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
+5 more
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.
Strengths & limitations
- 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.
- 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.
Frequently asked
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.
Sources
- Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206. link ↗
- Glover, F. & Laguna, M. (1997). Tabu Search. Springer. ISBN: 9780792349907
How to cite this page
ScholarGate. (2026, June 1). Tabu Search (Tabu Search Metaheuristic). ScholarGate. https://scholargate.app/en/optimization/tabu-search
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Ant Colony OptimizationOptimization↔ compare
- Genetic AlgorithmOptimization↔ compare
- Particle Swarm OptimizationOptimization↔ compare
- Simulated AnnealingOptimization↔ compare