Variable Neighborhood Search

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.

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">{{hint}}</p>
<div class="layout">
  <canvas id="cvs" width="340" height="200"></canvas>
  <div class="panel" id="panel">
    <div class="row"><span class="label">{{lbl_algo}}</span><span id="algoName" class="val">—</span></div>
    <div class="row"><span class="label">{{lbl_nbhd}}</span><span id="nbhd" class="val">—</span></div>
    <div class="row"><span class="label">{{lbl_cur_x}}</span><span id="curX" class="val">—</span></div>
    <div class="row"><span class="label">{{lbl_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">{{btn_run_ls}}</button>
  <button id="btnVNS" type="button">{{btn_run_vns}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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 $N_{1}$ may be on a downhill slope under $N_{3}$. This is not magic — it is geometry of the search space made algorithmic.

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.

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.