Introduction

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.

Try It: Tour Optimization

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">Tour length</span><span id="len" class="val">—</span></div>
      <div class="stat"><span class="label">Best found</span><span id="best" class="val">—</span></div>
      <div class="stat"><span class="label">Step</span><span id="step" class="val">0</span></div>
      <div class="stat"><span class="label">Mode</span><span id="mode-label" class="val">Tabu</span></div>
    </div>
    <div id="tabu-panel">
      <div class="tpanel-title">Tabu list <span class="tenure-note">(tenure 5)</span></div>
      <ul id="tabu-list"></ul>
    </div>
  </div>
  <div class="btns">
    <button id="btn-step" type="button">Step ×1</button>
    <button id="btn-run" type="button">Run</button>
    <button id="btn-mode" type="button" class="ghost">Switch to Hill Climb</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
  <p class="hint">
    <b>Tabu mode:</b> the algorithm may go uphill temporarily — the tabu list (right) blocks revisiting recent swaps, forcing exploration. <b>Hill Climb mode:</b> only improves; freezes at the first local optimum.
  </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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Tabu search on a 10-city tour (2-opt swap variant).
// At each step the best non-tabu swap is chosen; if it beats the best-known
// solution we apply the aspiration criterion and allow it even if tabu. Hill-climb mode only accepts improving swaps.

const CITIES = [
  [60,50],[220,40],[270,130],[240,230],[150,260],
  [50,240],[20,150],[100,160],[180,100],[130,220]
];
const N = CITIES.length;
const TENURE = 5;
const PAD = 18;
const CW = 300, CH = 280;

function dist(a, b) {
  const dx = CITIES[a][0] - CITIES[b][0], dy = CITIES[a][1] - CITIES[b][1];
  return Math.sqrt(dx*dx + dy*dy);
}
function tourLen(t) {
  let s = 0;
  for (let i = 0; i < N; i++) s += dist(t[i], t[(i+1)%N]);
  return s;
}
// Apply 2-opt swap: reverse segment [i+1 .. j]
function swap2opt(t, i, j) {
  const r = t.slice();
  let l = i+1, h = j;
  while (l < h) { [r[l], r[h]] = [r[h], r[l]]; l++; h--; }
  return r;
}
function swapKey(i, j) { return i < j ? i+','+j : j+','+i; }

let tour, bestTour, bestLen, tabuMap, step, running, hillClimb, animId;

function init() {
  tour = Array.from({length:N},(_,i)=>i);
  // simple greedy start: nearest neighbour
  const used = new Set([0]); const t = [0];
  while (t.length < N) {
    const last = t[t.length-1];
    let nb = -1, nd = Infinity;
    for (let j = 0; j < N; j++) if (!used.has(j)) {
      const d = dist(last, j); if (d < nd) { nd = d; nb = j; }
    }
    used.add(nb); t.push(nb);
  }
  tour = t;
  bestTour = tour.slice();
  bestLen = tourLen(tour);
  tabuMap = {}; // key -> expiry step
  step = 0;
  updateUI();
}

function doStep() {
  step++;
  const curLen = tourLen(tour);
  let bestSwapLen = Infinity, bestI = -1, bestJ = -1;

  for (let i = 0; i < N-1; i++) {
    for (let j = i+1; j < N; j++) {
      const key = swapKey(i, j);
      const newTour = swap2opt(tour, i, j);
      const newLen = tourLen(newTour);
      const isTabu = tabuMap[key] && tabuMap[key] > step;

      if (hillClimb) {
        // hill climb: only accept improvements, ignore tabu
        if (newLen < curLen && newLen < bestSwapLen) {
          bestSwapLen = newLen; bestI = i; bestJ = j;
        }
      } else {
        // tabu search: pick best non-tabu, or tabu if it beats global best (aspiration)
        const aspirationOk = newLen < bestLen;
        if (!isTabu || aspirationOk) {
          if (newLen < bestSwapLen) {
            bestSwapLen = newLen; bestI = i; bestJ = j;
          }
        }
      }
    }
  }

  if (bestI === -1) {
    // no improving swap found (hill climb stuck) or all tabu
    stopRun();
    updateUI();
    return;
  }

  const key = swapKey(bestI, bestJ);
  tabuMap[key] = step + TENURE;
  tour = swap2opt(tour, bestI, bestJ);
  const newLen = tourLen(tour);
  if (newLen < bestLen) { bestLen = newLen; bestTour = tour.slice(); }
  updateUI();
}

