Variable Neighborhood Search (VNS)

Variable Neighborhood Search (VNS) ist ein heuristisches Optimierungsframework, das 1997 von Mladenović und Hansen eingeführt wurde. Es entkommt lokalen Optima, indem es systematisch zwischen einer vordefinierten Menge von Nachbarschaftsstrukturen wechselt — zuerst wird die aktuelle Lösung gestört (Shaking), um eine andere Region des Suchraums zu erreichen, dann wird eine lokale Suche innerhalb dieser Region durchgeführt, und schließlich wird die neue Lösung nur akzeptiert, wenn sie die bisher beste verbessert. Die Methode ist flexibel genug, um kombinatorische Probleme (Routing, Scheduling, Graphenprobleme) sowie kontinuierliche Optimierung zu behandeln, was sie zu einer der am weitesten verbreiteten nachbarschaftsbasierten Metaheuristiken in der Operations Research macht.