Переменные окрестности (VNS)

Переменные окрестности (VNS) — это метаэвристическая оптимизационная структура, представленная Младенович и Хансен в 1997 году. Она позволяет избежать локальных оптимумов путем систематического переключения между предопределенным набором структур окрестностей — сначала возмущая текущее решение (встряхивание) для достижения другой области пространства поиска, затем применяя локальный поиск в этой области и, наконец, принимая новое решение только в том случае, если оно улучшает текущее. Метод достаточно гибок для решения комбинаторных задач (маршрутизация, планирование, графовые задачи), а также задач непрерывной оптимизации, что делает его одной из наиболее широко используемых метаэвристик, основанных на окрестностях, в исследовании операций.