Tabu search is local search with memory. Instead of accepting only improvements near the current solution, it temporarily forbids recently used moves or solutions. That discourages cycling and lets the search move beyond a local optimum. A tabu list records the restrictions; tabu tenure sets how many iterations they last. section 6.0 section 6.7
Choosing a different restaurant
Imagine choosing meals at a resort. Returning to yesterday’s good restaurant is tempting, but avoiding it for several days creates a chance to discover a better option. You still remember which meals were best and may return later. Tabu search applies the same combination of short-term restriction and remembered quality to candidate solutions. section 6.2
A basic run follows this loop:
- Start with a feasible solution and generate neighboring solutions through local changes. section 6.2
- Choose the best eligible neighbor, excluding tabu-active choices unless an aspiration criterion allows one. section 6.2 section 6.7
- Move there, record any improvement to the best-known solution, update the tabu list and repeat until a stopping criterion is met. section 6.2
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 the distinction between the current solution and the best-known solution, and where tabu restrictions and aspiration enter neighbor selection. section 6.2
Seven queens by hand
For the seven-queens constraint-satisfaction problem, count pairs of queens that attack each other. A worked run begins with four collisions; a swap cuts that to two and is forbidden for three iterations. Another swap brings the count to one. Later, an improving swap is still tabu-active, so an aspiration criterion permits it. This illustrates why the search must track both candidate quality and recent moves. section 6.3
Tune the initial-solution method, neighborhood, tabu tenure, aspiration rule and stopping criterion for the problem. Too short a tenure invites repeated moves; too long a tenure can cause stagnation and memory overload. Parameters may be fixed before a run or adjusted during it. Tabu search works in discrete and continuous spaces, but can require many iterations and does not guarantee a global optimum. section 6.2.3 section 6.7
Routing with Python
For the 52-location Berlin52 traveling-salesperson instance, an OR-Tools implementation builds a distance matrix and routing model, sets LocalSearchMetaheuristic.TABU_SEARCH, and applies a 30-second limit. Its reported route length is 7,884, compared with the stated shortest route of 7,542. The result is useful without being an optimality claim; try changing the search settings and comparing routes. section 6.5
