Cerca de Veïnatge Variable (VNS)

Variable Neighborhood Search (VNS) és un marc d'optimització metaheurístic introduït per Mladenović i Hansen el 1997. Escapa dels òptims locals canviant sistemàticament entre un conjunt predefinit d'estructures de veïnatge — primer pertorbant la solució actual (sacsejant) per arribar a una regió diferent de l'espai de cerca, després aplicant una cerca local dins d'aquella regió, i finalment acceptant la nova solució només si millora la incumbent. El mètode és prou flexible per gestionar problemes combinatoris (de ruta, de planificació, de grafs) així com optimització contínua, convertint-lo en una de les metaheurístiques basades en veïnatge més utilitzades en recerca operativa.