Introduction

Imagine you are searching for the lowest point in a rugged mountain range — at night, with only a flashlight. You walk downhill as far as you can, then stop: you are at a local optimum, the lowest point visible from where you stand. But the deepest valley might be ten kilometres away, on the other side of a ridge.

Most optimization algorithms face exactly this trap. Local search improves a solution step by step until no single change makes it better. The trouble is, "no single change" depends entirely on what you mean by change — the neighborhood structure you are using. Change the structure and a wall can become a door.

Variable Neighborhood Search (VNS), introduced by Pierre Hansen and Nenad Mladenović in 1997, turns this observation into a rigorous strategy. When local search stalls inside neighborhood k, VNS doesn't restart randomly: it shakes the solution with a larger perturbation from neighborhood k+1, then runs local search again from the new starting point. If the result is better, reset to the smallest neighborhood and keep searching; if not, widen the shake again.

The key insight is that different neighborhoods expose different structure: a swap-two-elements move cannot escape a basin that requires four simultaneous changes, but a block-reversal move can. By cycling through an ordered list of neighborhoods of increasing size, VNS systematically probes escape routes that smaller moves can never find — without surrendering the efficiency of local search.

Escape Local Optima

The landscape below has several local minima at different depths. Local Search (gradient descent on the curve) always gets trapped in the first valley it enters. VNS escapes by enlarging the perturbation radius when stuck.

<p class="hint">A bumpy landscape with several local minima. Local Search always gets trapped in the first valley. VNS escapes by enlarging the perturbation radius — <em>shaking</em> and then improving again.</p>
<div class="layout">
  <canvas id="cvs" width="340" height="200"></canvas>
  <div class="panel" id="panel">
    <div class="row"><span class="label">Algorithm</span><span id="algoName" class="val">—</span></div>
    <div class="row"><span class="label">Neighborhood k</span><span id="nbhd" class="val">—</span></div>
    <div class="row"><span class="label">Current x</span><span id="curX" class="val">—</span></div>
    <div class="row"><span class="label">Best cost</span><span id="bestCost" class="val">—</span></div>
    <div class="log" id="log"></div>
  </div>
