Variabel nabosøk (VNS)

Variabel nabosøk (VNS) er et metaheuristisk optimaliseringsrammeverk introdusert av Mladenović og Hansen i 1997. Det unnslipper lokale optima ved systematisk å bytte mellom et forhåndsdefinert sett av nabostrukturer — først ved å perturbere den nåværende løsningen (skaking) for å nå en annen region av søkerommet, deretter ved å anvende et lokalt søk innenfor den regionen, og til slutt ved å akseptere den nye løsningen kun hvis den forbedrer den gjeldende. Metoden er fleksibel nok til å håndtere kombinatoriske problemer (ruting, planlegging, grafproblemer) så vel som kontinuerlig optimalisering, noe som gjør den til en av de mest brukte nabobaserte metaheuristikkene innen operasjonsanalyse.