Lin–Kernighan: the heuristic that nearly solves the TSP

Introduction

The traveling salesman problem (TSP) asks for the shortest closed tour through $n$ cities. It is NP-hard: no algorithm is known that is guaranteed to solve every instance in polynomial time, and trying all $(n-1)!/2$ tours is hopeless beyond a few dozen cities.

Yet in practice the problem is treated very differently. Exact solvers have proved optimal tours for instances with tens of thousands of cities, and heuristics routinely produce tours within a fraction of a percent of the best known length on instances with millions of cities. The most influential of those heuristics was published in 1973 by Shen Lin and Brian Kernighan at Bell Labs.

The building block: local search. Start from any tour and look for a small change that shortens it, repeating until none exists.

2-opt (Croes, 1958) removes two edges and reconnects the tour the only other way that keeps it a single loop. In practice this means reversing one stretch of the tour.
3-opt (Lin, 1965) removes three edges and tries the ways of reconnecting the pieces.
Or-opt (Or, 1976) lifts a short run of 1 to 3 consecutive cities and reinserts it elsewhere, possibly reversed.

Each rule is simple, but you must decide in advance how many edges to swap. Lin–Kernighan removes that decision. It builds a move edge by edge and lets the search itself decide how deep to go, which is why it is called a variable-depth search.

The idea in one paragraph. Remove an edge $(t_1,t_2)$ from the tour. Add an edge $(t_2,t_3)$ from $t_2$ to a nearby city, which forces you to remove one of the two tour edges at $t_3$ , say $(t_3,t_4)$ . Closing the loop with $(t_4,t_1)$ gives a valid tour. If that tour is shorter, good. If not, do not give up: treat $t_4$ as the new loose end and keep going, adding $(t_4,t_5)$ , removing $(t_5,t_6)$ , and so on. Two rules keep this from running wild: the running total of removed minus added lengths (the gain) must stay positive, and an edge that was added may not be removed again.

improve(tour):
  for each city t1, for each of its two tour edges (t1,t2):
    G = |t1 t2|                       // gain so far: removed minus added
    repeat up to a depth limit:
      pick t3 near t2 with G - |t2 t3| > 0   // positive gain criterion
      t4 = the tour neighbour of t3 that keeps the tour closeable
      apply the flip; G = G - |t2 t3| + |t3 t4|
      remember the best closed tour seen (close with |t4 t1|)
      t2 = t4
    undo the flips after the best one
    if the best closed tour beat the original: accept and restart

Compare the idea with simulated annealing, which escapes bad local optima by accepting worse tours at random. Lin–Kernighan escapes them systematically: it is willing to look through a temporarily worse tour as long as the accumulated gain is still positive.

Untangle a Tour

The demo scatters up to 300 cities (uniformly, or in clusters) and builds a first tour with the nearest-neighbour rule: always walk to the closest city you have not visited yet. That tour is typically about 25% longer than the best possible, with long edges that cut across the map.

<div class="row">
  <label>Cities: <b id="n_val">100</b>
    <input id="n" type="range" min="10" max="300" step="10" value="100" aria-label="Number of cities">
  </label>
  <label>Layout
    <select id="layout"><option value="u">Uniform random</option><option value="c">Clustered</option></select>
  </label>
  <button id="new" type="button" class="ghost">New instance</button>
</div>
<canvas id="cv" role="img" aria-label="Map of the cities with the current tour drawn as a closed loop"></canvas>
<div class="stats">
  <div><span>Last method</span><b id="s_method"></b></div>
  <div><span>Tour length</span><b id="s_len"></b></div>
  <div><span>Held–Karp bound</span><b id="s_lb"></b></div>
  <div><span>Gap to bound</span><b id="s_gap"></b></div>
  <div><span>Moves applied</span><b id="s_moves"></b></div>
</div>
<div class="status" id="status" aria-live="polite"></div>
<div class="row">
  <button id="b_nn" type="button" class="ghost">Nearest neighbour</button>
  <button id="b_2opt" type="button">2-opt</button>
  <button id="b_oropt" type="button">Or-opt</button>
  <button id="b_lk" type="button">Lin–Kernighan</button>
  <button id="b_ilk" type="button">Iterated LK</button>
  <button id="b_all" type="button" class="accent">Run the pipeline</button>
</div>
<div class="row">
  <label>Speed <input id="speed" type="range" min="1" max="12" value="3" aria-label="Speed"></label>
  <label><input id="once" type="checkbox"> One move per click</label>
  <button id="pause" type="button" class="ghost" disabled>Pause</button>
</div>

