Tabu Search (TS) is a trajectory-based metaheuristic created by Fred Glover in 1986 and formalized in his seminal 1989–1990 two-part paper. It enhances basic local search by adding an explicit memory structure — the tabu list — that records recently visited moves and forbids the algorithm from revisiting them. This simple mechanism lets TS escape local optima that trap greedy hill-climbers, while remaining focused enough to converge to high-quality solutions.
The word “tabu” (Glover’s preferred spelling) comes from the Tongan word for things that are forbidden or sacred. The metaphor is apt: by declaring certain moves temporarily off-limits, the algorithm is forced to explore new regions of the search space. Unlike simulated annealing, which uses randomness to escape local optima, tabu search uses deterministic memory — it remembers where it has been and deliberately avoids going back.
Tabu search is one of the most commercially successful metaheuristics. It dominates vehicle routing (the CVRP solvers inside UPS ORION and similar logistics platforms use TS variants), job-shop scheduling, frequency assignment in telecommunications, and VLSI circuit design. Its strength lies in its simplicity, effectiveness, and natural extensibility — the memory framework generalizes cleanly to short-term, medium-term, and long-term memory strategies that can be tuned for specific problem structures.
Tabu search starts from an initial solution and iteratively moves to the best neighboring solution that is not forbidden by the tabu list. Crucially, TS always accepts the best available move — even if it worsens the objective — because the tabu list prevents cycling back to prior solutions:
def tabu_search(initial_solution, neighborhood, evaluate,
max_iterations, tabu_tenure):
current = initial_solution
best = current
tabu_list = {} # move → expiry iteration
for iteration in range(max_iterations):
# Generate all neighbors
candidates = neighborhood(current)
# Filter: remove tabu moves (unless aspiration met)
allowed = []
for move, solution in candidates:
if move not in tabu_list or tabu_list[move] <= iteration:
allowed.append((move, solution))
elif evaluate(solution) < evaluate(best):
# Aspiration: override tabu if globally best
allowed.append((move, solution))
if not allowed:
break
# Pick the best allowed neighbor
best_move, current = min(allowed, key=lambda x: evaluate(x[1]))
# Update tabu list
tabu_list[best_move] = iteration + tabu_tenure
# Update global best
if evaluate(current) < evaluate(best):
best = current
return bestThe tabu list is a short-term memory that stores attributes of recently applied moves (not full solutions — storing move attributes is more space-efficient and generalizes better). Each entry has a tabu tenure — the number of iterations the move remains forbidden. When the list is full, the oldest entries expire in FIFO order. Typical tenure values range from 5 to 20 for small problems, or √n for problems of size n.
The tabu tenure is the single most important parameter. Too short (1–2 iterations) and the search cycles between nearby solutions, failing to escape the local optimum. Too long (hundreds of iterations) and too many moves are forbidden, starving the search of options and causing it to miss good solutions.
In practice, three strategies are common:
7). Simple and often surprisingly effective.[t_min, t_max] each iteration. Prevents deterministic cycling patterns.A move that is tabu can still be accepted if it satisfies an aspiration criterion. The most common criterion: if a tabu move leads to a solution better than the global best found so far, accept it regardless of tabu status. This ensures that the tabu list — a heuristic safety mechanism — never prevents the algorithm from accepting a clearly superior solution.
Glover’s framework distinguishes three levels of memory, each serving a different strategic purpose:
Tabu search makes the exploration–exploitation tradeoff explicit through its memory structures. Intensification concentrates search around the best-known solutions; diversification forces the search to visit uncharted territory. The balance between them determines whether TS converges quickly (high intensification) or thoroughly explores the search space (high diversification). Advanced implementations alternate between phases or use adaptive rules to switch strategies.
The definition of the neighborhood — which solutions are reachable from the current one in a single move — is problem-specific and critical to performance. For vehicle routing: swap two customers between routes, move a customer to a different route, or reverse a sub-route (2-opt). For scheduling: swap the positions of two jobs, move a job to a different machine. The neighborhood should be large enough to reach good solutions but small enough to evaluate efficiently. Many implementations use a candidate list strategy, evaluating only a promising subset of neighbors each iteration.
Tabu search is the dominant metaheuristic for vehicle routing problems. The Capacitated Vehicle Routing Problem (CVRP) — assigning delivery stops to vehicles with capacity constraints to minimize total distance — is the backbone of logistics optimization. Taillard (1993) and Gendreau et al. (1994) established TS as the state-of-the-art for CVRP. Modern variants handle time windows (VRPTW), pickup-and-delivery, and multi-depot scenarios. Commercial solvers like Google OR-Tools and the COIN-OR VRP solver include TS components. UPS’s ORION system, which saves the company an estimated $300–400 million annually in fuel costs, uses routing algorithms built on tabu search principles.
The job-shop scheduling problem (JSSP) — assigning operations to machines and time slots to minimize makespan — is a classic NP-hard problem. Taillard’s (1994) tabu search for JSSP used a neighborhood defined by swapping adjacent operations on the critical path, with tabu tenure proportional to problem size. This approach held benchmark records for years and remains competitive with modern methods.
In telecommunications, assigning frequencies to transmitters while minimizing interference is equivalent to graph coloring — and tabu search is one of the best-known methods for this problem. The TABUCOL algorithm (Hertz & de Werra, 1987) uses a penalty-based approach where the neighborhood swaps the color of a conflicting vertex, and the tabu list forbids reassigning a vertex to its previous color for a random tenure.
In machine learning contexts, tabu search has been applied to feature selection (tabu-based wrapper methods that track recently added/removed features), Bayesian network structure learning (the search space of DAGs is navigated with arc addition/deletion/reversal moves), and hyperparameter optimization (discrete or mixed search spaces where gradient information is unavailable).