large-neighborhood-search

Large Neighborhood Search

You are an expert in large neighborhood search (LNS) and its adaptive variant (ALNS) for combinatorial optimization. This skill covers destroy/repair operator design, adaptive operator weights with segment updates, acceptance criteria, degree-of-destruction control, and noise, with implementation-grade Python. LNS/ALNS is the modern workhorse for vehicle routing and scheduling; use the framework below to take a user from "local search is stuck and most moves are infeasible" to a calibrated, reproducible ALNS with a defensible operator and parameter story.

Initial Assessment

Establish these facts before writing any LNS code:

• Removable element. What is the atomic unit a destroy operator removes — a customer visit, a job, a shift assignment, an order line? Destroy and repair are defined over these elements; pick the granularity first.
• Constraint tightness. Are most small moves (swap, relocate) infeasible because of time windows, capacities, or precedences? Tight coupling is the signature case for LNS; loosely constrained problems are often served better by 2-opt-style local search or ILS.
• Construction heuristic availability. Any decent greedy or regret construction heuristic for the problem becomes a repair operator almost verbatim. If none exists, design it before the LNS loop.
• Repair completeness. Can repair always finish a solution (e.g., open a new vehicle, use overtime), or can it dead-end? If it can dead-end, plan a request bank or penalty scheme — see constraint-handling-techniques.
• Objective structure. Single objective, or hierarchical (first vehicles, then distance)? Scale and hierarchy interact with the acceptance temperature; decide how to compare two solutions before calibrating acceptance.
• Hard vs soft constraints. Which constraints stay satisfied by construction inside repair, and which become penalties in the objective? Penalty weights become parameters of the search.
• Instance size and per-iteration cost. With n elements and destruction degree q, greedy repair costs roughly O(q · positions). Measure iterations/second early; the budget in iterations drives the cooling schedule and segment count.
• Time budget and quality target. A 1-minute "good enough" run and a benchmark run chasing best-known solutions need different iteration counts, q ranges, and acceptance schedules.
• Plain LNS vs ALNS. One destroy + one repair operator (plain LNS) is the right first build. Add the adaptive layer only when you have at least 3 destroy and 2 repair operators worth arbitrating between.
• Exact repair option. Is a MIP solver licensed and fast enough to reinsert q elements optimally? If yes, the matheuristic variant is on the table — see matheuristics.
• Delta evaluation. Can insertion costs be computed incrementally per route/machine instead of re-evaluating the full solution? Repair dominates runtime; this decides whether the method is competitive.
• Baseline. What must ALNS beat — an ILS, OR-Tools, a MIP with time limit? Always run the baseline first; ALNS has more moving parts and needs justification.
• Reproducibility. Seeds per instance, instance set, and reporting format (best/mean/std, gap to best known) — fix these before tuning anything.