Variable Neighborhood Search (VNS)

to szkielet optymalizacyjny typu metaheurystycznego, wprowadzony przez Mladenovića i Hansena w 1997 roku. Ucieka on od lokalnych minimów poprzez systematyczne przełączanie między predefiniowanym zbiorem struktur sąsiedztwa — najpierw zaburzając bieżące rozwiązanie (wstrząs), aby dotrzeć do innego regionu przestrzeni poszukiwań, następnie stosując lokalne przeszukiwanie w tym regionie, i wreszcie akceptując nowe rozwiązanie tylko wtedy, gdy poprawia ono rozwiązanie najlepsze dotychczasowe. Metoda jest na tyle elastyczna, że może obsługiwać problemy kombinatoryczne (problemy trasowania, harmonogramowania, grafowe), jak i optymalizację ciągłą, co czyni ją jedną z najczęściej stosowanych metaheurystyk opartych na sąsiedztwie w badaniach operacyjnych.