Пошук зі змінними сусідствами (Variable Neighborhood Search, VNS)

Пошук зі змінними сусідствами (VNS) — це метаевристична система оптимізації, представлена Младеновичем та Гансеном у 1997 році. Вона дозволяє уникнути локальних оптимумів шляхом систематичного перемикання між заздалегідь визначеним набором структур сусідства: спочатку збурюючи поточне рішення (струшування) для досягнення іншої області простору пошуку, потім застосовуючи локальний пошук у цій області, і, нарешті, приймаючи нове рішення лише в тому випадку, якщо воно покращує поточне. Цей метод є достатньо гнучким для розв'язання комбінаторних задач (маршрутизація, планування, задачі на графах), а також задач неперервної оптимізації, що робить його одним із найпоширеніших метаевристик на основі сусідства в дослідженні операцій.