Ricerca Locale

La ricerca locale è la famiglia di euristiche di miglioramento che parte da una soluzione iniziale e a ogni iterazione cerca un vicino migliore entro un piccolo insieme di modifiche detto vicinato. Gli studi sistematici sul TSP iniziano con 2-opt di Croes (1958) e 3-opt di Lin (1965), culminando con l'algoritmo k-opt a profondità variabile di Lin e Kernighan (1973) — Lin-Kernighan e i suoi derivati a profondità variabile (Helsgaun 2000) hanno fornito per decenni la migliore performance empirica sul TSP. Una ricerca locale consiste in una definizione di vicinato (es. scambio di due archi nel TSP, scambio di due lavori nello scheduling, relocate / swap / 2-opt* nel VRP), una regola di valutazione (primo miglioramento, miglior miglioramento, minimo peggioramento) e un criterio di arresto. La ricerca locale converge sempre a un **ottimo locale** — un punto non migliorabile nel vicinato — ma non offre garanzia globale. Per sfuggire agli ottimi locali si sono sviluppate metaeuristiche: tabu search (Glover 1989), simulated annealing (Kirkpatrick 1983), VNS (Mladenović e Hansen 1997), iterated local search (Lourenço, Martin e Stützle 2003). La ricerca locale offre un enorme vantaggio in velocità: su un TSP da 10.000 città un'esecuzione derivata da Lin-Kernighan cade allo 0,5% della soluzione esatta in pochi secondi su hardware moderno. Aarts e Lenstra (1997) *Local Search in Combinatorial Optimization* è il volume di riferimento.