6 Tabu Search

Building on local search, this chapter introduces tabu search (TS) as a trajectory-based metaheuristic that augments simple neighborhood improvement with adaptive memory and responsive exploration. Unlike greedy local search that risks getting trapped in local optima, TS allows non-improving moves while preventing cycling by marking recently used solution attributes or moves as tabu. At each iteration it evaluates a candidate neighborhood, selects the best admissible move (respecting tabu restrictions unless an aspiration rule permits an override), updates memories, and continues until stopping criteria such as no improvement, exhausted neighborhoods, or external convergence evidence are met. The approach has been applied widely across scheduling, routing, design, allocation, and other combinatorial and continuous optimization tasks.

The core components of TS are its memory structures and admissibility rules. Short-term (recency-based) memory records recently used moves to discourage immediate reversal and promote escape from local optima, while long-term (frequency-based) memory guides diversification by penalizing overused components to steer the search toward unexplored regions. Aspiration criteria mitigate stagnation by allowing tabu moves that yield solutions better than the incumbent. Performance hinges on design and tuning: neighborhood operators, tabu tenure (fixed, dynamic, or reactive to detected cycles), aspiration limits, and stopping rules. Adaptive and self-adaptive schemes can vary tenure within bounds, intensifying in promising regions and diversifying when progress stalls; these mechanisms enable TS to operate effectively on both discrete and continuous landscapes.

Through case studies, the chapter demonstrates TS in action: solving constraint satisfaction via n-queens by minimizing collisions with swap neighborhoods and tabu lists; handling continuous function optimization (e.g., Himmelblau) with a generic TS solver; and addressing routing with both a custom TS and an implementation in OR-Tools on the Berlin52 instance, as well as a real-world delivery tour. It also tackles assembly line balancing (SALBP and space-aware TSALBP), honoring precedence and cycle-time constraints while minimizing imbalance using a Smoothing Index, with neighborhoods defined by feasible swaps and benchmark evaluations. Across these examples, TS consistently balances intensification and diversification, often producing high-quality near-optimal solutions when its memory structures, neighborhoods, and parameters are thoughtfully tuned.

Tabu Search Steps [1]

A 4-City TSP

In knapsack problems, each item has a utility and a weight, and we want to maximize the utility of the contents of the knapsack without exceeding the maximum weight. The problem is constrained by the capacity of the bag. Two tabu lengths are used for adding and removing items.

TS short-term memory and long-term memory and the search dilemma

Tabu structure for the 4-City TSP. The numbers in recency-based memory represent the number of iterations remaining for tabu-active moves and the number in the long-term memory represent the frequency count of using the move.

Effect of Tabu Length

Dynamically controlling the tabu tenure

A 7-Queens Problem - TS Initialization. C represents the column where a queen Q is place. Dotted lines shows the 4 collisions between the queens. * denotes the selected swap that gives best neighboring solution.

A 7-Queens Problem - TS Iteration-1

A 7-Queens Problem - TS Iteration-2

A 7-Queens Problem - TS Iteration-3

A 7-Queens Problem - TS Iteration-4

A 7-Queens Problem - TS Iteration-5

A 7-Queens Problem - TS Iteration-6

A 7-Queens solution generated by hand-iterations

A 7-Queens solution generated by Python code

Himmelblau's function. This function has four identical local minima at (3.0, 2.0), (−2.805118, 3.131312), (−3.779310, −3.283186) and (3.584428, −1.848126). It also has one local maximum at (-0.270845,-0.923039).

TSP solution using Tabu Search in OR-Tools. The axes represent the x, y coordinates of the points of interest included in the dataset.

TS solution for Walmart delivery semi-truck route with total distance= 223.53 km

Assembly Line Balancing Problem.

Precedence diagram.

Equation 6.1

Precedence diagram example for 6 tasks

TS Initialization for ALBP

TS Iteration-1 for ALBP

TS Iteration-2 for ALBP

SALBP initial and final solutions

• Local search iteratively explores a subset of search space in the neighborhood of the current solution/state in order to improve this solution by local changes.
• Tabu search extends local search by combining it with memory structures. It guides a local search procedure to explore the solution space beyond local optimality.
• Memory-based strategies are the hallmark of tabu search approach.
• Tabu search accepts non-improving solutions in order to escape from local optima (where all the neighboring solutions are non-improving).
• Tabu search uses past experiences to improve current decision making by using memory (a “tabu list”) to prohibit certain moves – “makes tabu search attempt to be a global optimizer rather than a local optimizer.”
• Tabu tenure is a certain amount of time or a certain number of iterations during which previously visited nodes are forbidden.
• As a way to avoid search stagnation, aspiration criteria allow tabu-active moves to be accepted by relaxing or temporarily lifting the tabu condition.
• A key element of the adaptive tabu search is to create a balance between search intensification and diversification.

FAQ