function updateUI() {
  document.getElementById('len').textContent = tourLen(tour).toFixed(1);
  document.getElementById('best').textContent = bestLen.toFixed(1);
  document.getElementById('step').textContent = step;
  document.getElementById('mode-label').textContent = hillClimb ? 'Hill Climb' : 'Tabu';
  // tabu list
  const ul = document.getElementById('tabu-list');
  ul.innerHTML = '';
  const active = Object.entries(tabuMap)
    .filter(([,exp]) => exp > step)
    .sort((a,b)=>b[1]-a[1]);
  if (active.length === 0) {
    const li = document.createElement('li');
    li.textContent = '(empty)';
    li.style.background = '#f0f0f0';
    li.style.border = '1px solid #ccc';
    li.style.color = '#888';
    ul.appendChild(li);
  } else {
    active.forEach(([key, exp]) => {
      const li = document.createElement('li');
      li.textContent = fmt('swap(%replace%) — %max%★ left', { replace: key.replace(',',', '), max: Math.max(0,exp-step) });
      ul.appendChild(li);
    });
  }
  draw();
}

function draw() {
  const canvas = document.getElementById('tour');
  const ctx = canvas.getContext('2d');
  ctx.clearRect(0, 0, CW, CH);
  // scale cities to canvas
  const xs = CITIES.map(c=>c[0]), ys = CITIES.map(c=>c[1]);
  const minX=Math.min(...xs), maxX=Math.max(...xs), minY=Math.min(...ys), maxY=Math.max(...ys);
  function px(i) {
    const [x,y] = CITIES[i];
    return [PAD+(x-minX)/(maxX-minX)*(CW-2*PAD), PAD+(y-minY)/(maxY-minY)*(CH-2*PAD)];
  }
  // draw tour edges
  ctx.strokeStyle = '#457b9d'; ctx.lineWidth = 2;
  ctx.beginPath();
  const [sx,sy] = px(tour[0]); ctx.moveTo(sx,sy);
  for (let i = 1; i < N; i++) { const [ex,ey]=px(tour[i]); ctx.lineTo(ex,ey); }
  ctx.closePath(); ctx.stroke();
  // draw best tour edges (lighter)
  ctx.strokeStyle = '#a8d5ba'; ctx.lineWidth = 1; ctx.setLineDash([4,4]);
  ctx.beginPath();
  const [bsx,bsy]=px(bestTour[0]); ctx.moveTo(bsx,bsy);
  for (let i=1;i<N;i++){const [bex,bey]=px(bestTour[i]);ctx.lineTo(bex,bey);}
  ctx.closePath(); ctx.stroke();
  ctx.setLineDash([]);
  // draw cities
  for (let i = 0; i < N; i++) {
    const [cx,cy] = px(i);
    ctx.beginPath(); ctx.arc(cx, cy, 7, 0, Math.PI*2);
    ctx.fillStyle = i === tour[0] ? '#e63946' : '#1d3557';
    ctx.fill(); ctx.strokeStyle='#fff'; ctx.lineWidth=1.5; ctx.stroke();
    ctx.fillStyle='#fff'; ctx.font='bold 9px system-ui'; ctx.textAlign='center'; ctx.textBaseline='middle';
    ctx.fillText(i+1, cx, cy);
  }
}

function stopRun() {
  running = false;
  if (animId) { clearTimeout(animId); animId = null; }
  document.getElementById('btn-run').textContent = 'Run';
  document.getElementById('btn-step').disabled = false;
}

function startRun() {
  running = true;
  document.getElementById('btn-run').textContent = 'Pause';
  document.getElementById('btn-step').disabled = true;
  function tick() {
    if (!running) return;
    doStep();
    animId = setTimeout(tick, 220);
  }
  tick();
}

hillClimb = false;

document.getElementById('btn-step').addEventListener('click', () => { if (!running) doStep(); });
document.getElementById('btn-run').addEventListener('click', () => {
  if (running) stopRun(); else startRun();
});
document.getElementById('btn-reset').addEventListener('click', () => { stopRun(); init(); });
document.getElementById('btn-mode').addEventListener('click', () => {
  hillClimb = !hillClimb;
  document.getElementById('btn-mode').textContent =
    hillClimb ? 'Switch to Tabu Search' : 'Switch to Hill Climb';
  stopRun(); init();
});

init();

// Verify: tabu search should reach a tour shorter than the greedy start
const greedyLen = tourLen(tour);
console.assert(greedyLen > 0, 'Tour length must be positive');
console.log('Demo loaded. Greedy start tour length:', greedyLen.toFixed(1));
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/tabu-search/Content licensed under CC BY-NC 4.0.