Búsqueda Local

La búsqueda local es la familia de heurísticas de mejora que parte de una solución inicial y en cada iteración busca un mejor vecino dentro de un pequeño conjunto de cambios denominado vecindad. Los estudios sistemáticos sobre TSP comenzaron con 2-opt de Croes (1958) y 3-opt de Lin (1965), culminando con el algoritmo k-opt de profundidad variable de Lin y Kernighan (1973) — Lin-Kernighan y sus derivados de profundidad variable (Helsgaun 2000) ofrecieron durante décadas el mejor rendimiento empírico en TSP. Una búsqueda local consta de una definición de vecindad (p. ej. intercambio de dos aristas en TSP, intercambio de dos trabajos en scheduling, relocate / swap / 2-opt* en VRP), una regla de evaluación (primera mejora, mejor mejora, menor empeoramiento) y un criterio de parada. La búsqueda local siempre converge a un **óptimo local** — un punto no mejorable dentro de la vecindad — pero no ofrece garantía global. Para escapar de óptimos locales se desarrollaron metaheurísticas: tabu search (Glover 1989), recocido simulado (Kirkpatrick 1983), VNS (Mladenović y Hansen 1997), búsqueda local iterada (Lourenço, Martin y Stützle 2003). La búsqueda local aporta una enorme ventaja de velocidad: en un TSP de 10.000 ciudades una corrida derivada de Lin-Kernighan cae al 0,5% de la solución exacta en segundos sobre hardware moderno. Aarts y Lenstra (1997) *Local Search in Combinatorial Optimization* es el volumen de referencia.