Variable Neighborhood Search (VNS)

Variable Neighborhood Search (VNS) è un framework di ottimizzazione meta-euristica introdotto da Mladenović e Hansen nel 1997. Sfugge ai punti di ottimo locale passando sistematicamente tra un insieme predefinito di strutture di vicinato — prima perturbando la soluzione corrente (shaking) per raggiungere una regione diversa dello spazio di ricerca, poi applicando una ricerca locale all'interno di quella regione, e infine accettando la nuova soluzione solo se migliora quella incumbent. Il metodo è sufficientemente flessibile da gestire problemi combinatori (routing, scheduling, problemi sui grafi) così come l'ottimizzazione continua, rendendolo una delle meta-euristiche basate sul vicinato più utilizzate nella ricerca operativa.