Introduction

Imagine you are managing deliveries for a city. You have a route plan — trucks, customers, time windows — and it is not quite right. Some trucks are overloaded, some detours are ridiculous, and the total distance is higher than it should be. What do you do?

One answer is to restart from scratch. Another, far more effective answer is Large Neighborhood Search (LNS): rip out a significant chunk of the plan, solve that piece optimally, and slot the repaired section back in. If it is better, keep it. If not, try ripping a different chunk. Repeat.

Paul Shaw introduced LNS in 1998 as a way to tackle Vehicle Routing Problems (VRPs). The insight is beautiful: small local moves (swap two customers) get trapped in bad local optima, but large moves (remove 30% of all assignments) open up enough space for a strong sub-solver to find genuinely better structure. You are not searching blindly — you are destroying intelligently and rebuilding optimally.

LNS sits in the family of metaheuristics alongside simulated annealing and tabu search, but its destroy-and-repair rhythm lets it exploit powerful exact solvers (MIP, CP) on the sub-problems it creates.

Repair a Route

Below is a small vehicle-routing scenario: 8 customers spread across a grid, served by 3 trucks starting from a depot (center). The initial assignment is random and likely poor. Press Run one LNS step to destroy a random subset of assignments and greedily re-assign them to the nearest available truck. Press Run 20 steps to watch quality climb iteration by iteration.

<div class="hint">
  <b>8 customers</b> (colored dots) are served by <b>3 trucks</b> from the depot (center).
  Destroy some assignments and greedily repair them. Watch total distance drop.
</div>
<canvas id="canvas" width="300" height="300"></canvas>
<div class="stats">
  <span>Total distance: <b id="dist">—</b></span>
  <span>Step: <b id="step">0</b></span>
</div>
<div class="controls">
  <label>Destroy size: <b id="kval">3</b>
    <input type="range" id="kslider" min="1" max="6" value="3">
  </label>
</div>
<div class="btns">
  <button id="btnStep" type="button">Run one LNS step</button>
  <button id="btnMany" type="button">Run 20 steps</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .5rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 10px;
         background: #f5f8fb; margin-bottom: .5rem; max-width: 100%; }
