Lokale Suche

Die lokale Suche ist die Familie der Verbesserungsheuristiken, die mit einer Anfangslösung beginnt und in jeder Iteration einen besseren Nachbarn innerhalb einer als Nachbarschaft definierten kleinen Änderungsmenge sucht. Systematische TSP-Studien beginnen mit Croes (1958) 2-opt und Lin (1965) 3-opt und erreichen ihren Höhepunkt mit dem variable-tiefen k-opt-Algorithmus von Lin und Kernighan (1973) — Lin-Kernighan und seine variable-tiefen Ableitungen (Helsgaun 2000) lieferten jahrzehntelang die beste empirische TSP-Leistung. Eine lokale Suche besteht aus einer Nachbarschaftsdefinition (z. B. Kantentausch im TSP, Auftragstausch im Scheduling, Relocate / Swap / 2-opt* im VRP), einer Bewertungsregel (first-improvement, best-improvement, least-worsening) und einem Abbruchkriterium. Lokale Suche konvergiert immer zu einem **lokalen Optimum** — einem in der Nachbarschaft nicht verbesserbaren Punkt — bietet aber keine globale Garantie. Zum Verlassen lokaler Optima wurden Metaheuristiken entwickelt: Tabu Search (Glover 1989), Simulated Annealing (Kirkpatrick 1983), VNS (Mladenović und Hansen 1997), Iterated Local Search (Lourenço, Martin und Stützle 2003). Lokale Suche bietet enorme Geschwindigkeit: auf einem 10.000-Städte-TSP landet ein Lin-Kernighan-abgeleiteter Lauf auf moderner Hardware in Sekunden 0,5% an der Exaktlösung. Aarts und Lenstra (1997) *Local Search in Combinatorial Optimization* ist die Referenz.