Local Search

Local search is the family of improvement heuristics that starts from an initial solution and at each iteration looks for a better neighbor within a small set of changes called the neighborhood. Systematic studies on TSP began with Croes (1958) 2-opt and Lin (1965) 3-opt, peaking with the variable-depth k-opt algorithm of Lin and Kernighan (1973) — Lin-Kernighan and its variable-depth derivatives (Helsgaun 2000) have for decades provided the best empirical performance on TSP. A local search consists of a neighborhood definition (e.g. swap two edges in TSP, swap two jobs in scheduling, relocate / swap / 2-opt* in VRP), a move-evaluation rule (first-improvement, best-improvement, least-worsening), and a stopping criterion. Local search always converges to a **local optimum** — a point that cannot be improved within the neighborhood — but offers no global guarantee. To escape local optima, metaheuristics were developed: tabu search (Glover 1989), simulated annealing (Kirkpatrick 1983), VNS (Mladenović and Hansen 1997), iterated local search (Lourenço, Martin and Stützle 2003). Local search delivers a massive speed advantage: on a 10,000-city TSP a Lin-Kernighan-derived run lands within 0.5% of the exact solution in seconds on modern hardware. Aarts and Lenstra (1997) *Local Search in Combinatorial Optimization* is the reference volume.