.stats { font-size: .9rem; margin-bottom: .4rem; display: flex; gap: 1.2rem; }
.controls { font-size: .85rem; margin-bottom: .6rem; }
.controls input[type=range] { vertical-align: middle; margin-left: .4rem; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Large Neighborhood Search demo on a small VRP instance.
// 8 customers, 3 trucks, depot at center.
// Destroy: remove k customers at random from their trucks.
// Repair: greedily assign each removed customer to the nearest truck (by current last stop).
// Accept: if new total distance <= old, update solution.

const W = 300, H = 300;
const DEPOT = { x: 150, y: 150 };
const CUSTOMERS = [
  { x: 60,  y: 70  },
  { x: 100, y: 50  },
  { x: 230, y: 80  },
  { x: 260, y: 140 },
  { x: 220, y: 240 },
  { x: 130, y: 260 },
  { x: 60,  y: 210 },
  { x: 40,  y: 140 }
];
const TRUCK_COLORS = ['#e63946', '#2a9d8f', '#e9c46a'];
const N = CUSTOMERS.length;
const T = 3;

// State: assignment[i] = truck index for customer i
let assignment = [];
let stepCount = 0;

function dist(a, b) {
  return Math.hypot(a.x - b.x, a.y - b.y);
}

// Total route distance: depot -> customers in truck order -> depot
function routeDistance(asgn) {
  let total = 0;
  for (let t = 0; t < T; t++) {
    const stops = asgn.reduce((acc, tr, i) => { if (tr === t) acc.push(i); return acc; }, []);
    if (stops.length === 0) continue;
    let prev = DEPOT;
    for (const i of stops) { total += dist(prev, CUSTOMERS[i]); prev = CUSTOMERS[i]; }
    total += dist(prev, DEPOT);
  }
  return total;
}

function initAssignment() {
  // Random initial assignment, ensuring each truck gets at least 1 customer
  assignment = Array.from({ length: N }, (_, i) => i % T);
  // shuffle
  for (let i = N - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [assignment[i], assignment[j]] = [assignment[j], assignment[i]];
  }
  stepCount = 0;
}

function lnsStep(k) {
  // Destroy: pick k distinct customers at random
  const idx = Array.from({ length: N }, (_, i) => i);
  for (let i = N - 1; i > 0; i--) { const j = Math.floor(Math.random() * (i + 1)); [idx[i], idx[j]] = [idx[j], idx[i]]; }
  const removed = idx.slice(0, k);

  // Build tentative assignment without removed customers
  const newAsgn = assignment.slice();
  removed.forEach(i => { newAsgn[i] = -1; });

  // Greedy repair: for each removed customer, assign to truck with nearest last stop
  // Shuffle removed to avoid insertion-order bias
  for (let i = removed.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [removed[i], removed[j]] = [removed[j], removed[i]];
  }
  for (const ci of removed) {
    let bestTruck = 0, bestDist = Infinity;
    for (let t = 0; t < T; t++) {
      // Last stop in truck t under newAsgn
      const stops = newAsgn.reduce((acc, tr, i) => { if (tr === t) acc.push(i); return acc; }, []);
      const lastStop = stops.length > 0 ? CUSTOMERS[stops[stops.length - 1]] : DEPOT;
      const d = dist(lastStop, CUSTOMERS[ci]) + dist(CUSTOMERS[ci], DEPOT);
      if (d < bestDist) { bestDist = d; bestTruck = t; }
    }
    newAsgn[ci] = bestTruck;
  }

  // Accept if improvement (or accept degradation with small prob to escape traps)
  const oldDist = routeDistance(assignment);
  const newDist = routeDistance(newAsgn);
  if (newDist <= oldDist * 1.05) {
    assignment = newAsgn;
  }
  stepCount++;
}

function draw() {
  const canvas = document.getElementById('canvas');
  const ctx = canvas.getContext('2d');
  ctx.clearRect(0, 0, W, H);

  // Draw routes: for each truck, depot -> customers -> depot
  for (let t = 0; t < T; t++) {
    const stops = assignment.reduce((acc, tr, i) => { if (tr === t) acc.push(i); return acc; }, []);
    if (stops.length === 0) continue;
    ctx.beginPath();
    ctx.strokeStyle = TRUCK_COLORS[t];
    ctx.lineWidth = 1.5;
    ctx.setLineDash([4, 3]);
    ctx.moveTo(DEPOT.x, DEPOT.y);
    for (const i of stops) ctx.lineTo(CUSTOMERS[i].x, CUSTOMERS[i].y);
    ctx.lineTo(DEPOT.x, DEPOT.y);
    ctx.stroke();
    ctx.setLineDash([]);
  }

  // Draw depot
  ctx.beginPath();
  ctx.arc(DEPOT.x, DEPOT.y, 8, 0, 2 * Math.PI);
  ctx.fillStyle = '#1d3557';
  ctx.fill();
  ctx.fillStyle = '#fff';
  ctx.font = 'bold 9px system-ui';
  ctx.textAlign = 'center';
  ctx.textBaseline = 'middle';
  ctx.fillText('D', DEPOT.x, DEPOT.y);

  // Draw customers
  for (let i = 0; i < N; i++) {
    const c = CUSTOMERS[i];
    const t = assignment[i];
    ctx.beginPath();
    ctx.arc(c.x, c.y, 7, 0, 2 * Math.PI);
    ctx.fillStyle = TRUCK_COLORS[t] || '#999';
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 1.5;
    ctx.stroke();
    ctx.fillStyle = '#fff';
    ctx.font = 'bold 8px system-ui';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(i + 1, c.x, c.y);
  }

  // Update stats
  const d = routeDistance(assignment);
  document.getElementById('dist').textContent = fmt('%round% px', { round: Math.round(d) });
  document.getElementById('step').textContent = stepCount;
}

function getK() { return parseInt(document.getElementById('kslider').value, 10); }

document.getElementById('kslider').addEventListener('input', function() {
  document.getElementById('kval').textContent = this.value;
});
document.getElementById('btnStep').addEventListener('click', () => { lnsStep(getK()); draw(); });
document.getElementById('btnMany').addEventListener('click', () => { for (let i = 0; i < 20; i++) lnsStep(getK()); draw(); });
document.getElementById('btnReset').addEventListener('click', () => { initAssignment(); draw(); });

// Verify: routeDistance must return a finite positive number for a valid assignment
(function selfTest() {
  const testAsgn = [0, 0, 1, 1, 2, 2, 0, 1];
  const d = routeDistance(testAsgn);
  if (!isFinite(d) || d <= 0) throw new Error(fmt('routeDistance selftest failed: %d%', { d: d }));
  console.log('LNS selftest passed. Route distance for test assignment:', Math.round(d));
})();

initAssignment();
draw();
Result
Console

Notice how the total distance drops with each accepted repair. A single step sometimes makes things worse (the algorithm can accept mild degradations to escape traps), but the trend is always downward. The destroy size slider controls how many customers are removed per step — too small and you can't escape local optima; too large and the repair problem becomes as hard as the original.

The Real Complexity

Why does LNS matter? Because the problems it targets are genuinely hard.

  • Vehicle Routing is NP-hard. Even the simplest variant — minimize total distance, no time windows — contains the Traveling Salesman Problem as a special case. Exact algorithms run in exponential time on large instances.
  • Local search gets stuck. Classic neighborhood search swaps one or two customers at a time. The neighborhood is small, so the solver quickly finds a local optimum it cannot escape by tiny moves.
  • LNS opens a large neighborhood cheaply. Removing k customers creates a sub-problem with roughly k! ways to re-insert them. For k = 5 that is already 120 possibilities; for k = 30 it is astronomical. Yet the repair step — done with a greedy heuristic or a CP/MIP sub-solver — navigates this enormous space efficiently by exploiting structure.
  • No optimality guarantee. LNS is a heuristic: it cannot promise the optimal solution. But on real benchmarks (Solomon instances, CVRPLIB) it consistently finds solutions within 1–3% of the best known, far better than naive local search.
  • Adaptive LNS (ALNS) (Ropke & Pisinger, 2006) takes the idea further: maintain a portfolio of destroy operators and a portfolio of repair operators, score each by historical performance, and sample them with probability proportional to their score. The algorithm learns which combinations work best on the current instance.

The theoretical reason LNS works is that large neighborhoods expose global structure invisible to small-move searches. Destroying a region and repairing it lets the solver jump across many local-optima barriers at once.

Where It Matters

Large Neighborhood Search has moved from academic papers to production systems across many industries:

  • Last-mile logistics: platforms like UPS ORION, Amazon Route Optimization, and open-source tools (OR-Tools, OptaPlanner) use LNS-style destroy-and-repair at the core of their routing engines. Millions of deliveries are planned this way every day.
  • Hospital scheduling: operating-room assignments, nurse rosters, and patient transport are classic VRP variants. LNS finds feasible schedules fast enough to react to cancellations or emergencies in real time — a domain also studied in nurse rostering.
  • Supply-chain planning: warehouse pick-and-pack sequencing, inter-facility truck routing, and container loading all share the same destroy-and-repair structure.
  • Satellite mission planning: assigning observation windows to requests is an NP-hard assignment problem. Space agencies use LNS because exact solvers cannot handle instance sizes in the thousands of requests.
  • Research benchmark: the CVRPLIB library contains hundreds of standard instances. LNS-based solvers hold many of the best-known records, making it the de-facto proving ground for routing algorithms.

Understanding LNS connects directly to integer programming (the sub-solver used in ALNS repair), constraint programming, and the broader field of combinatorial optimization.

Conclusion

Large Neighborhood Search captures a profound engineering insight: when a problem is too big to solve globally, break it deliberately and fix the pieces. By destroying a large fraction of a solution and handing the gap to a strong sub-solver, LNS sidesteps the local-optima traps that doom naive search — and it does so without the exponential cost of exact methods.

Shaw's 1998 paper turned a simple observation into a scalable algorithm. Ropke and Pisinger's ALNS (2006) turned it into an adaptive framework that learns on the fly. Today, every major logistics platform owes something to this destroy-and-repair rhythm.

The next time a delivery app re-routes your driver mid-trip after a new order appears, there is a good chance a version of LNS just ran in the background — quietly ripping out a few stops, rebuilding them better, and handing back a plan before you even noticed.

Share this article

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

Comments

Loading comments...

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