:root { --fg:#1d2733; --bg:#ffffff; --mut:#5b6b7b; --edge:#1d4e89; --dot:#e63946; --line:#cdd9e3; --panel:#f1f5f9; --accent:#1d4e89; }
@media (prefers-color-scheme: dark) { :root { --fg:#e6edf3; --bg:#161b22; --mut:#9fb0c3; --edge:#6cb2ff; --dot:#ff7b86; --line:#30363d; --panel:#1f262e; --accent:#3b82c4; } }
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; padding: 4px; font-size: 14px; }
.row { display: flex; flex-wrap: wrap; gap: .4rem .6rem; align-items: center; margin: .35rem 0; }
label { display: inline-flex; align-items: center; gap: .35rem; font-size: .85rem; }
input[type=range] { width: 110px; }
select { font: inherit; padding: .2rem; background: var(--panel); color: var(--fg); border: 1px solid var(--line); border-radius: 6px; }
canvas { width: 100%; height: 300px; display: block; background: var(--panel); border: 1px solid var(--line); border-radius: 8px; }
.stats { display: grid; grid-template-columns: repeat(auto-fit, minmax(96px, 1fr)); gap: .3rem; margin: .5rem 0; }
.stats div { background: var(--panel); border: 1px solid var(--line); border-radius: 8px; padding: .25rem .5rem; }
.stats span { display: block; font-size: .7rem; color: var(--mut); }
.stats b { font: 700 .95rem ui-monospace, monospace; }
.status { min-height: 1.3em; font-weight: 600; font-size: .9rem; margin: .3rem 0; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .7rem; border: 1px solid var(--accent); background: var(--accent); color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--accent); }
button.accent { background: #0a7d33; border-color: #0a7d33; }
button:disabled { opacity: .45; cursor: default; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const $ = (id) => document.getElementById(id);
const cv = $('cv');
const ctx = cv.getContext('2d');
const MAXD = 30;
const BREADTH = 3;
const ILK_ITERS = 500;
let n = 100, pts = [], D = null, nb = [], tour = [], pos = [], seed = 7;
let moves = 0, lb = 0, lbOk = false, methodKey = 'idle', timer = null, queue = [], lkPtr = 0, lbToken = 0, ilkCount = 0;

// Small seeded random generator so instances are reproducible
function rng(s) {
  return function () {
    s |= 0; s = (s + 0x6D2B79F5) | 0;
    let t = Math.imul(s ^ (s >>> 15), 1 | s);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
function gen() {
  const r = rng(seed * 9973 + n);
  pts = [];
  const layout = $('layout').value;
  const cx = [], cy = [];
  for (let k = 0; k < 6; k++) { cx.push(0.12 + 0.76 * r()); cy.push(0.12 + 0.76 * r()); }
  for (let i = 0; i < n; i++) {
    if (layout === 'u') pts.push([r(), r()]);
    else {
      const k = Math.floor(r() * 6);
      const g1 = Math.sqrt(-2 * Math.log(r() + 1e-9)) * Math.cos(6.2831853 * r());
      const g2 = Math.sqrt(-2 * Math.log(r() + 1e-9)) * Math.cos(6.2831853 * r());
      pts.push([Math.min(0.99, Math.max(0.01, cx[k] + 0.05 * g1)), Math.min(0.99, Math.max(0.01, cy[k] + 0.05 * g2))]);
    }
  }
  D = new Float64Array(n * n);
  for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) D[i * n + j] = Math.hypot(pts[i][0] - pts[j][0], pts[i][1] - pts[j][1]);
  nb = [];
  for (let i = 0; i < n; i++) {
    const idx = [];
    for (let j = 0; j < n; j++) if (j !== i) idx.push(j);
    idx.sort((a, b) => D[i * n + a] - D[i * n + b]);
    nb.push(idx.slice(0, 8));
  }
}
const d = (a, b) => D[a * n + b];
function tourLen() { let s = 0; for (let i = 0; i < n; i++) s += d(tour[i], tour[(i + 1) % n]); return s; }
function setTour(arr) { tour = arr.slice(); for (let i = 0; i < n; i++) pos[tour[i]] = i; }
function stepC(c, dir) { return tour[(pos[c] + dir + n) % n]; }
function revPath(a, b) {
  const i = pos[a], j = pos[b];
  const len = ((j - i + n) % n) + 1;
  for (let k = 0; k < (len >> 1); k++) {
    const x = (i + k) % n, y = (j - k + n) % n;
    const cx = tour[x], cy = tour[y];
    tour[x] = cy; tour[y] = cx; pos[cy] = x; pos[cx] = y;
  }
}

// Greedy construction: always walk to the nearest unvisited city
function buildNN() {
  const start = Math.floor(Math.random() * n);
  const used = new Uint8Array(n), arr = [start];
  used[start] = 1;
  let cur = start;
  for (let k = 1; k < n; k++) {
    let best = -1, bd = Infinity;
    for (let j = 0; j < n; j++) if (!used[j] && d(cur, j) < bd) { bd = d(cur, j); best = j; }
    used[best] = 1; arr.push(best); cur = best;
  }
  setTour(arr);
}

// 2-opt: reverse a stretch of the tour whenever that removes two edges for two shorter ones
function step2opt() {
  for (let i = 0; i < n - 2; i++) {
    const a = tour[i], b = tour[i + 1];
    for (let j = i + 2; j < n; j++) {
      if (i === 0 && j === n - 1) continue;
      const c = tour[j], e = tour[(j + 1) % n];
      if (d(a, c) + d(b, e) - d(a, b) - d(c, e) < -1e-9) { revPath(b, c); return true; }
    }
  }
  return false;
}

// Or-opt: move a run of 1 to 3 cities (maybe reversed) to a cheaper place
function stepOrOpt() {
  for (let L = 1; L <= 3; L++) {
    for (let i = 0; i < n; i++) {
      const seg = [];
      for (let k = 0; k < L; k++) seg.push(tour[(i + k) % n]);
      const p = tour[(i - 1 + n) % n], nx = tour[(i + L) % n];
      const s0 = seg[0], s1 = seg[L - 1];
      const gain = d(p, s0) + d(s1, nx) - d(p, nx);
      if (gain <= 1e-9) continue;
      const rest = [];
      for (let k = 0; k < n - L; k++) rest.push(tour[(i + L + k) % n]);
      for (let k = 0; k < rest.length - 1; k++) {
        const u = rest[k], v = rest[k + 1];
        const fwd = d(u, s0) + d(s1, v) - d(u, v);
        const rev = d(u, s1) + d(s0, v) - d(u, v);
        if (fwd < gain - 1e-9 || rev < gain - 1e-9) {
          const ins = fwd <= rev ? seg : seg.slice().reverse();
          setTour(rest.slice(0, k + 1).concat(ins, rest.slice(k + 1)));
          return true;
        }
      }
    }
  }
  return false;
}

// Simplified Lin-Kernighan: chain of 2-opt flips, positive partial gain, no re-removal of added edges, keep the best prefix
const ekey = (a, b) => (a < b ? a * n + b : b * n + a);
function lkFrom(t1, dir, alt) {
  const flips = [];
  const added = new Set();
  let cur2 = stepC(t1, dir);
  let g = d(t1, cur2), best = 0, bestK = 0;
  for (let depth = 0; depth < MAXD; depth++) {
    const cands = [];
    for (const t3 of nb[cur2]) {
      const g1 = g - d(cur2, t3);
      if (g1 <= 1e-9) break;
      if (t3 === t1 || t3 === stepC(cur2, dir)) continue;
      const t4 = stepC(t3, -dir);
      if (added.has(ekey(t3, t4))) continue;
      cands.push([g1 + d(t3, t4), t3, t4]);
    }
    if (!cands.length) break;
    cands.sort((x, y) => y[0] - x[0]);
    const pick = depth === 0 ? cands[alt] : cands[0];
    if (!pick) break;
    const t3 = pick[1], t4 = pick[2];
    if (dir > 0) revPath(cur2, t4); else revPath(t4, cur2);
    flips.push([cur2, t4, dir]);
    added.add(ekey(cur2, t3));
    g = pick[0];
    cur2 = t4;
    const closed = g - d(t4, t1);
    if (closed > best + 1e-9) { best = closed; bestK = flips.length; }
  }
  while (flips.length > bestK) {
    const f = flips.pop();
    if (f[2] > 0) revPath(f[1], f[0]); else revPath(f[0], f[1]);
  }
  return best > 0;
}
function stepLK() {
  for (let k = 0; k < n; k++) {
    const t1 = tour[(lkPtr + k) % n];
    for (const dir of [1, -1]) {
      for (let alt = 0; alt < BREADTH; alt++) {
        if (lkFrom(t1, dir, alt)) { lkPtr = (lkPtr + k) % n; return true; }
      }
    }
  }
  return false;
}

// Iterated LK: random double-bridge kick, repair with LK, keep only if shorter
function stepILK() {
  ilkCount++;
  const before = tour.slice(), old = tourLen();
  const p = Math.floor(Math.random() * n);
  const arr = [];
  for (let k = 0; k < n; k++) arr.push(tour[(p + 1 + k) % n]);
  const span = Math.min(n - 1, 50);
  const cuts = [];
  while (cuts.length < 3) { const c = 1 + Math.floor(Math.random() * (span - 1)); if (!cuts.includes(c)) cuts.push(c); }
  cuts.sort((x, y) => x - y);
  const a = cuts[0], b = cuts[1], c = cuts[2];
  setTour(arr.slice(0, a).concat(arr.slice(b, c), arr.slice(a, b), arr.slice(c)));
  let guard = 0;
  while (guard++ < 300 && stepLK());
  if (tourLen() > old - 1e-9) { setTour(before); return false; }
  return true;
}

// Held-Karp bound: 1-trees with node penalties improved by subgradient steps
function heldKarp(ub) {
  const pi = new Float64Array(n);
  let bestW = 0, lambda = 2, stall = 0;
  const deg = new Int32Array(n);
  for (let it = 0; it < 250; it++) {
    const inT = new Uint8Array(n), best = new Float64Array(n).fill(Infinity), par = new Int32Array(n).fill(-1);
    deg.fill(0);
    let w = 0;
    best[1] = 0;
    for (let k = 1; k < n; k++) {
      let u = -1, bu = Infinity;
      for (let v = 1; v < n; v++) if (!inT[v] && best[v] < bu) { bu = best[v]; u = v; }
      inT[u] = 1;
      if (par[u] >= 0) { w += bu; deg[u]++; deg[par[u]]++; }
      for (let v = 1; v < n; v++) {
        if (!inT[v]) { const c = d(u, v) + pi[u] + pi[v]; if (c < best[v]) { best[v] = c; par[v] = u; } }
      }
    }
    let m1 = Infinity, m2 = Infinity, i1 = -1, i2 = -1;
    for (let v = 1; v < n; v++) {
      const c = d(0, v) + pi[0] + pi[v];
      if (c < m1) { m2 = m1; i2 = i1; m1 = c; i1 = v; } else if (c < m2) { m2 = c; i2 = v; }
    }
    w += m1 + m2; deg[0] = 2; deg[i1]++; deg[i2]++;
    let sp = 0;
    for (let i = 0; i < n; i++) sp += pi[i];
    const bound = w - 2 * sp;
    if (bound > bestW + 1e-12) { bestW = bound; stall = 0; } else if (++stall >= 15) { lambda *= 0.5; stall = 0; }
    let nrm = 0;
    for (let i = 0; i < n; i++) nrm += (deg[i] - 2) * (deg[i] - 2);
    if (nrm === 0) break;
    const t = lambda * (ub - bound) / nrm;
    for (let i = 0; i < n; i++) pi[i] += t * (deg[i] - 2);
  }
  return bestW;
}
function computeBound() {
  const token = ++lbToken;
  lbOk = false; lb = 0; showStats();
  setTimeout(function () {
    if (token !== lbToken) return;
    lb = heldKarp(tourLen());
    lbOk = true;
    showStats();
  }, 20);
}

// Drawing and statistics
function css(name) { return getComputedStyle(document.documentElement).getPropertyValue(name).trim(); }
function draw() {
  const w = cv.clientWidth, h = cv.clientHeight;
  const dpr = window.devicePixelRatio || 1;
  if (cv.width !== Math.round(w * dpr)) { cv.width = Math.round(w * dpr); cv.height = Math.round(h * dpr); }
  ctx.setTransform(dpr, 0, 0, dpr, 0, 0);
  ctx.clearRect(0, 0, w, h);
  const pad = 10, X = (p) => pad + p[0] * (w - 2 * pad), Y = (p) => pad + p[1] * (h - 2 * pad);
  ctx.strokeStyle = css('--edge'); ctx.lineWidth = 1.4; ctx.lineJoin = 'round';
  ctx.beginPath();
  for (let i = 0; i <= n; i++) {
    const p = pts[tour[i % n]];
    if (i === 0) ctx.moveTo(X(p), Y(p)); else ctx.lineTo(X(p), Y(p));
  }
  ctx.stroke();
  ctx.fillStyle = css('--dot');
  const r = n > 200 ? 1.8 : 2.6;
  for (const p of pts) { ctx.beginPath(); ctx.arc(X(p), Y(p), r, 0, 6.2832); ctx.fill(); }
}
function showStats() {
  const L = tourLen();
  $('s_len').textContent = L.toFixed(3);
  $('s_lb').textContent = lbOk ? lb.toFixed(3) : '…';
  $('s_gap').textContent = lbOk ? ((L / lb - 1) * 100).toFixed(2) + '%' : '…';
  $('s_moves').textContent = String(moves);
  const names = { idle: "-", nn: "Nearest neighbour", twoopt: "2-opt", oropt: "Or-opt", lk: "Lin–Kernighan", ilk: "Iterated LK", all: "2-opt, Or-opt, LK" };
  $('s_method').textContent = names[methodKey];
  draw();
}

// Animation driver and buttons
const STEPS = { twoopt: step2opt, oropt: stepOrOpt, lk: stepLK, ilk: stepILK };
function stop() { if (timer) { clearInterval(timer); timer = null; } queue = []; $('pause').disabled = true; }
function finish() {
  stop();
  $('status').textContent = i18nFmt("Local optimum reached: %gap%% above the bound.", { gap: lbOk ? ((tourLen() / lb - 1) * 100).toFixed(2) : '?' });
}
function runQueue(list, label) {
  stop();
  queue = list.slice();
  methodKey = label;
  ilkCount = 0;
  const once = $('once').checked;
  function tick() {
    let k = once ? 1 : Number($('speed').value);
    const t0 = performance.now();
    while (k-- > 0 && performance.now() - t0 < 30) {
      if (!queue.length) { finish(); showStats(); return; }
      const name = queue[0];
      const ok = STEPS[name]();
      if (ok) moves++;
      if (name === 'ilk') { if (ilkCount >= ILK_ITERS) queue.shift(); }
      else if (!ok) queue.shift();
    }
    if (!queue.length) { finish(); }
    showStats();
  }
  $('status').textContent = "Improving the tour…";
  if (once) { tick(); stopKeepStatus(); return; }
  $('pause').disabled = false;
  timer = setInterval(tick, 30);
}
function stopKeepStatus() { if (timer) { clearInterval(timer); timer = null; } $('pause').disabled = true; }
function reset(newSeed) {
  stop();
  if (newSeed) seed++;
  n = Number($('n').value);
  $('n_val').textContent = String(n);
  gen(); buildNN(); moves = 0; lkPtr = 0; methodKey = 'nn';
  $('status').textContent = "Nearest-neighbour tour built. Pick an improvement method.";
  showStats(); computeBound();
}
$('n').addEventListener('input', () => reset(false));
$('layout').addEventListener('change', () => reset(false));
$('new').addEventListener('click', () => reset(true));
$('b_nn').addEventListener('click', () => { stop(); buildNN(); moves = 0; methodKey = 'nn'; $('status').textContent = "Nearest-neighbour tour built. Pick an improvement method."; showStats(); });
$('b_2opt').addEventListener('click', () => runQueue(['twoopt'], 'twoopt'));
$('b_oropt').addEventListener('click', () => runQueue(['oropt'], 'oropt'));
$('b_lk').addEventListener('click', () => runQueue(['lk'], 'lk'));
$('b_ilk').addEventListener('click', () => runQueue(['lk', 'ilk'], 'ilk'));
$('b_all').addEventListener('click', () => runQueue(['twoopt', 'oropt', 'twoopt', 'lk'], 'all'));
$('pause').addEventListener('click', () => { stop(); $('status').textContent = "Paused."; });
window.addEventListener('resize', draw);
reset(false);

<div class="row">
  <label>Cities: <b id="n_val">100</b>
    <input id="n" type="range" min="10" max="300" step="10" value="100" aria-label="Number of cities">
  </label>
  <label>Layout
    <select id="layout"><option value="u">Uniform random</option><option value="c">Clustered</option></select>
  </label>
  <button id="new" type="button" class="ghost">New instance</button>
</div>
<canvas id="cv" role="img" aria-label="Map of the cities with the current tour drawn as a closed loop"></canvas>
<div class="stats">
  <div><span>Last method</span><b id="s_method"></b></div>
  <div><span>Tour length</span><b id="s_len"></b></div>
  <div><span>Held–Karp bound</span><b id="s_lb"></b></div>
  <div><span>Gap to bound</span><b id="s_gap"></b></div>
  <div><span>Moves applied</span><b id="s_moves"></b></div>
</div>
<div class="status" id="status" aria-live="polite"></div>
<div class="row">
  <button id="b_nn" type="button" class="ghost">Nearest neighbour</button>
  <button id="b_2opt" type="button">2-opt</button>
  <button id="b_oropt" type="button">Or-opt</button>
  <button id="b_lk" type="button">Lin–Kernighan</button>
  <button id="b_ilk" type="button">Iterated LK</button>
  <button id="b_all" type="button" class="accent">Run the pipeline</button>
</div>
<div class="row">
  <label>Speed <input id="speed" type="range" min="1" max="12" value="3" aria-label="Speed"></label>
  <label><input id="once" type="checkbox"> One move per click</label>
  <button id="pause" type="button" class="ghost" disabled>Pause</button>
</div>

:root { --fg:#1d2733; --bg:#ffffff; --mut:#5b6b7b; --edge:#1d4e89; --dot:#e63946; --line:#cdd9e3; --panel:#f1f5f9; --accent:#1d4e89; }
@media (prefers-color-scheme: dark) { :root { --fg:#e6edf3; --bg:#161b22; --mut:#9fb0c3; --edge:#6cb2ff; --dot:#ff7b86; --line:#30363d; --panel:#1f262e; --accent:#3b82c4; } }
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; padding: 4px; font-size: 14px; }
.row { display: flex; flex-wrap: wrap; gap: .4rem .6rem; align-items: center; margin: .35rem 0; }
label { display: inline-flex; align-items: center; gap: .35rem; font-size: .85rem; }
input[type=range] { width: 110px; }
select { font: inherit; padding: .2rem; background: var(--panel); color: var(--fg); border: 1px solid var(--line); border-radius: 6px; }
canvas { width: 100%; height: 300px; display: block; background: var(--panel); border: 1px solid var(--line); border-radius: 8px; }
.stats { display: grid; grid-template-columns: repeat(auto-fit, minmax(96px, 1fr)); gap: .3rem; margin: .5rem 0; }
.stats div { background: var(--panel); border: 1px solid var(--line); border-radius: 8px; padding: .25rem .5rem; }
.stats span { display: block; font-size: .7rem; color: var(--mut); }
.stats b { font: 700 .95rem ui-monospace, monospace; }
.status { min-height: 1.3em; font-weight: 600; font-size: .9rem; margin: .3rem 0; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .7rem; border: 1px solid var(--accent); background: var(--accent); color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--accent); }
button.accent { background: #0a7d33; border-color: #0a7d33; }
button:disabled { opacity: .45; cursor: default; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const $ = (id) => document.getElementById(id);
const cv = $('cv');
const ctx = cv.getContext('2d');
const MAXD = 30;
const BREADTH = 3;
const ILK_ITERS = 500;
let n = 100, pts = [], D = null, nb = [], tour = [], pos = [], seed = 7;
let moves = 0, lb = 0, lbOk = false, methodKey = 'idle', timer = null, queue = [], lkPtr = 0, lbToken = 0, ilkCount = 0;

// Small seeded random generator so instances are reproducible
function rng(s) {
  return function () {
    s |= 0; s = (s + 0x6D2B79F5) | 0;
    let t = Math.imul(s ^ (s >>> 15), 1 | s);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
function gen() {
  const r = rng(seed * 9973 + n);
  pts = [];
  const layout = $('layout').value;
  const cx = [], cy = [];
  for (let k = 0; k < 6; k++) { cx.push(0.12 + 0.76 * r()); cy.push(0.12 + 0.76 * r()); }
  for (let i = 0; i < n; i++) {
    if (layout === 'u') pts.push([r(), r()]);
    else {
      const k = Math.floor(r() * 6);
      const g1 = Math.sqrt(-2 * Math.log(r() + 1e-9)) * Math.cos(6.2831853 * r());
      const g2 = Math.sqrt(-2 * Math.log(r() + 1e-9)) * Math.cos(6.2831853 * r());
      pts.push([Math.min(0.99, Math.max(0.01, cx[k] + 0.05 * g1)), Math.min(0.99, Math.max(0.01, cy[k] + 0.05 * g2))]);
    }
  }
  D = new Float64Array(n * n);
  for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) D[i * n + j] = Math.hypot(pts[i][0] - pts[j][0], pts[i][1] - pts[j][1]);
  nb = [];
  for (let i = 0; i < n; i++) {
    const idx = [];
    for (let j = 0; j < n; j++) if (j !== i) idx.push(j);
    idx.sort((a, b) => D[i * n + a] - D[i * n + b]);
    nb.push(idx.slice(0, 8));
  }
}
const d = (a, b) => D[a * n + b];
function tourLen() { let s = 0; for (let i = 0; i < n; i++) s += d(tour[i], tour[(i + 1) % n]); return s; }
function setTour(arr) { tour = arr.slice(); for (let i = 0; i < n; i++) pos[tour[i]] = i; }
function stepC(c, dir) { return tour[(pos[c] + dir + n) % n]; }
function revPath(a, b) {
  const i = pos[a], j = pos[b];
  const len = ((j - i + n) % n) + 1;
  for (let k = 0; k < (len >> 1); k++) {
    const x = (i + k) % n, y = (j - k + n) % n;
    const cx = tour[x], cy = tour[y];
    tour[x] = cy; tour[y] = cx; pos[cy] = x; pos[cx] = y;
  }
}

// Greedy construction: always walk to the nearest unvisited city
function buildNN() {
  const start = Math.floor(Math.random() * n);
  const used = new Uint8Array(n), arr = [start];
  used[start] = 1;
  let cur = start;
  for (let k = 1; k < n; k++) {
    let best = -1, bd = Infinity;
    for (let j = 0; j < n; j++) if (!used[j] && d(cur, j) < bd) { bd = d(cur, j); best = j; }
    used[best] = 1; arr.push(best); cur = best;
  }
  setTour(arr);
}

// 2-opt: reverse a stretch of the tour whenever that removes two edges for two shorter ones
function step2opt() {
  for (let i = 0; i < n - 2; i++) {
    const a = tour[i], b = tour[i + 1];
    for (let j = i + 2; j < n; j++) {
      if (i === 0 && j === n - 1) continue;
      const c = tour[j], e = tour[(j + 1) % n];
      if (d(a, c) + d(b, e) - d(a, b) - d(c, e) < -1e-9) { revPath(b, c); return true; }
    }
  }
  return false;
}

// Or-opt: move a run of 1 to 3 cities (maybe reversed) to a cheaper place
function stepOrOpt() {
  for (let L = 1; L <= 3; L++) {
    for (let i = 0; i < n; i++) {
      const seg = [];
      for (let k = 0; k < L; k++) seg.push(tour[(i + k) % n]);
      const p = tour[(i - 1 + n) % n], nx = tour[(i + L) % n];
      const s0 = seg[0], s1 = seg[L - 1];
      const gain = d(p, s0) + d(s1, nx) - d(p, nx);
      if (gain <= 1e-9) continue;
      const rest = [];
      for (let k = 0; k < n - L; k++) rest.push(tour[(i + L + k) % n]);
      for (let k = 0; k < rest.length - 1; k++) {
        const u = rest[k], v = rest[k + 1];
        const fwd = d(u, s0) + d(s1, v) - d(u, v);
        const rev = d(u, s1) + d(s0, v) - d(u, v);
        if (fwd < gain - 1e-9 || rev < gain - 1e-9) {
          const ins = fwd <= rev ? seg : seg.slice().reverse();
          setTour(rest.slice(0, k + 1).concat(ins, rest.slice(k + 1)));
          return true;
        }
      }
    }
  }
  return false;
}

// Simplified Lin-Kernighan: chain of 2-opt flips, positive partial gain, no re-removal of added edges, keep the best prefix
const ekey = (a, b) => (a < b ? a * n + b : b * n + a);
function lkFrom(t1, dir, alt) {
  const flips = [];
  const added = new Set();
  let cur2 = stepC(t1, dir);
  let g = d(t1, cur2), best = 0, bestK = 0;
  for (let depth = 0; depth < MAXD; depth++) {
    const cands = [];
    for (const t3 of nb[cur2]) {
      const g1 = g - d(cur2, t3);
      if (g1 <= 1e-9) break;
      if (t3 === t1 || t3 === stepC(cur2, dir)) continue;
      const t4 = stepC(t3, -dir);
      if (added.has(ekey(t3, t4))) continue;
      cands.push([g1 + d(t3, t4), t3, t4]);
    }
    if (!cands.length) break;
    cands.sort((x, y) => y[0] - x[0]);
    const pick = depth === 0 ? cands[alt] : cands[0];
    if (!pick) break;
    const t3 = pick[1], t4 = pick[2];
    if (dir > 0) revPath(cur2, t4); else revPath(t4, cur2);
    flips.push([cur2, t4, dir]);
    added.add(ekey(cur2, t3));
    g = pick[0];
    cur2 = t4;
    const closed = g - d(t4, t1);
    if (closed > best + 1e-9) { best = closed; bestK = flips.length; }
  }
  while (flips.length > bestK) {
    const f = flips.pop();
    if (f[2] > 0) revPath(f[1], f[0]); else revPath(f[0], f[1]);
  }
  return best > 0;
}
function stepLK() {
  for (let k = 0; k < n; k++) {
    const t1 = tour[(lkPtr + k) % n];
    for (const dir of [1, -1]) {
      for (let alt = 0; alt < BREADTH; alt++) {
        if (lkFrom(t1, dir, alt)) { lkPtr = (lkPtr + k) % n; return true; }
      }
    }
  }
  return false;
}

// Iterated LK: random double-bridge kick, repair with LK, keep only if shorter
function stepILK() {
  ilkCount++;
  const before = tour.slice(), old = tourLen();
  const p = Math.floor(Math.random() * n);
  const arr = [];
  for (let k = 0; k < n; k++) arr.push(tour[(p + 1 + k) % n]);
  const span = Math.min(n - 1, 50);
  const cuts = [];
  while (cuts.length < 3) { const c = 1 + Math.floor(Math.random() * (span - 1)); if (!cuts.includes(c)) cuts.push(c); }
  cuts.sort((x, y) => x - y);
  const a = cuts[0], b = cuts[1], c = cuts[2];
  setTour(arr.slice(0, a).concat(arr.slice(b, c), arr.slice(a, b), arr.slice(c)));
  let guard = 0;
  while (guard++ < 300 && stepLK());
  if (tourLen() > old - 1e-9) { setTour(before); return false; }
  return true;
}

// Held-Karp bound: 1-trees with node penalties improved by subgradient steps
function heldKarp(ub) {
  const pi = new Float64Array(n);
  let bestW = 0, lambda = 2, stall = 0;
  const deg = new Int32Array(n);
  for (let it = 0; it < 250; it++) {
    const inT = new Uint8Array(n), best = new Float64Array(n).fill(Infinity), par = new Int32Array(n).fill(-1);
    deg.fill(0);
    let w = 0;
    best[1] = 0;
    for (let k = 1; k < n; k++) {
      let u = -1, bu = Infinity;
      for (let v = 1; v < n; v++) if (!inT[v] && best[v] < bu) { bu = best[v]; u = v; }
      inT[u] = 1;
      if (par[u] >= 0) { w += bu; deg[u]++; deg[par[u]]++; }
      for (let v = 1; v < n; v++) {
        if (!inT[v]) { const c = d(u, v) + pi[u] + pi[v]; if (c < best[v]) { best[v] = c; par[v] = u; } }
      }
    }
    let m1 = Infinity, m2 = Infinity, i1 = -1, i2 = -1;
    for (let v = 1; v < n; v++) {
      const c = d(0, v) + pi[0] + pi[v];
      if (c < m1) { m2 = m1; i2 = i1; m1 = c; i1 = v; } else if (c < m2) { m2 = c; i2 = v; }
    }
    w += m1 + m2; deg[0] = 2; deg[i1]++; deg[i2]++;
    let sp = 0;
    for (let i = 0; i < n; i++) sp += pi[i];
    const bound = w - 2 * sp;
    if (bound > bestW + 1e-12) { bestW = bound; stall = 0; } else if (++stall >= 15) { lambda *= 0.5; stall = 0; }
    let nrm = 0;
    for (let i = 0; i < n; i++) nrm += (deg[i] - 2) * (deg[i] - 2);
    if (nrm === 0) break;
    const t = lambda * (ub - bound) / nrm;
    for (let i = 0; i < n; i++) pi[i] += t * (deg[i] - 2);
  }
  return bestW;
}
function computeBound() {
  const token = ++lbToken;
  lbOk = false; lb = 0; showStats();
  setTimeout(function () {
    if (token !== lbToken) return;
    lb = heldKarp(tourLen());
    lbOk = true;
    showStats();
  }, 20);
}

// Drawing and statistics
function css(name) { return getComputedStyle(document.documentElement).getPropertyValue(name).trim(); }
function draw() {
  const w = cv.clientWidth, h = cv.clientHeight;
  const dpr = window.devicePixelRatio || 1;
  if (cv.width !== Math.round(w * dpr)) { cv.width = Math.round(w * dpr); cv.height = Math.round(h * dpr); }
  ctx.setTransform(dpr, 0, 0, dpr, 0, 0);
  ctx.clearRect(0, 0, w, h);
  const pad = 10, X = (p) => pad + p[0] * (w - 2 * pad), Y = (p) => pad + p[1] * (h - 2 * pad);
  ctx.strokeStyle = css('--edge'); ctx.lineWidth = 1.4; ctx.lineJoin = 'round';
  ctx.beginPath();
  for (let i = 0; i <= n; i++) {
    const p = pts[tour[i % n]];
    if (i === 0) ctx.moveTo(X(p), Y(p)); else ctx.lineTo(X(p), Y(p));
  }
  ctx.stroke();
  ctx.fillStyle = css('--dot');
  const r = n > 200 ? 1.8 : 2.6;
  for (const p of pts) { ctx.beginPath(); ctx.arc(X(p), Y(p), r, 0, 6.2832); ctx.fill(); }
}
function showStats() {
  const L = tourLen();
  $('s_len').textContent = L.toFixed(3);
  $('s_lb').textContent = lbOk ? lb.toFixed(3) : '…';
  $('s_gap').textContent = lbOk ? ((L / lb - 1) * 100).toFixed(2) + '%' : '…';
  $('s_moves').textContent = String(moves);
  const names = { idle: "-", nn: "Nearest neighbour", twoopt: "2-opt", oropt: "Or-opt", lk: "Lin–Kernighan", ilk: "Iterated LK", all: "2-opt, Or-opt, LK" };
  $('s_method').textContent = names[methodKey];
  draw();
}

// Animation driver and buttons
const STEPS = { twoopt: step2opt, oropt: stepOrOpt, lk: stepLK, ilk: stepILK };
function stop() { if (timer) { clearInterval(timer); timer = null; } queue = []; $('pause').disabled = true; }
function finish() {
  stop();
  $('status').textContent = i18nFmt("Local optimum reached: %gap%% above the bound.", { gap: lbOk ? ((tourLen() / lb - 1) * 100).toFixed(2) : '?' });
}
function runQueue(list, label) {
  stop();
  queue = list.slice();
  methodKey = label;
  ilkCount = 0;
  const once = $('once').checked;
  function tick() {
    let k = once ? 1 : Number($('speed').value);
    const t0 = performance.now();
    while (k-- > 0 && performance.now() - t0 < 30) {
      if (!queue.length) { finish(); showStats(); return; }
      const name = queue[0];
      const ok = STEPS[name]();
      if (ok) moves++;
      if (name === 'ilk') { if (ilkCount >= ILK_ITERS) queue.shift(); }
      else if (!ok) queue.shift();
    }
    if (!queue.length) { finish(); }
    showStats();
  }
  $('status').textContent = "Improving the tour…";
  if (once) { tick(); stopKeepStatus(); return; }
  $('pause').disabled = false;
  timer = setInterval(tick, 30);
}
function stopKeepStatus() { if (timer) { clearInterval(timer); timer = null; } $('pause').disabled = true; }
function reset(newSeed) {
  stop();
  if (newSeed) seed++;
  n = Number($('n').value);
  $('n_val').textContent = String(n);
  gen(); buildNN(); moves = 0; lkPtr = 0; methodKey = 'nn';
  $('status').textContent = "Nearest-neighbour tour built. Pick an improvement method.";
  showStats(); computeBound();
}
$('n').addEventListener('input', () => reset(false));
$('layout').addEventListener('change', () => reset(false));
$('new').addEventListener('click', () => reset(true));
$('b_nn').addEventListener('click', () => { stop(); buildNN(); moves = 0; methodKey = 'nn'; $('status').textContent = "Nearest-neighbour tour built. Pick an improvement method."; showStats(); });
$('b_2opt').addEventListener('click', () => runQueue(['twoopt'], 'twoopt'));
$('b_oropt').addEventListener('click', () => runQueue(['oropt'], 'oropt'));
$('b_lk').addEventListener('click', () => runQueue(['lk'], 'lk'));
$('b_ilk').addEventListener('click', () => runQueue(['lk', 'ilk'], 'ilk'));
$('b_all').addEventListener('click', () => runQueue(['twoopt', 'oropt', 'twoopt', 'lk'], 'all'));
$('pause').addEventListener('click', () => { stop(); $('status').textContent = "Paused."; });
window.addEventListener('resize', draw);
reset(false);

Result

Console

Try this sequence:

Press 2-opt. Crossing edges disappear. Tick One move per click to watch single moves.
Press Or-opt. Stray cities that 2-opt could not rescue slide into better places.
Press Lin–Kernighan. Chains of several flips find improvements that no single 2-opt or Or-opt move can.
Press Iterated LK. After each local optimum the search kicks the tour with a random perturbation, repairs it, and keeps the result only if it is shorter.

The Held–Karp bound is a lower bound on the optimal tour, computed from penalised minimum 1-trees. The gap is measured against that bound, so it overstates the true distance to the optimum: on random uniform instances the optimal tour typically sits less than 1% above the bound. On clustered instances the bound is looser.

The Real Complexity

The problem. The TSP is NP-hard, and the decision version is NP-complete. Brute force examines $(n-1)!/2$ tours. The classic dynamic program of Bellman and of Held and Karp (1962) brings this to $O(n^{2}2^{n})$ time and $O(n2^{n})$ memory, still exponential.

Cost of local search. Checking whether any improving 2-opt move exists takes $O(n^{2})$ time with a plain scan, since there are $\binom{n}{2}-n$ pairs of edges. A naive 3-opt scan costs $O(n^{3})$ . Practical codes avoid this by only considering each city's $K$ nearest neighbours as candidates, typically $K$ between 5 and 10, and by don't-look bits that skip cities whose neighbourhood has not changed. Then one pass costs roughly $O(nK)$ per improvement attempt, and memory is $O(nK)$ for the candidate lists plus $O(n)$ for the tour.

The gain criterion. Writing $x_i$ for removed edges and $y_i$ for added ones, the partial gain after $i$ steps is

G_i = \sum_{j=1}^{i}\bigl(|x_j|-|y_j|\bigr),

and the search only extends a chain while $G_i>0$ . The actual improvement of closing the tour at step $i$ is $G_i^{*}=G_{i-1}+|x_i|-|y_i^{*}|$ , where $y_i^{*}$ is the closing edge. The algorithm applies the prefix with the largest $G_i^{*}$ . This criterion prunes the otherwise huge search tree: a chain whose gain has turned non-positive cannot be part of an improving move.

Quality in practice. Johnson and McGeoch's large experimental study of TSP local search (1997) reported, for random uniform instances, tours roughly 5% above the Held–Karp bound for 2-opt with neighbour lists, about 3% for 3-opt and about 2% for Lin–Kernighan, with iterated variants getting down to the vicinity of 1%. The demo above reproduces this ordering at small scale.

Worst case. There is no strong guarantee. Christofides always returns a tour at most $3/2$ times the optimum on metric instances; Lin–Kernighan has no comparable ratio, and Papadimitriou (1992) showed that finding a Lin–Kernighan local optimum is PLS-complete, so even reaching a local optimum may take exponentially many improving steps in the worst case. Such instances do not appear in practice, which is the usual gap between worst-case and typical behaviour.

Helsgaun's LKH. In 2000 Keld Helsgaun published a heavily refined implementation. Its basic move is a sequential 5-opt step rather than a 2-opt flip, and its candidate edges are chosen by alpha-nearness, computed from the same minimum 1-trees with node penalties used for the Held–Karp bound, instead of by plain geometric closeness. Each of these changes costs time per step but reaches much better tours per run.

The state of the art. The Waterloo TSP pages list, for the 1,904,711-city World TSP instance, a tour found by LKH of length 7,515,772,107 (reported in 2018) and a lower bound of 7,512,218,268 proved with the Concorde code, so the best known tour is within about 0.05% of optimal. For the 100,000-city Mona Lisa instance the best known tour (by Yuichi Nagata, 2009) has length 5,757,191 against a lower bound of 5,757,084. At the exact end, Applegate, Bixby, Chvátal and Cook solved the 85,900-city instance pla85900 to proven optimality with Concorde in 2006.

Where It Matters

Whenever something has to visit many places in a good order, a TSP lurks underneath, and Lin–Kernighan style moves are the default way to polish a solution.

Logistics and routing: vehicle routing solvers are built from TSP-like routes, and Lin–Kernighan variants are the standard local improvement inside them.
Manufacturing: drilling thousands of holes in a circuit board, plotting, or laser cutting all minimise the travel of a tool head. Several of the largest TSP benchmark instances come from exactly such VLSI layouts.
Science: ordering genetic markers, scheduling telescope pointings and X-ray crystallography sampling can all be phrased as shortest-tour problems.
Exact solvers: a very good tour is the upper bound that makes branch and cut effective, since it lets the search discard huge regions immediately.
Other metaheuristics: iterated local search wraps a strong local search such as Lin–Kernighan in a loop of kicks, exactly as the demo's Iterated LK button does.

The lower-bound side matters as much as the tours. The bound used in the demo comes from the same idea as Lagrangian relaxation applied to minimum spanning trees: a tour is a spanning-tree-like object plus one edge, and penalising the cities pushes the relaxation toward a tour.

Conclusion

Lin–Kernighan swaps a fixed neighbourhood for a search that decides how deep to go, guided by one simple rule: keep the running gain positive. That one idea, refined by decades of engineering and by Helsgaun's LKH, turned a notorious NP-hard problem into one where near-optimal tours on millions of cities are routine, and where exact solvers can certify optimality on instances with tens of thousands of cities.

It is also a reminder of what NP-hardness does and does not say. It warns that no method is guaranteed to be both fast and exact on every instance. It does not say that typical instances are hard, or that a clever heuristic cannot land within a hair of the answer. Play with the demo: after a few seconds of Lin–Kernighan, the gap to the bound is already down to a couple of percent.

Comments

Loading comments...

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

Cookies & privacy

Lin–Kernighan

How a 1973 local search tames an NP-hard problem