A tabu list is a memory structure in tabu search that records tabu-active moves or solutions: choices the search temporarily cannot revisit. Ordinary local search can cycle through familiar solutions or stall at a local optimum. By ruling out recent choices, the list encourages the search to try other neighborhoods. section 6.7 section 6.2
At each iteration:
- Generate and score neighbors of the current solution, excluding tabu-active choices unless an aspiration criterion permits them. section 6.2
- Move to the best eligible neighbor, update the list, and retain an improved best-known solution. section 6.2
- Release entries after their tabu tenure. Tune that duration: too short risks cycling; too long can cause stagnation and memory overload. section 6.7
Algorithm 6.2 Tabu search
Input: an initial feasible solution
Output: optimal solution
Begin
While termination criteria not met do
Choose the best: s’∈N(s) ← N(s)-T(s)+A(s)
Memorize s’ if it improves the best known solution
s←s’
Update Tab list T(S) and Aspiration criterion A(s)
The pseudocode shows how the neighborhood, tabu restrictions, and aspiration criterion combine when selecting the next solution. section 6.2
A three-iteration restriction
In a knapsack search, swapping items 1 and 4 produces a candidate solution. Record that swap as tabu-active for the next three iterations so the search does not immediately repeat it. If adding and removing items are treated as distinct move types, separate lists may be useful. section 6.2.1
Decide what a list entry represents before implementing one. It might identify a move, a solution, or a variable assignment; the candidate check must use the same representation. A small Python implementation appends a move and removes the oldest entry when the list exceeds the specified tenure. A generic tabu-search solver instead uses a dictionary for its tabu structure. section 6.3 section 6.4
Recency-based memory restricts recent moves, while frequency-based memory counts repeated moves to help guide exploration of less-visited regions. An aspiration criterion can override a tabu restriction when a candidate improves the best-known solution. These choices balance avoiding repetition against excluding a promising move. section 6.2.1 section 6.2
The same idea appears in constraint satisfaction, routing, continuous optimization, and assembly-line balancing. In OR-Tools routing, TABU_SEARCH maintains restrictions per variable, whereas GENERIC_TABU_SEARCH maintains one list for the search. Which design works best depends on the problem and its chosen moves. section 6.5 section 6.6