</div>
<div class="btns">
  <button id="btnLS" type="button">Run Local Search</button>
  <button id="btnVNS" type="button">Run VNS</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.layout { display: flex; gap: 10px; align-items: flex-start; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #f5f8fb; flex-shrink: 0; }
.panel { flex: 1; min-width: 0; }
.row { display: flex; justify-content: space-between; font-size: .82rem; padding: 3px 0; border-bottom: 1px solid #eef1f4; }
.label { color: #666; }
.val { font-weight: 600; color: #1d3557; }
.log { margin-top: 6px; font-size: .78rem; color: #444; max-height: 120px; overflow-y: auto; line-height: 1.5; }
.log .entry { padding: 1px 0; }
.log .entry.good { color: #0a7d33; }
.log .entry.shake { color: #e07b00; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .6rem; }
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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// VNS demo: 1-D landscape with several local minima.
// The cost function f(x) is a sum of sinusoids designed to have a clear
// global minimum near x=0.78 and several local traps.
// Local Search: steepest descent with step 0.01.
// VNS: shake radius starts at 0.05 (k=1) and doubles each time stuck (k=2→0.10, k=3→0.20 …).

const W = 340, H = 200, PAD = { l: 28, r: 10, t: 14, b: 24 };
const XL = 0, XR = 1;  // domain [0,1]
const cvs = document.getElementById('cvs');
const ctx = cvs.getContext('2d');

// --- landscape ----------------------------------------------------------
function f(x) {
  // Multi-modal: global min ~0.78 (depth ~-2.1), several shallower traps
  return (
    Math.sin(2 * Math.PI * x) * 0.6 +
    Math.sin(5 * Math.PI * x) * 0.4 +
    Math.sin(11 * Math.PI * x) * 0.15 +
    Math.cos(7 * Math.PI * x) * 0.25 -
    0.45 * x
  );
}
// Evaluate global min for reference
let gMin = Infinity, gMinX = 0;
for (let i = 0; i <= 1000; i++) {
  const xi = i / 1000, fi = f(xi);
  if (fi < gMin) { gMin = fi; gMinX = xi; }
}

// --- coordinate helpers -------------------------------------------------
function toCanvasX(x) { return PAD.l + (x - XL) / (XR - XL) * (W - PAD.l - PAD.r); }
function toCanvasY(y) {
  const yMin = -1.5, yMax = 1.3;
  return PAD.t + (1 - (y - yMin) / (yMax - yMin)) * (H - PAD.t - PAD.b);
}

// --- drawing ------------------------------------------------------------
function drawLandscape() {
  ctx.clearRect(0, 0, W, H);
  // axes
  ctx.strokeStyle = '#ccc'; ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(PAD.l, H - PAD.b); ctx.lineTo(W - PAD.r, H - PAD.b);
  ctx.moveTo(PAD.l, PAD.t); ctx.lineTo(PAD.l, H - PAD.b);
  ctx.stroke();
  // x labels
  ctx.fillStyle = '#888'; ctx.font = '10px system-ui'; ctx.textAlign = 'center';
  for (let i = 0; i <= 4; i++) {
    const xi = i / 4;
    ctx.fillText(xi.toFixed(2), toCanvasX(xi), H - PAD.b + 12);
  }
  // curve
  ctx.strokeStyle = '#4a7fa5'; ctx.lineWidth = 2;
  ctx.beginPath();
  for (let px = PAD.l; px <= W - PAD.r; px++) {
    const x = XL + (px - PAD.l) / (W - PAD.l - PAD.r) * (XR - XL);
    const y = f(x);
    px === PAD.l ? ctx.moveTo(px, toCanvasY(y)) : ctx.lineTo(px, toCanvasY(y));
  }
  ctx.stroke();
  // global minimum marker
  ctx.strokeStyle = '#aaa'; ctx.lineWidth = 1; ctx.setLineDash([3, 3]);
  const gx = toCanvasX(gMinX), gy = toCanvasY(gMin);
  ctx.beginPath(); ctx.moveTo(gx, PAD.t); ctx.lineTo(gx, H - PAD.b); ctx.stroke();
  ctx.setLineDash([]);
  ctx.fillStyle = '#888'; ctx.font = '9px system-ui'; ctx.textAlign = 'left';
  ctx.fillText('global', gx + 2, PAD.t + 9);
}

function drawDot(x, color, radius) {
  ctx.beginPath();
  ctx.arc(toCanvasX(x), toCanvasY(f(x)), radius, 0, 2 * Math.PI);
  ctx.fillStyle = color; ctx.fill();
}

function drawShakeArc(x, radius, k) {
  const colors = ['#e07b00', '#c24b00', '#8b0000'];
  const col = colors[Math.min(k - 1, 2)];
  ctx.strokeStyle = col; ctx.lineWidth = 1.2; ctx.setLineDash([4, 3]);
  const cx = toCanvasX(x), cy = toCanvasY(f(x));
  const rx = radius / (XR - XL) * (W - PAD.l - PAD.r);
  ctx.beginPath(); ctx.ellipse(cx, cy, rx, 8, 0, 0, 2 * Math.PI);
  ctx.stroke(); ctx.setLineDash([]);
}

// --- log / panel --------------------------------------------------------
function logEntry(text, cls) {
  const div = document.createElement('div');
  div.className = 'entry' + (cls ? ' ' + cls : '');
  div.textContent = text;
  const log = document.getElementById('log');
  log.prepend(div);
}
function setPanel(algo, k, x, cost) {
  document.getElementById('algoName').textContent = algo;
  document.getElementById('nbhd').textContent = k !== null ? 'k=' + k + ' (r=' + (0.05 * Math.pow(2, k - 1)).toFixed(3) + ')' : '—';
  document.getElementById('curX').textContent = x !== null ? x.toFixed(4) : '—';
  document.getElementById('bestCost').textContent = cost !== null ? cost.toFixed(4) : '—';
}

// --- local search -------------------------------------------------------
function localSearch(startX, step) {
  // Gradient descent: try ±step, accept improvement
  let x = startX, fx = f(x);
  const MAX = 2000;
  for (let i = 0; i < MAX; i++) {
    let improved = false;
    for (const dx of [-step, step]) {
      const nx = x + dx;
      if (nx < XL || nx > XR) continue;
      const nfx = f(nx);
      if (nfx < fx) { x = nx; fx = nfx; improved = true; break; }
    }
    if (!improved) break;
  }
  return { x, fx };
}

// --- animations ---------------------------------------------------------
let running = false;

function setButtons(dis) {
  ['btnLS', 'btnVNS', 'btnReset'].forEach(id =>
    document.getElementById(id).disabled = dis);
}

async function sleep(ms) { return new Promise(r => setTimeout(r, ms)); }

async function runLocalSearch() {
  if (running) return;
  running = true; setButtons(true);
  document.getElementById('log').innerHTML = '';
  const START = 0.05;
  const STEP = 0.005;
  logEntry(fmt('Starting at x=%START%', { START: START.toFixed(3) }), '');
  setPanel('Local Search', null, START, f(START));

  drawLandscape();
  drawDot(START, '#e07b00', 5);
  await sleep(300);

  // Animate descent
  let x = START, fx = f(x);
  let prev = x;
  for (let iter = 0; iter < 2000; iter++) {
    let improved = false;
    for (const dx of [-STEP, STEP]) {
      const nx = x + dx;
      if (nx < XL || nx > XR) continue;
      const nfx = f(nx);
      if (nfx < fx) { x = nx; fx = nfx; improved = true; break; }
    }
    if (!improved) break;
    if (Math.abs(x - prev) > 0.015 || iter % 20 === 0) {
      drawLandscape();
      drawDot(x, '#c0392b', 5);
      setPanel('Local Search', null, x, fx);
      await sleep(30);
      prev = x;
    }
  }
  drawLandscape();
  drawDot(x, '#c0392b', 7);
  setPanel('Local Search', null, x, fx);
  logEntry(fmt('Trapped at x=%x% cost=%fx%', { x: x.toFixed(4), fx: fx.toFixed(4) }), '');
  logEntry(fmt('Global min is at x=%gMinX% cost=%gMin%', { gMinX: gMinX.toFixed(4), gMin: gMin.toFixed(4) }), '');
  running = false; setButtons(false);
}

async function runVNS() {
  if (running) return;
  running = true; setButtons(true);
  document.getElementById('log').innerHTML = '';
  const START = 0.05;
  const STEP = 0.005;
  const K_MAX = 5;
  const BASE_RADIUS = 0.05;
  logEntry(fmt('Starting VNS at x=%START%', { START: START.toFixed(3) }), '');

  let best = localSearch(START, STEP);
  setPanel('VNS', 1, best.x, best.fx);
  drawLandscape(); drawDot(best.x, '#2ecc71', 7);
  await sleep(400);

  let k = 1;
  let noImproveRounds = 0;
  const MAX_ROUNDS = 60;

  for (let round = 0; round < MAX_ROUNDS && k <= K_MAX; round++) {
    const radius = BASE_RADIUS * Math.pow(2, k - 1);
    // Shake: random point in [best.x - radius, best.x + radius] ∩ [0,1]
    const lo = Math.max(XL, best.x - radius);
    const hi = Math.min(XR, best.x + radius);
    const shakeX = lo + Math.random() * (hi - lo);

    // Draw shake radius
    drawLandscape(); drawDot(best.x, '#2ecc71', 7);
    drawShakeArc(best.x, radius, k);
    drawDot(shakeX, '#e07b00', 5);
    setPanel('VNS', k, shakeX, best.fx);
    logEntry(fmt('k=%k% shake→x=%shakeX%', { k: k, shakeX: shakeX.toFixed(4) }), 'shake');
    await sleep(350);

    // Local search from shake point
    const cand = localSearch(shakeX, STEP);

    drawLandscape(); drawDot(best.x, '#2ecc71', 7); drawDot(cand.x, '#e67e22', 6);
    await sleep(200);

    if (cand.fx < best.fx - 1e-6) {
      // Improvement: accept, reset k
      best = cand;
      k = 1;
      noImproveRounds = 0;
      logEntry("  " + fmt('✓ improved → x=%x% cost=%fx%', { x: best.x.toFixed(4), fx: best.fx.toFixed(4) }), 'good');
    } else {
      // No improvement: widen neighborhood
      k++;
      noImproveRounds++;
      logEntry("  " + fmt('no improvement, k→%k%', { k: k }), '');
      if (k > K_MAX) {
        logEntry('Exhausted all neighborhoods, stopping.', '');
        break;
      }
    }
    setPanel('VNS', k, best.x, best.fx);
    drawLandscape(); drawDot(best.x, '#2ecc71', 7);
    await sleep(150);
  }

  drawLandscape(); drawDot(best.x, '#27ae60', 8);
  setPanel('VNS', k > K_MAX ? K_MAX : k, best.x, best.fx);
  const gap = ((best.fx - gMin) / Math.abs(gMin) * 100).toFixed(2);
  logEntry(fmt('VNS done: x=%x% cost=%fx% (gap %gap%% from global)', { x: best.x.toFixed(4), fx: best.fx.toFixed(4), gap: gap }), 'good');
  running = false; setButtons(false);
}

document.getElementById('btnLS').addEventListener('click', runLocalSearch);
document.getElementById('btnVNS').addEventListener('click', runVNS);
document.getElementById('btnReset').addEventListener('click', () => {
  if (running) return;
  document.getElementById('log').innerHTML = '';
  setPanel('—', null, null, null);
  drawLandscape();
});

drawLandscape();
setPanel('—', null, null, null);
Result
Console

Press Run Local Search to watch a simple descender get permanently trapped. Then press Run VNS and see it shake out of each basin as the neighborhood grows. The panel on the right shows which neighborhood k is active, the current best cost, and when a shake landed in a genuinely better basin.

The Real Complexity

VNS targets problems that are NP-hard — where finding the guaranteed global optimum would require, in the worst case, exhaustive search over an exponential space. The algorithm makes no claim to solve them exactly.

What VNS does guarantee is structural:

  • Local optimality in every neighborhood: if VNS stops at a solution, it is locally optimal with respect to all neighborhood structures used — a much stronger certificate than local optimality in just one neighborhood.
  • Completeness on finite spaces: given unlimited time, VNS will visit every solution (the perturbation can reach any point); it converges to the global optimum in the limit on finite instances.
  • No polynomial guarantee: the number of shakes needed to escape all basins is problem-dependent and can be exponential. VNS is a heuristic, not an exact algorithm.

The problems VNS is typically applied to — TSP, graph coloring, bin packing, vehicle routing — are NP-hard. Exact solvers scale poorly; VNS trades optimality guarantees for the practical ability to find high-quality solutions on real-sized instances in minutes rather than millennia.

The theoretical reason VNS outperforms random restarts is the neighborhood change condition: a shake is accepted only if it lands outside the current basin of attraction of the local optimum. Switching to a larger neighborhood changes the basin boundaries, so a point that was a dead end under N1N_{1} may be on a downhill slope under N3N_{3}. This is not magic — it is geometry of the search space made algorithmic.

Where It Matters

VNS is not a curiosity — it is a workhorse in industrial and scientific optimization:

  • Vehicle routing: logistics companies use VNS-based solvers to plan delivery routes for thousands of stops. The classic VRPTW (vehicle routing with time windows) benchmark records show VNS variants consistently among the top-performing heuristics.
  • Scheduling: timetable construction for schools, hospitals, and production lines involves hundreds of mutually conflicting constraints. VNS navigates this landscape where greedy constructors stall.
  • Network design: telecommunications companies configure backbone topologies with VNS to minimize cost while guaranteeing connectivity — a problem related to Steiner tree which is NP-hard.
  • Bioinformatics: protein structure prediction and genome sequence clustering use VNS to search conformational or clustering spaces too large for exact methods.
  • Data clustering: VNS-based algorithms improve upon k-means by escaping the local optima that fixed-initialization clustering always falls into (see k-means).

The reason VNS generalizes so well is that its framework requires only two ingredients: a local search procedure and an ordered family of neighborhoods. Any domain that has both — and nearly every combinatorial domain does — can plug into VNS immediately.

Conclusion

Variable Neighborhood Search embodies a simple but deep idea: when you are stuck, the problem is not where you started — it is the lens through which you are looking. By systematically widening that lens, VNS converts the obstacle of local optimality into a navigational tool.

It does not solve NP-hard problems exactly, and it carries no polynomial-time certificate. But it does something arguably more useful for practice: it finds near-optimal solutions on real instances where exact methods are hopeless, faster than random restarts, and with a principled reason why it should work.

If you have ever felt trapped by the best move available to you, VNS has a prescription — look at the same problem from a larger neighborhood, and keep going until the landscape opens up. The connection to non-convex optimization runs deep: every technique for escaping local optima, from simulated annealing to gradient restarts, is wrestling with the same fundamental geometry that VNS addresses head-on.

Share this article

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

Comments

Loading comments...

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