Переменный поиск соседей

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

Введение

VNS систематически меняет окрестность в две фазы: во-первых, спуск для поиска локального оптимума и, наконец, фазу возмущения для выхода из соответствующей долины.

Число приложений быстро увеличивается, и они относятся ко многим областям: теория местоположения , кластерный анализ , планирование , маршрутизация транспортных средств , проектирование сетей , определение размеров партий, искусственный интеллект , инженерия, проблемы объединения, биология, филогения , надежность , геометрия, проектирование телекоммуникаций и т. д. .

Есть несколько книг, важных для понимания VNS, например: Handbook of Metaheuristics , 2010, ^[3] Справочник по метаэвристике, 2003 г. ^[4] и Методологии поиска, 2005 г. ^[5]Более ранние работы, мотивирующие этот подход, можно найти в

Дэвид, туалет ^[6]
Флетчер, Р., Пауэлл, MJD ^[7]
Младенович, Н. ^[8] и
Бримберг Дж., Младенович Н. ^[9]

Недавние обзоры методологии VNS, а также многочисленных приложений можно найти в 4OR, 2008 г. ^[10] и Анналы ОР, 2010.

Определение проблемы

Определите одну детерминированную задачу оптимизации с

$\min {\{f(x)|x\in X,X\subseteq S\}}$ , (1)

где S , X , x и f — пространство решений, допустимый набор, допустимое решение и вещественная целевая функция соответственно. Если S — конечное, но большое множество, определяется задача комбинаторной оптимизации. Если ${S=R^{n}}$ , существует модель непрерывной оптимизации.

Решение ${x^{*}\in X}$ оптимально, если

${f(x^{*})\leq f(x),\qquad \forall {x}\,\in X}$ .

Точный алгоритм решения задачи (1) состоит в том, чтобы найти оптимальное решение x* с обоснованием его оптимальной структуры, или, если оно нереализуемо, в процедуре должно быть показано отсутствие достижимого решения, т. е. $X=\varnothing$ , или решение неограничено. Время процессора должно быть конечным и коротким. Для непрерывной оптимизации разумно допускать некоторую степень допуска, т. е. останавливаться, когда появляется допустимое решение. $x^{*}$ было найдено такое, что

${f(x^{*})\leq f(x)+\epsilon ,\qquad \forall {x}\,\in X}$ или ${(f(x^{*})-f(x))/f(x^{*})<\epsilon ,\qquad \forall {x}\,\in X}$

Некоторые эвристики быстро принимают приближенное решение или оптимальное решение, но без проверки его оптимальности.Некоторые из них имеют неверный сертификат, т.е. решение $x_{h}$ полученное удовлетворяет

${(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}$ для некоторых $\epsilon$ , хотя это редко бывает небольшим.

Эвристики сталкиваются с проблемой локального оптимума из-за того, что им удается избежать безграничного вычислительного времени.Локальный оптимум $x_{L}$ проблема такова, что

${f(x_{L})\leq f(x),\qquad \forall {x}\,\in N(x_{L})\cap X}$

где $N(x_{L})$ обозначает окрестность $x_{L}$

Описание

Согласно (Младенович, 1995), VNS представляет собой метаэвристику, которая систематически выполняет процедуру изменения окрестности, как при спуске к локальным минимумам, так и при выходе из долин, которые их содержат.

VNS построен на следующих представлениях:

Локальный минимум по отношению к одной структуре окрестности не обязательно является локальным минимумом для другой структуры окрестности.
Глобальный минимум — это локальный минимум по отношению ко всем возможным структурам окрестности.
Для многих задач локальные минимумы по отношению к одной или нескольким окрестностям относительно близки друг к другу.

В отличие от многих других метаэвристик, базовые схемы VNS и ее расширений просты и требуют небольшого количества, а иногда и вообще никаких параметров. Таким образом, помимо предоставления очень хороших решений, часто более простыми способами, чем другие методы, VNS дает представление о причинах такой производительности, что, в свою очередь, может привести к более эффективным и сложным реализациям.

Среди недавно упомянутых работ есть несколько работ, в которых его можно было бы изучить, например (Hansen and Mladenović 1999, 2001a, 2003, 2005; Moreno-Pérez et al.; ^[11])

Локальный поиск

Эвристика локального поиска выполняется путем выбора начального решения x, обнаружения направления спуска от x в окрестности N(x) и перехода к минимуму f(x) внутри N(x) в том же направлении. Если направления спуска нет, эвристика прекращается; в противном случае он повторяется. Обычно используется самое высокое направление спуска, также называемое лучшим улучшением. Этот набор правил обобщен в алгоритме 1, где мы предполагаем, что начальное решение x задано . Выходные данные состоят из локального минимума, обозначаемого x' , и его значения. Заметим, что структура окрестности N(x) определена для всех x ∈ X. На каждом шаге окрестность N(x) точки x исследуется полностью. Поскольку это может занять много времени, альтернативой является использование эвристики первого спуска. Векторы $x^{i}\in N(x)$ затем систематически пересчитываются, и движение производится, как только будет найдено направление спуска. Это суммировано в алгоритме 2.

Алгоритм 1: Эвристика наилучшего улучшения (наивысшего спуска)

Функция BestImprovement(x)  1: повторить  2: х' ← х  3: x ← argmin_{ f(y) }, y ∈ N(x)  4: до тех пор, пока ( f(x) ≥ f(x'))  5: вернуть х'

