Том 15, номер 3, 2008 г., Стр. 43-57
УДК 519.87
Т. В. Леванова, А. С. Федоренко
Локальный поиск с чередующимися окрестностями для двухстадийной задачи размещения
Аннотация:
Предложены варианты алгоритма локального поиска с чередующимися окрестностями (VNS) для решения двухстадийной задачи размещения. В рамках данной схемы определены наборы окрестностей и порядок их просмотра для решения этой задачи. Введена новая рандомизированная окрестность, учитывающая специфику задачи и улучшающая работу алгоритма. Приведены результаты экспериментальных исследований предложенных алгоритмов на трудных в вычислительном отношении сериях тестовых задач. Показано, что использование новой окрестности существенно повышает качество работы алгоритма и позволяет находить решения с малой погрешностью за относительно небольшое время. Выполнено сравнение VNS с алгоритмом имитации отжига (SA), имеющим свойство асимптотической сходимости. Сравнительный анализ показал, что предложенный алгоритм превосходит соответствующие результаты SA на большинстве тестовых примеров.
Ключевые слова: дискретная оптимизация, двухстадийная задача размещения предприятий, локальный поиск с чередующимися окрестностями.
Леванова Татьяна Валентиновна 1
Федоренко Анатолий Сергеевич 1
1. Омский филиал Института математики им. С. Л. Соболева СО РАН,
ул. Певцова 13, 644099 Омск, Россия
е-mail: tlevanova@ofim.oscsbras.ru, fas.omsk@mail.ru
Статья поступила 26 февраля 2008 г.
Исправленный вариант — 23 апреля 2008г.
