Tabu Search

Imagine you are lost in a hilly landscape and you want to reach the highest peak. You climb the nearest slope, reach the top of a small hill — and then realize it is surrounded by valleys. Every direction looks downward. You are stuck at a local optimum, a peak that looks great from where you stand but is dwarfed by the mountains you cannot see.

Ordinary local search faces exactly this trap. It moves to the best neighboring solution at every step, but the moment every neighbor is worse it halts, even if the global optimum lies just two valleys away.

In 1986, the operations researcher Fred Glover published a deceptively simple fix: keep a tabu list — a short memory of the moves you have just made — and simply forbid repeating them for a few steps. With those moves blocked, the algorithm is forced off the local hill, even if the first steps go downhill. The tabu list lifts after a few iterations, and the search resumes in fresh territory.

That one idea — memory-guided prohibition — turned local search from a dead-end strategy into one of the most effective heuristics for hard combinatorial problems like route planning and scheduling.

Below is a 10-city tour optimization. Each city is a dot; the algorithm tries to shorten the total route by swapping pairs of cities in the order. Watch the tabu list on the right — whenever a swap is made, it is blacklisted for several steps, forcing the search into unexplored territory even when that means temporarily accepting a longer route.

<div id="app">
  <div id="canvas-wrap">
    <canvas id="tour" width="300" height="280"></canvas>
    <div id="info">
      <div class="stat"><span class="label">{{lbl_tour_length}}</span><span id="len" class="val">—</span></div>
      <div class="stat"><span class="label">{{lbl_best_found}}</span><span id="best" class="val">—</span></div>
      <div class="stat"><span class="label">{{lbl_step}}</span><span id="step" class="val">0</span></div>
      <div class="stat"><span class="label">{{lbl_mode}}</span><span id="mode-label" class="val">{{mode_tabu}}</span></div>
    </div>
    <div id="tabu-panel">
      <div class="tpanel-title">{{tabu_list_title}} <span class="tenure-note">({{tenure_note}})</span></div>
      <ul id="tabu-list"></ul>
    </div>
  </div>
  <div class="btns">
    <button id="btn-step" type="button">{{btn_step}}</button>
    <button id="btn-run" type="button">{{btn_run}}</button>
    <button id="btn-mode" type="button" class="ghost">{{btn_switch_hill}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <p class="hint">
    {{hint_text}}
  </p>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 4px; }
#app { display: flex; flex-direction: column; gap: 8px; }
#canvas-wrap { display: flex; gap: 12px; flex-wrap: wrap; align-items: flex-start; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #f5f8fa; flex-shrink: 0; }
#info { display: flex; flex-direction: column; gap: 6px; min-width: 130px; }
.stat { display: flex; flex-direction: column; }
.label { font-size: .72rem; color: #666; text-transform: uppercase; letter-spacing: .05em; }
.val { font-size: 1.05rem; font-weight: 700; color: #1d3557; }
#tabu-panel { min-width: 140px; }
.tpanel-title { font-size: .78rem; font-weight: 600; color: #555; margin-bottom: 4px; }
.tenure-note { font-weight: 400; color: #888; }
#tabu-list { list-style: none; margin: 0; padding: 0; display: flex; flex-direction: column; gap: 3px; }
#tabu-list li { font-size: .8rem; background: #fde8e8; border: 1px solid #f4b8b8; border-radius: 5px;
                padding: 2px 7px; color: #a30000; font-weight: 600; }
.btns { display: flex; gap: 8px; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.hint { font-size: .82rem; color: #555; margin: 0; line-height: 1.5; }

// Code not found

Notice how the tour length sometimes increases for a step or two. That is not a bug — it is the tabu mechanism pushing the search over a hill to find a better valley on the other side. Compare with Hill Climb mode: pure hill climbing never goes uphill and quickly freezes at the first local optimum it finds.

Tabu search is a metaheuristic: it provides no proof that the solution found is globally optimal. Its power lies in three carefully balanced mechanisms:

• Tabu tenure: each forbidden move stays on the list for a fixed number of iterations (the tenure). Too short and the algorithm cycles back immediately; too long and it misses good moves. Tuning tenure is both art and science.
• Aspiration criterion: even a tabu move is allowed if it leads to a solution better than the best seen so far. This escape hatch prevents the list from blocking genuinely great discoveries.
• Diversification vs. intensification: after the short-term tabu list has pushed the search around, longer-term memory can steer it back toward promising regions (intensification) or push it into completely unexplored areas (diversification).

The problems tabu search is typically applied to — vehicle routing, job scheduling, graph coloring — are NP-hard. No polynomial-time exact algorithm is known, so practitioners willingly trade the guarantee of optimality for a fast, high-quality heuristic. In many benchmark competitions, tabu search matches or beats other leading approaches including simulated annealing and genetic algorithms.

Glover formalized the method across two seminal papers in 1986 and 1989–1990. The word tabu (also spelled taboo) deliberately evokes cultural prohibition: some moves are simply off limits, not because they are impossible, but because the algorithm has decided to forbid them temporarily to force exploration.

Any time an exact solver is too slow and a random restart is too naive, tabu search fills the gap:

• Vehicle routing and logistics: delivery companies optimize thousands of routes daily. Tabu search variants consistently rank among the best heuristics for the Capacitated Vehicle Routing Problem, often within 1% of the mathematical lower bound.
• Job-shop scheduling: assigning tasks to machines with complex precedence constraints. Industrial schedulers use tabu search to compress makespan (total completion time) in semiconductor fabrication and airline crew rostering.
• Telecommunications and network design: choosing which links to build, which frequencies to assign, and how to route data packets are all combinatorial problems where tabu search delivers practical solutions.
• VLSI circuit layout: placing transistors and routing wires on a chip is a notoriously hard 2D packing problem. Tabu search is one of the standard tools in electronic design automation.
• Bioinformatics: protein structure prediction and DNA sequence alignment involve huge search spaces; tabu search provides competitive results without the exponential blow-up of exhaustive methods.

The common thread is NP-hard combinatorial structure paired with real-world scale: thousands of variables, tight deadlines, and no time for exact algorithms. Tabu search offers a principled, memory-driven way to search that space without getting permanently stuck.

Tabu search teaches a counterintuitive lesson: sometimes the best move is the one you forbid yourself from repeating. By keeping a short memory of recent steps and blacklisting them temporarily, the algorithm is forced out of comfortable local optima and into the rough terrain where better solutions hide.

There is no magic guarantee — tabu search may still miss the global optimum, and tuning tenure and memory structures requires care. But on the hardest combinatorial problems industry faces every day, that simple prohibition list has delivered some of the best practical results known, often beating more complex methods.

The next time an optimization problem seems stuck, the tabu insight is worth remembering: rules that forbid revisiting the past can unlock a better future.