Алгоритм 2: Эвристика первого улучшения (первого спуска)

Функция FirstImprovement(x)  1: повторить  2: х' ← х; я ← 0  3: повторить  4: я ← я + 1  5: x ← argmin{ f(x), f(x^i)}, x^i ∈ N(x)  6: до тех пор, пока ( f(x) < f(x^i) или i = |N(x)|)  7: до тех пор, пока ( f(x) ≥ f(x'))  8: вернуть х'

Пусть обозначается ${\mathcal {N}}_{k}(k=1,...,k_{max})$ , конечный набор заранее выбранных структур окрестности, и с ${\mathcal {N}}_{k}(x)$ множество решений в k-й окрестности точки x .

Также будет использоваться обозначение ${\mathcal {N'}}_{k}(x),k=1,...,k'_{max}$ при описании местного происхождения. Районы ${\mathcal {N}}_{k}(x)$ или ${\mathcal {N'}}_{k}(x)$ может быть индуцировано одной или несколькими метрическими (или квазиметрическими) функциями, введенными в пространство решений S .Оптимальное решение $x_{opt}$ (или глобальный минимум ) — это допустимое решение, при котором достигается минимум проблемы. Мы называем x' ∈ X локальным минимумом задачи относительно ${\mathcal {N}}_{k}(x)$ , если нет решения $x\in {\mathcal {N'}}_{k}(x)\subseteq X$ такой, что $f(x)<f(x')$ .

Чтобы решить проблему с использованием нескольких окрестностей, факты 1–3 можно использовать тремя разными способами: (i) детерминистически; (ii) стохастический ; (iii) как детерминированные, так и стохастические. Сначала мы даем в алгоритме 3 шаги функции изменения окрестности, которые будут использоваться позже. Функция NeighborhoodChange() сравнивает новое значение f(x') с действующим значением f(x), полученным в окрестности k (строка 1). Если улучшение получено, k возвращается к исходному значению, а новый действующий оператор обновляется (строка 2). В противном случае рассматривается следующая окрестность (строка 3).

Алгоритм 3: – Смена соседства

Функция NeighborhoodChange (x, x', k) 1: если f (x') < f(x), то 2: x ← x' // Делаем ход 3: k ← 1 // Начальная окрестность 4: еще 5: k ← k+1 // Следующая окрестность

Если VNS не дает хорошего решения, можно предпринять несколько шагов, таких как сравнение первых и лучших стратегий улучшения локального поиска, уменьшение соседства, усиление тряски, принятие VND, принятие FSS и экспериментирование с настройками параметров.

Метод Базовой ВНС (БВНС) ( Справочник по метаэвристике , 2010) ^[3] сочетает в себе детерминированные и стохастические изменения окрестности. Его шаги приведены в алгоритме 4. Часто последовательные окрестности ${\mathcal {N}}_{k}$ будет вложенным. Обратите внимание, что точка x' генерируется случайным образом на шаге 4, чтобы избежать цикличности, которая могла бы произойти, если бы применялось детерминированное правило. На шаге 5 лучшим улучшением локального поиска (алгоритм 1) обычно являетсяусыновленный. Однако его можно заменить первым улучшением (алгоритм 2).

Алгоритм 4: Базовый VNS

Функция ВНС (x, kmax, tmax) 1: повторить 2: к ← 1 3: повторить 4: x' ← Shake(x, k) // Встряхивание 5: x'' ← BestImprovement(x' ) // Локальный поиск 6: x ← NeighbourhoodChange(x, x'', k) // Изменить соседство 7: до тех пор, пока k = kmax 8: t ← CpuTime() 9: до тех пор, пока t > tmax

Варианты ВНС

Базовый VNS — это лучший метод спуска улучшений с рандомизацией. ^[3] Без особых дополнительных усилий его можно преобразовать в метод спуска-восхождения: в функции NeighbourhoodChange() замените также x на x" с некоторой вероятностью, даже если решение хуже действующего. Его также можно превратить в первое метод улучшения.Другим вариантом базовой VNS может быть поиск решения x' на шаге «Встряхивание» как лучшего среди b (параметр) случайно сгенерированных решений из k -й окрестности. Возможны два варианта этого расширения: (1) выполнять только один локальный поиск из лучшей среди b точек; (2) выполнить все b локальных поисков и затем выбрать лучший. В статье (Флессар и хинди ^[12]) можно найти алгоритм.

Расширения

донг ^[13]

Метод переменного спуска окрестностей (VND) получается, если смена окрестностей выполняется детерминированным способом. В описаниях его алгоритмов мы предполагаем, что начальное решение x задано . Большинство эвристик локального поиска на этапе спуска используют очень мало окрестностей. Окончательное решение должно быть локальным минимумом по отношению ко всем

k_{max}

кварталы; следовательно, шансы на достижение глобального уровня выше при использовании VND, чем при использовании структуры с одним соседством.

РВНС ^[14]

Метод приведенной ВНС (РВНС) получается, если случайные точки выбираются из

{\mathcal {N}}_{k}(x)

и никакого спуска не происходит. Скорее, значения этих новых баллов сравниваются со значениями действующего игрока, и в случае улучшения происходит обновление. Предполагается, что условие остановки было выбрано как максимально время процессора . допустимое

t_{max}

или максимальное количество итераций между двумя улучшениями.

Для упрощения описания алгоритмов используется

t_{max}

ниже. Поэтому RVNS использует два параметра:

t_{max}

и

k_{max}

. RVNS полезен в очень больших случаях, когда локальный поиск является дорогостоящим. Было замечено, что наилучшее значение параметра

k_{max}

часто равно 2. Кроме того, максимальное количество итераций между двумя улучшениями обычно используется в качестве условия остановки. RVNS похож на метод Монте-Карло , но является более систематическим.

Искаженный VNS

Метод перекошенной VNS (SVNS) (Хансен и др.) ^[15] решает проблему исследования долин, далекую от существующего решения. Действительно, как только лучшее решение в большом регионе найдено, необходимо приложить определенные усилия, чтобы получить улучшенное решение. Решения, выбранные случайным образом в отдаленных окрестностях, могут существенно отличаться от действующего, и тогда VNS может в некоторой степени переродиться в эвристику Multistart (в которой спуск осуществляется итеративно из решений, сгенерированных случайным образом, эвристика, которая, как известно, не очень эффективна). ). Следовательно, необходимо сделать некоторую компенсацию за расстояние от действующего президента.

Поиск разложения окрестности переменной

Метод поиска разложения окрестности переменной (VNDS) (Хансен и др.) ^[16] расширяет базовую VNS до двухуровневой схемы VNS, основанной на декомпозиции задачи. Для простоты изложения, но без потери общности, предполагается, что решение x представляет собой множество некоторых элементов.

Параллельная VNS

Недавно было предложено несколько способов распараллеливания VNS для решения проблемы p-медианы. Гарсиа-Лопес и др. ^[17] три из них протестированы: (i) распараллелить локальный поиск; (ii) увеличить количество решений, взятых из текущей окрестности, и выполнить локальный поиск параллельно для каждого из них, и (iii) сделать то же самое, что и (ii), но обновить информацию о найденном наилучшем решении. Три параллельные стратегии VNS также предлагаются для решения проблемы путешествующего покупателя в Ochi et al. ^[18]

Первично-двойной ВНС

Для большинства современных эвристик разница в ценности оптимального решения и полученного совершенно неизвестна. Гарантированную эффективность основной эвристики можно определить, если нижняя граница известна значения целевой функции. С этой целью стандартный подход заключается в ослаблении условия целостности основных переменных на основе формулировки проблемы с помощью математического программирования.

Однако, когда размерность проблемы велика, даже расслабленную задачу невозможно решить точно с помощью стандартных коммерческих решателей. Таким образом, представляется хорошей идеей также эвристически решать задачи двойной релаксации. Были получены гарантированные границы производительности первичной эвристики. При первично-двойственной ВНС (ПД-ВНС) (Хансен и др.) ^[19] Предлагается один из возможных общих способов достижения как гарантированных оценок, так и точного решения.

Ветвление переменного окружения ^[20]

Задача смешанного целочисленного линейного программирования (MILP) состоит из максимизации или минимизации линейной функции с учетом ограничений равенства или неравенства, а также ограничений целочисленности некоторых переменных.

Поиск в пространстве формулировки переменной окрестности ^[21]

FSS — это метод, который очень полезен, поскольку одна проблема может быть определена дополнительно к формулировкам, и перемещение по формулировкам является законным. Доказано, что локальный поиск работает внутри формулировок, подразумевая окончательное решение, если начать с некоторого начального решения в первой формулировке. Локальный поиск систематически чередует различные формулировки, что исследовалось для задачи упаковки кругов (CPP), где стационарная точка для нелинейного программирования формулировки CPP в декартовых координатах не является строго стационарной точкой в полярных координатах .

Приложения

Применения VNS или разновидностей VNS очень многочисленны. Некоторые области, где можно найти сборники научных работ:

Промышленное применение
Проблемы дизайна в общении
Проблемы с местоположением
Интеллектуальный анализ данных
Проблемы с графиком
Проблемы с рюкзаком и упаковкой
Смешанные целочисленные задачи
Таблица времени
Планирование
Проблемы с маршрутизацией транспортных средств
Прокладка дуги и сбор отходов
Проблемы с листами флота
Проблемы с расширенной маршрутизацией транспортных средств
Проблемы по биологическим наукам и химии
Непрерывная оптимизация
Другие проблемы оптимизации
Открытие науки

Заключение

VNS подразумевает несколько особенностей, представленных Хансеном и Младеновичем. ^[22] и некоторые из них представлены здесь:

Простота: система VNS проста, понятна и универсальна.
Точность: VNS сформулирован в точных математических определениях.
Связность: все действия эвристик по решению задач вытекают из принципов ВНС.
Эффективность: VNS предоставляет оптимальные или почти оптимальные решения для всех или, по крайней мере, наиболее реалистичных случаев.
Эффективность: VNS требует умеренного вычислительного времени для создания оптимальных или почти оптимальных решений.
Надежность: функционирование VNS согласовано в различных случаях.
Удобство для пользователя: VNS не имеет параметров, поэтому его легко понять, выразить и использовать.
Инновации: VNS создает новые типы приложений.
Общность: VNS дает хорошие результаты при широком спектре проблем.
Интерактивность: VNS позволяет пользователю использовать свои знания для улучшения процесса разрешения.
Множественность: VNS способна создавать определенные, близкие к оптимальным решения, из которых пользователь может выбирать;

Интерес к ВНС быстро растет, о чем свидетельствует рост ежегодного количества статей, публикуемых по этой теме (10 лет назад — всего несколько, 5 лет назад — около десятка и около 50 в 2007 г.).Более того, 18-я мини-конференция ЕВРО, состоявшаяся на Тенерифе в ноябре 2005 года, была полностью посвящена ВНС. Это привело к появлению специальных выпусков журнала IMA Journal of Management Mathematics в 2007 году, Европейского журнала операционных исследований ( http://www.journals.elsevier.com/european-journal-of-operational-research/ ) и журнала эвристики ( https). ://www.springer.com/mathematics/applications/journal/10732/ ) в 2008 году.

Ссылки

^ Хансен, П.; Младенович, Н.; Перес, ДЖЕМ (2010). «Поиск переменной окрестности: методы и приложения». Анналы исследования операций . 175 : 367–407. дои : 10.1007/s10479-009-0657-6 . S2CID 26469746 .
^ Ненад Младенович; Пьер Хансен (1997). «Поиск переменного соседства». Компьютеры и исследования операций . 24 (11): 1097–1100. CiteSeerX 10.1.1.800.1797 . дои : 10.1016/s0305-0548(97)00031-2 .
^ Перейти обратно: ^а ^б ^с Жандро, М.; Потвин, Дж.Ю. (2010). «Справочник по метаэвристике». Спрингер.
^ Гловер, Ф.; Кохенбергер, Джорджия (2003). «Справочник по метаэвристике». Академическое издательство Клювер.
^ Берк, EK.; Кендалл, Г. (2005). Берк, Эдмунд К; Кендалл, Грэм (ред.). Методики поиска. Вводные уроки по методам оптимизации и поддержки принятия решений . Спрингер. дои : 10.1007/978-1-4614-6940-7 . ISBN 978-1-4614-6939-1 .
^ Дэвидон, WC (1959). «Алгоритм переменной метрики для минимизации». Отчет Аргоннской национальной лаборатории ANL-5990 .
^ Флетчер, Р.; Пауэлл, MJD (1963). «Метод быстро сходящегося спуска для минимизации» . Вычислить. Дж . 6 (2): 163–168. дои : 10.1093/comjnl/6.2.163 .
^ Младенович, Н. (1995). «Алгоритм переменной окрестности - новая метаэвристика для комбинаторной оптимизации». Тезисы докладов, представленных на Днях оптимизации, Монреаль : 112.
^ Бримберг, Дж.; Младенович, Н. (1996). «Алгоритм переменной окрестности для решения непрерывной задачи местоположения-распределения». Стад. Найдите. Анал . 10 : 1–12.
^ Хансен, П.; Младенович, Н.; Перес, ДЖЕМ (2008). «Поиск переменной окрестности: методы и приложения». 4ИЛИ . 6 (4): 319–360. дои : 10.1007/s10288-008-0089-1 . S2CID 538959 .
^ Морено-Перес, Жако; Хансен, П.; Младенович, Н. (2005). «Параллельный поиск окрестности переменных». В Альбе, Э (ред.). Параллельная метаэвристика: новый класс алгоритмов . стр. 247–266. CiteSeerX 10.1.1.615.2796 . дои : 10.1002/0471739383.ch11 . ISBN 9780471739388 .
^ Флессар, К; Хинди, Канзас (2004). «Решение задачи планирования проекта с ограниченными ресурсами с помощью поиска переменных окрестностей». Eur J Oper Res . 155 (2): 402–413. дои : 10.1016/s0377-2217(02)00884-6 .
^ Бримберг, Дж.; Хансен, П.; Младенович, Н.; Тайлард, Э. (2000). «Усовершенствования и сравнение эвристик для решения задачи Вебера с несколькими источниками» . Опер. Рез . 48 (3): 444–460. дои : 10.1287/opre.48.3.444.12431 .
^ Младенович, Н.; Петрович, Дж.; Ковачевич-Вуйчич, В.; Кангалович, М. (2003b). «Решение проблемы разработки многофазного кода радиолокационной станции с расширенным спектром с помощью поиска с запретами и поиска переменных окрестностей». Евро. Дж. Опер. Рез . 151 (2): 389–399. дои : 10.1016/s0377-2217(02)00833-0 .
^ Хансен, П.; Жомар, Б ; Младенович, Н; Паррейра, А. (2000). «Поиск переменной окрестности для задачи взвешенной максимальной выполнимости». Les Cahiers du GERAD G–2000–62, HEC Montréal, Канада .
^ Хансен, П; Младенович, Н; Перес-Брито, Д (2001). «Поиск разложения окрестности переменной». J Эвристика . 7 (4): 335–350. дои : 10.1023/А:1011336210885 . S2CID 31111583 .
^ Гарсиа-Лопес, форвард; Мелиан-Батиста, Б; Морено-Перес, Дж. А. (2002). «Параллельный поиск окрестности переменной для задачи p-медианы» J Эвристика . 8 (3): 375–388. дои : 10.1023/A:1015013919497 . S2CID 16096161 .
^ Очи, Л.С.; Сильва, МБ; Драммонд, Л. (2001). «Метаэвристика на основе GRASP и VNS для решения задачи путешествующего покупателя» . MIC'2001, Порту : 489–494.
^ Хансен, П; Бримберг, Дж; Урошевич, Д; Младенович, Н. (2007a). «Поиск окрестностей первично-двойственной переменной для простой задачи размещения объекта» . Информирует J Comput . 19 (4): 552–564. дои : 10.1287/ijoc.1060.0196 .
^ Хансен, П.; Младенович, Н.; Уросевич, Д. (2006). «Поиск переменных окрестностей и локальное ветвление». Компьютеры и исследования операций . 33 (10): 3034–3045. CiteSeerX 10.1.1.108.987 . дои : 10.1016/j.cor.2005.02.033 .
^ Младенович, Н.; Пластрия, Ф .; Уросевич, Д. (2006). «Реформулирующий спуск применительно к задачам упаковки кругов». Компьютеры и исследования операций . 32 (9): 2419–2434. дои : 10.1016/j.cor.2004.03.010 .
^ Хансен, П; Младенович, Н (2003). «Поиск переменного соседства». В Гловере Ф; Кохенбергер Г. (ред.). Справочник по метаэвристике . Международная серия по исследованию операций и науке управления. Том. 57. Дордрехт: Клювер. стр. 145–184. CiteSeerX 10.1.1.635.7056 . дои : 10.1007/0-306-48056-5_6 . ISBN 978-1-4020-7263-5 .

Внешние ссылки

[1] Хансен, П.; Младенович, Н.; Перес, ДЖЕМ (2010). «Поиск переменной окрестности: методы и приложения». Анналы исследования операций . 175 : 367–407. дои : 10.1007/s10479-009-0657-6 . S2CID 26469746 .

[.....-2] Ненад Младенович; Пьер Хансен (1997). «Поиск переменного соседства». Компьютеры и исследования операций . 24 (11): 1097–1100. CiteSeerX 10.1.1.800.1797 . дои : 10.1016/s0305-0548(97)00031-2 .

[HoM2010-3] Перейти обратно: ^а ^б ^с Жандро, М.; Потвин, Дж.Ю. (2010). «Справочник по метаэвристике». Спрингер.

[4] Гловер, Ф.; Кохенбергер, Джорджия (2003). «Справочник по метаэвристике». Академическое издательство Клювер.

[5] Берк, EK.; Кендалл, Г. (2005). Берк, Эдмунд К; Кендалл, Грэм (ред.). Методики поиска. Вводные уроки по методам оптимизации и поддержки принятия решений . Спрингер. дои : 10.1007/978-1-4614-6940-7 . ISBN 978-1-4614-6939-1 .

[6] Дэвидон, WC (1959). «Алгоритм переменной метрики для минимизации». Отчет Аргоннской национальной лаборатории ANL-5990 .

[7] Флетчер, Р.; Пауэлл, MJD (1963). «Метод быстро сходящегося спуска для минимизации» . Вычислить. Дж . 6 (2): 163–168. дои : 10.1093/comjnl/6.2.163 .

[8] Младенович, Н. (1995). «Алгоритм переменной окрестности - новая метаэвристика для комбинаторной оптимизации». Тезисы докладов, представленных на Днях оптимизации, Монреаль : 112.

[9] Бримберг, Дж.; Младенович, Н. (1996). «Алгоритм переменной окрестности для решения непрерывной задачи местоположения-распределения». Стад. Найдите. Анал . 10 : 1–12.

[10] Хансен, П.; Младенович, Н.; Перес, ДЖЕМ (2008). «Поиск переменной окрестности: методы и приложения». 4ИЛИ . 6 (4): 319–360. дои : 10.1007/s10288-008-0089-1 . S2CID 538959 .

[11] Морено-Перес, Жако; Хансен, П.; Младенович, Н. (2005). «Параллельный поиск окрестности переменных». В Альбе, Э (ред.). Параллельная метаэвристика: новый класс алгоритмов . стр. 247–266. CiteSeerX 10.1.1.615.2796 . дои : 10.1002/0471739383.ch11 . ISBN 9780471739388 .

[12] Флессар, К; Хинди, Канзас (2004). «Решение задачи планирования проекта с ограниченными ресурсами с помощью поиска переменных окрестностей». Eur J Oper Res . 155 (2): 402–413. дои : 10.1016/s0377-2217(02)00884-6 .

[13] Бримберг, Дж.; Хансен, П.; Младенович, Н.; Тайлард, Э. (2000). «Усовершенствования и сравнение эвристик для решения задачи Вебера с несколькими источниками» . Опер. Рез . 48 (3): 444–460. дои : 10.1287/opre.48.3.444.12431 .

[14] Младенович, Н.; Петрович, Дж.; Ковачевич-Вуйчич, В.; Кангалович, М. (2003b). «Решение проблемы разработки многофазного кода радиолокационной станции с расширенным спектром с помощью поиска с запретами и поиска переменных окрестностей». Евро. Дж. Опер. Рез . 151 (2): 389–399. дои : 10.1016/s0377-2217(02)00833-0 .

[15] Хансен, П.; Жомар, Б ; Младенович, Н; Паррейра, А. (2000). «Поиск переменной окрестности для задачи взвешенной максимальной выполнимости». Les Cahiers du GERAD G–2000–62, HEC Montréal, Канада .

[16] Хансен, П; Младенович, Н; Перес-Брито, Д (2001). «Поиск разложения окрестности переменной». J Эвристика . 7 (4): 335–350. дои : 10.1023/А:1011336210885 . S2CID 31111583 .

[17] Гарсиа-Лопес, форвард; Мелиан-Батиста, Б; Морено-Перес, Дж. А. (2002). «Параллельный поиск окрестности переменной для задачи p-медианы» J Эвристика . 8 (3): 375–388. дои : 10.1023/A:1015013919497 . S2CID 16096161 .

[18] Очи, Л.С.; Сильва, МБ; Драммонд, Л. (2001). «Метаэвристика на основе GRASP и VNS для решения задачи путешествующего покупателя» . MIC'2001, Порту : 489–494.

[19] Хансен, П; Бримберг, Дж; Урошевич, Д; Младенович, Н. (2007a). «Поиск окрестностей первично-двойственной переменной для простой задачи размещения объекта» . Информирует J Comput . 19 (4): 552–564. дои : 10.1287/ijoc.1060.0196 .

[20] Хансен, П.; Младенович, Н.; Уросевич, Д. (2006). «Поиск переменных окрестностей и локальное ветвление». Компьютеры и исследования операций . 33 (10): 3034–3045. CiteSeerX 10.1.1.108.987 . дои : 10.1016/j.cor.2005.02.033 .

[21] Младенович, Н.; Пластрия, Ф .; Уросевич, Д. (2006). «Реформулирующий спуск применительно к задачам упаковки кругов». Компьютеры и исследования операций . 32 (9): 2419–2434. дои : 10.1016/j.cor.2004.03.010 .

[22] Хансен, П; Младенович, Н (2003). «Поиск переменного соседства». В Гловере Ф; Кохенбергер Г. (ред.). Справочник по метаэвристике . Международная серия по исследованию операций и науке управления. Том. 57. Дордрехт: Клювер. стр. 145–184. CiteSeerX 10.1.1.635.7056 . дои : 10.1007/0-306-48056-5_6 . ISBN 978-1-4020-7263-5 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]