Large Neighbourhood Search (LNS) is a metaheuristic that improves a feasible solution by repeatedly destroying a large portion of it and then repairing the destroyed portion using a local optimisation solver. Each cycle makes a large, structured move through the solution space rather than the single-variable swaps used in standard local search. The result is that LNS can escape local optima that single-variable methods cannot, because the repair solver finds arrangements reachable only by changing many variables simultaneously. The name is literal: the neighbourhood explored at each iteration is large enough to include solutions several variable-values away from the current one.
The situation: A logistics planner has a feasible route plan for 200 deliveries across 12 trucks. Standard local search tries swapping one delivery between two routes, but it quickly gets stuck: no single swap improves the plan further without violating a time window or capacity constraint.
Without LNS: Local search terminates at a local optimum. Any individual swap either violates a constraint or increases cost, so no improvement is found.
With LNS (destroy-repair): Destroy step: remove 40 deliveries (20%) from their assigned routes, leaving gaps. Repair step: run a small Mixed-Integer Programming (MIP) solver on just those 40 displaced deliveries to re-insert them optimally into the existing route structure. Because 40 deliveries form a tractable subproblem, the repair solver finds an arrangement that no single swap could reach. After 200 iterations of destroy-repair, the solution cost falls 10-15% below the local search result.
The key design choice: The destroy operator. A random destroy finds some improvements; a problem-aware destroy (remove deliveries on the most congested routes, or remove deliveries with tight time windows) finds far better repairs. This is why published LNS results vary so widely: the destroy operator is the engineering insight, not the repair.
The critical distinction: When evaluating a published LNS implementation, the first question to ask is: is the repair exact (MIP or Constraint Programming) or heuristic (priority rule, greedy)? Exact repair gives optimality guarantees within the repaired subproblem; heuristic repair is faster but weaker. A LNS paper that shows 5% improvements might be using heuristic repair and reaching a local optimum within each destroyed subproblem, while an alternative using exact repair solvers might achieve 12% improvements at the cost of compute time.
The metaheuristic role: LNS itself is often presented as a complete algorithm, but it is best understood as a wrapper around an exact repair solver. The quality of the solution depends on problem-specific destroy design (which part of the solution to remove?) and the capacity of the repair solver. Both matter more than the LNS iteration count.
The destroy operator determines solution quality — the repair is just an exact solver. Most published LNS results vary because the destroy strategy differs, not the repair.