Large Neighborhood Search

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.

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">
  {{hint_customers}}
  {{hint_destroy}}
</div>
<canvas id="canvas" width="300" height="300"></canvas>
<div class="stats">
  <span>{{label_total_dist}} <b id="dist">—</b></span>
  <span>{{label_step}} <b id="step">0</b></span>
</div>
<div class="controls">
  <label>{{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">{{btn_step}}</button>
  <button id="btnMany" type="button">{{btn_many}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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.

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.

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.