Алгоритмы локального поиска для задачи о (r/p)-центроиде

Давыдов, Иван Александрович

Алгоритмы локального поиска для задачи о (r/p)-центроиде тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Давыдов, Иван Александрович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Новосибирск МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Алгоритмы локального поиска для задачи о (r/p)-центроиде»

Автореферат диссертации на тему "Алгоритмы локального поиска для задачи о (r/p)-центроиде"

На правах рукописи

ДАВЫДОВ Иван Александрович

АЛГОРИТМЫ ЛОКАЛЬНОГО ПОИСКА ДЛЯ ЗАДАЧИ О (ф)-ЦЕНТРОИДЕ

Специальность 01.01.09 — Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск - 2013

1 г!0Я ¿013

005537775

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор Кочетов Юрий Андреевич

Васильев Игорь Леонидович

кандидат физико-математических наук, доцент, Институт динамики систем и теории управления СО РАН, г. Иркутск, ведущий научный сотрудник

Пяткин Артем Валерьевич

доктор физико-математических наук, доцент, Институт математики им. С.Л. Соболева СО РАН, ведущий научный сотрудник Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского»

Защита состоится 25 декабря 2013 г. в 17 час. 00 мин. на заседании диссертационного совета Д 003.015.01 при Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук (ИМ СО РАН) по адресу: 630090 г. Новосибирск, пр. Ак. Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке ИМ СО РАН. Автореферат разослан -^ноября 2013 г.

Ученый секретарь диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Задачи размещения предприятий имеют широкий круг приложений, возникающих при планировании и реконструкции производства, проектировании сетей обслуживания, в стандартизации, кластерном анализе и других областях. Значительный интерес к задачам так же связан с их высокой сложностью. Исследования в области задач размещения ведутся в Институте математики им. С.Л. Соболева СО РАН с конца 60-х годов прошлого столетия. Актуальность этих исследований обусловлена их важными практическими приложениями. Об этом свидетельствует большое число работ, посвященных задачам размещения. Среди них в первую очередь стоит отметить работы Береснева B.JL, Гимади Э.Х., Дементьева В.Т., Гермейера Ю.Б., Шамардина Ю.В., Колоколова A.A., Антипина A.C., Хамисова О.В., Васильева И.Л., Забуд-ского Г.Г., Левановой Т.В. и др. В настоящее время область дискретной оптимизации, связанная с задачами размещения, активно развивается. Ведутся исследования структуры и вычислительной сложности задач, выделяются полиномиально разрешимые случаи, развиваются точные и приближенные методы их решения.

Цель диссертации состоит в разработке и исследовании методов локального поиска для решения задач о (г|р)-центроиде и о (г|Хр)-медиапоиде, а так же исследовании сложностпого статуса данных задач.

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

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

Научная новизна. Оригинальность и научная новизна полученных результатов состоит в следующем.

1. Проведено исследование сложности дискретной и непрерывной задач о (г|р)-центроиде. Доказано, что непрерывная задача на евклидовой плоскости является Е^-трудной, а дискретная задача является Е^'-трудной даже в случае евклидовых расстояний.

2. Разработан итерационный метод локального поиска для задачи на плоскости. Установлена полиномиальная разрешимость задачи о (г\Хр-\ + +1)-центроиде при фиксированном параметре г.

3. Разработан эффективный итерационный метод локального поиска для решения дискретной задачи о (г|р)-центроиде.

Основные результаты диссертации заключаются в следующем:

1. Установлено, что задача о (г|р)-центроиде является ^-трудной в дискретном варианте, на плоскости и на сети даже в случае евклидовых расстояний между предприятиями и потребителями. Показано, что задача о (г|Х;,)-медиапоиде в каждом из указанных случаев является ЫР-трудной в сильном смысле.

2. Установлено, что задача о (г|Хр_1 + 1)-центроиде на плоскости, т.е. задача оптимального размещения нового предприятия лидера при уже открытых его р — 1 предприятии может быть решена точно за полиномиальное время при фиксированном параметре г.

3. Для задачи о (г|р)-центроиде в дискретном варианте и на плоскости разработаны алгоритмы локального поиска, которые по точности получаемых решений превосходят известные ранее приближенные алгоритмы на тестовых примерах из библиотеки «Дискретные задачи размещения».

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

Практическая и теоретическая ценность. Работа носит теоретический и экспериментальный характер. Установлена вычислительная сложность задачи о (г|р)-центроиде на плоскости. Получены численные методы решения дискретной и непрерывной задач о центроиде. Разработанные методы реализованы в виде программ. Они показали свою эффективность и могут применяться при решении практических задач, а также

при преподавании курсов «Исследование операций» и «Теория принятия решений».

Апробация работы. Все разделы диссертации прошли апробацию на следующих конференциях в России и за рубежом:

— Международная конференция «Дискретная оптимизация и исследование операций», Новосибирск, 2013;

— Международная конференция по исследованию операций (0112011), Цюрих, Швейцария, 2011;

— XV Байкальская международная школа-семинар «Методы оптимизации и их приложения» (МОР2011), пос. Листвянка, 2011;

— XIV Всероссийская конференция «Математическое программирование и приложения», Екатеринбург, 2011;

— Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2009 и 2012;

— Российская конференция «Дискретная оптимизация и исследование операций», Новосибирск, Алтай, 2010;

— Российская конференция «Дискретная оптимизация и исследование операций», Владивосток, 2007;

— V Азиатская международная школа-семинар «Проблемы оптимизации сложных систем», Кыргызская Республика, г. Бишкек, 2009;

— IV Азиатская международная школа-семинар «Проблемы оптимизации сложных систем», Республика Алтай, пос. Чемал, 2006;

— Научные семинары Института математики им. С.Л. Соболева СО РАН;

— Научные семинары Института математики при Университете г. Севилья, Испания.

Публикации. По теме диссертации автором опубликовано 12 работ, в том числе 4 статьи в журналах из списка ВАК.

Объем и структура диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы (82 наименования). Объем диссертации — 113 страниц.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе формулируется задача о (г|р)-центроиде в различных постановках. В диссертации рассматриваются задачи, которые возникают в моделях с конкурентным размещением предприятий. Задано множество клиентов. Для каждого клиента задана его покупательная способность. Две фирмы, лидер и конкурент, последовательно открывают предприятия для обслуживания клиентов. Сначала лидер открывает р предприятий, затем конкурент, зная решение лидера, открывает г предприятий соответственно. Затем каждый клиент выбирает ближайшее из открытых предприятий в качестве своего поставщика. Обслуживание клиента приносит доход владельцу предприятия. Требуется найти такое размещение предприятий лидера, чтобы при наилучшем ответном ходе конкурента доход лидера был максимальным.

Рассматриваемые задачи являются представителями конкурентных моделей размещения, а так же могут быть сформулированы в терминах некооперативной игры Штаккельберга. Представим дискретную задачу о центроиде в виде задачи двухуровневого целочисленного программирования. Пусть I — множество мест для размещения предприятий. 3 — множество клиентов. Обозначим через ш, величину дохода, получаемого игроком от обслуживания ^'-го клиента. Будем предполагать, что это положительная величина для каждого з € ./. Предпочтения клиентов на множестве предприятий будем задавать матрицей (д^)- Если дг] > ду, то клиент з из открытых предприятий г и к выбирает предприятие к. Для наглядности можно считать, что матрица (д¿¿) задает расстояния от клиентов до предприятий, и клиент предпочитает наименее удаленное предприятие независимо от того, какому игроку оно принадлежит.

Введем переменные задачи:

Г 1, если лидер открывает предприятие г,

X'__\

' 1 ^ О в противном случае,

Г 1, если конкурент открывает предприятие г, ^1 \ 0 в противном случае,

Г 1, если клиент ] обслуживается из предприятия лидера, \ 0, если клиент з обслуживается из предприятия конкурента.

Пусть вектор х задает решение лидера. Определим множество предприятий (х), позволяющих конкуренту захватить клиента ], т.е. 13{х) = = {г 6 / | < т'1П1с1 (91] I Х1 = !)}■ Из определения этого множества следует, что в случае равных расстояний до предприятий лидера и конкурента клиент отдает предпочтение лидеру [5]. Другие варианты поведения клиентов можно найти в [3].

С использованием введенных обозначений задача о (г|р)-цептроиде может быть представлена как задача двухуровневого целочисленного программирования [1]: найти

тах^\о^и^х) ¿6.7

при ограничениях

¿е/

^€{0,1}, ге/, где и* (х), у* (х) — оптимальное решение задачи конкурента: найти

тах} (1 — щ) у>и

при ограничениях

¡/¿,^•€{0,1}, г 6 7,^6 3.

Целевая функция

\У(х) =

задает суммарный доход лидера при условии, что он открывает ровно р предприятий. Эта величина зависит от оптимального решения задачи конкурента. Целевая функция в задаче конкурента определяет его доход. Первое ограничение позволяет конкуренту открывать ровно г предприятий. Второе ограничение не разрешает конкуренту обслуживать клиента 3, если в множестве Т3 {х) нет его предприятий. Вектор х и множества 1]{х) для всех ] 6 7 в задаче конкурента считаются известными.

Непрерывная задача может быть представлена следующим образом. Пусть п точек на двухмерной евклидовой плоскости задают расположение клиентов. Каждый клиент j имеет положительный вес го,-. Обозначим через X множество из р точек, где лидер размещает свои предприятия, а через У — множество из г точек, где размещаются предприятия конкурента. Расстояние между клиентом ] и ближайшим из предприятий лидера обозначим через ¿(о,Х). Аналогично, <1(],У) — расстояние до ближайшего предприятия конкурента. Будем говорить, что клиент ] предпочитает У, если <¿(.7, У) < X), и предпочитает X в противном случае. Через и (У -< X) обозначим множество клиентов, предпочитающих У. т.е.

[/(УкХ) = {Лф-,У)<ф-,Х)}.

Тогда доход конкурента -< X) определяется как суммарный вес

соответствующих клиентов:

ж(У -<х) = ^Г | з е и (У ■< х)).

При заданном решении X, конкурент стремится максимизировать свой доход. Значение этого дохода Ш* (X) определяется как решение следующей задачи:

1У*т= тах И^(У-<Х).

У, |У|=г-

Эту задачу принято называть задачей о (?'|Хр)-медиаиоиде или задачей конкурента. Лидер стремится максимизировать собственный доход или,

что то же самое, минимизировать доход конкурента. Минимальное значение W*(X*) потерь лидера определяется из решения следующей задачи:

W*(X*)= min W" (X). v ' x,\x\ =p

Наилучшее решение лидера X* определяет его доход как J2 Wj—W*(X*).

з=1

Требуется найти X* и W*{X*).

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

В разд. 1.2 рассматривается вопрос о сложности непрерывной задачи на плоскости в общем случае. Доказана

Теорема 1. Задача о (г\р)-центроиде на двухмерной евклидовой плоскости является Ef -трудной.

Следствие 1. Дискретная задача о (ф)-центроиде является E-f-трудной даже в случае, когда клиенты и предприятия представлены точками на двухмерной евклидовой плоскости, а матрица dij удовлетворяет аксиомам евклидовой метрики.

Следствие 2. Задача о (г|р)-центроиде на сети является -трудной даже в случае пленарного графа, вершины которого представлены точками на двухмерной плоскости, а длины ребер определяются евклидовой метрикой.

Следствия 1 и 2 обобщают результаты, полученные Нолтмейером и др. в работе [7]. Однако техника доказательства, использованная авторами, оказалась не применима к задаче па плоскости, что потребовало разработки принципиально новой схемы.

В разд. 1.3 обобщаются известные результаты о сложности задачи конкурента, известной как задача о (г|Хр)-медианоиде. Доказано, что

Теорема 2. Задана конкурента на двухмерной евклидовой плоскости является NP-трудной в сильном смысле.

Следствие 3. Дискретная задача конкурента является NP-трудной в сильном смысле даже в случае, когда клиенты и предприятия представлены точками на двухмерной евклидовой плоскости.

Следствие 4. Задача конкурента на сети является КТР-трудной в сильном смысле даже в случае планарного графа, вершины которого представлены точками на двухмерной плоскости, а длины ребер определяются как евклидовы расстояния между вершинами.

Во второй главе подробно рассматривается непрерывная задача о центроиде.

В разд. 2.2 приводится подробная формулировка задачи и математическая модель.

В разд. 2.3 приводится подробное описание непрерывной задачи конкурента. Эта задача записывается в виде задачи целочисленного линейного программирования и решается с использованием метода ветвей и границ.

Рассмотрим точный алгоритм для решения задачи конкурента. Он состоит из двух этапов. На первом этапе исходная задача сводится к задаче линейного целочисленного программирования. Чтобы "захватить" клиента ] конкуренту необходимо разместить свое предприятие ближе, чем ближайшее предприятие лидера, т.е. на меньшем расстоянии, чем X) от клиента Каждому клиенту ] сопоставим диск радиуса с

центром в точке, где расположен этот клиент. Если два или более дисков пересекаются, то размещение предприятия внутри пересечения позволяет конкуренту захватить сразу несколько клиентов. Пересекаясь, диски делят плоскость на некоторое количество замкнутых областей. Для каждой из областей можно посчитать доход, который получит конкурент, разместив свое предприятие в этой области. Таким образом, для решения задачи конкурента необходимо выбрать г областей, суммарный доход от которых будет максимальным. Общее количество таких областей довольно велико, однако можно ограничиться рассмотрением только выпуклых областей. Общее число выпуклых областей можно ограничить величиной п2. Обозначим через (абинарную матрицу, выделяющую клиентов, которые будут обслуживаться в предприятии конкурента, если оно будет открыто в соответствующей области, т.е. а^ := 1 если, открыв предприятие в области к, конкурент захватывает клиента и а^ := 0 в противном случае. Далее потребуется два множества переменных:

{1, если конкурент открывает свое предприятие в области к, О в противном случае.

{1. если конкурент захватывает клиента j, О в противном случае.

С использованием этих переменных задача конкурента может быть записана как задача линейного целочисленного программирования:

max^^WjZj з=1

при ограничениях zj < ^^ dkjVk, 3 — 1, • • •, п,

fc=i

ттг *;=1

yh,Zj в {0,1}, к - 1,.. .,тп, j = 1,.. . ,п.

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

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

1. Построить начальное решение лидера. Обнулить рекорд целевой функции.

Основной цикл В течение заданного количества итераций делать следующее.

2. Найти решение задачи конкурента для текущего решения лидера. Если значение целевой функции превзошло рекорд, то обновить рекорд.

3. Зафиксировать предприятия конкурента. Найти оптимальный ответ лидера на размещение конкурента. Перейти на шаг 2.

Для уточнения шага 3 предлагается процедура кластеризации, использующая точное решение задачи об (1,1)-центроиде [4].

В разд. 2.5 рассматривается задача о (г | Хр-\ + 1)-центроиде, в которой лидер имеет р — 1 открытых предприятий и хочет открыть еще одно, выбрав для этого наилучшую позицию. Показано, что количество

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

Теорема 4. Задача о (r|Xp_i + 1 )-центроиде разрешима за полиномиальное время при фиксированном г.

В разд. 2.6 полученный результат применяется в локальном поиске. В качестве основной эвристики используется поиск с чередующимися окрестностями (VNS, [6]), где за основу взята окрестность (/с, Z)-Swap с различными величинами к и I. В этой окрестности к предприятий лидера перемещаются на новые места, но не далее чем на расстояние I от их текущих позиций.

В разд. 2.7 приводятся результаты численных экспериментов. Представленный алгоритм запрограммирован в среде Delphi 7.0 и тестировался на примерах из электронной библиотеки «Дискретные задачи размещения». Во всех примерах п = 50, клиенты размещены случайным образом с равномерным распределением на квадрате 7000 х 7000. Рассматривается два типа покупательной способности: равная Wj = 1 и дифференцированная, когда покупательная способность выбирается с равномерным распределением из интервала, wj 6 [1,200]. Для всех примеров изучается поведение алгоритма при р = г = 10. Результаты численных экспериментов свидетельствуют о существенном улучшении качества получаемых решений по сравнению с предшествующими алгоритмами.

В третьей главе подробно рассматривается дискретная задача о (г |р)-центроиде.

В разд. 3.1 приводится формулировка задачи и ее представление в виде задачи двухуровневого целочисленного программирования.

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

Г 1, если клиент j выбирает предприятие г, ^ \ 0 в противном случае.

Тогда задачу конкурента можно записать следующим образом:

при ограничениях

£ yij< i, jeJ, (2)

ieij(x)

Уг>Уа> 0, ieljeJ, (3)

X)^ =r' (4)

гё/

y«,y»j е {0,1}, ieljeJ. (5)

Поставим в соответствие ограничениям (2) вектор неотрицательных переменных Аj и рассмотрим Лагранжеву релаксацию задачи по этим ограничениям:

LR{А) = шах - Л,-) £ Ун + Ц AJ

Vi'Vii j€J ¿e/j(x) jeJ

при ограничениях (3),(4),(5).

Заметим, что при заданном векторе А величина LR(А) может быть вычислена точно за полиномиальное время. Пусть множество Ji(x) задает тех клиентов, которые предпочтут предприятие i любому из предприятий лидера в решении х. если это предприятие будет открыто конкурентом:

Mx) = {jzJ\ieIj(x)}. ■

Для каждого г € / вычислим доход конкурента от открытия этого предприятия, равный J2jzJi(x) max{°i } и выберем г наиболее доходных предприятий. Легко проверить, что такое решение дает точное значение величины LR(А). Она является верхней оценкой на максимальный доход конкурента при любых неотрицательных значениях величин Аj. Решение двойственной задачи

DP = min LR{ А)

А>0

дает наилучшую из таких верхних оценок.

Теорема 5. Оптимальное значение линейной релаксации задачи конкурента совпадает с решением двойственной задачи DP.

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

В разд. 3.3 приводится описание алгоритма поиска с запретами для

дискретной задаче о центроиде.

В разд. 3.4 приводятся результаты численных экспериментов. Разработанный алгоритм запрограммирован в программной среде Delphi 7.0 и тестировался на персональном компьютере Fujitsu-Siemens Amilo Pro V2040 1,6 ГГц. Численные эксперименты показали, что новый метод заметно быстрее своих предшественников находит известные оптимальные решения лидера. Если же время решения задачи ограничено, то частота получения оптимума остается достаточно большой, а средняя относительная погрешность получаемых решений оказывается незначительной.

В разд. 3.5 рассматривается альтернативный метод решения задачи конкурента, основанный на стохастическом поиске с запретами. Показано, что такой подход позволяет получать решения высокого качества па примерах с неевклидовой метрикой.

В заключении приводятся основные результаты диссертации.

Основные результаты

• Установлено, что задача о (ф)-центроиде является Ef-трудной в дискретном варианте, на плоскости и на сети даже в случае евклидовых расстояний между предприятиями и потребителями. Показано, что задача о (г|Хр)-медианоиде в каждом из указанных случаев является NP-трудной в сильном смысле.

• Установлено, что задача о (riXp_i + 1)-центроиде на плоскости, т.е. задача оптимального размещения нового предприятия лидера при уже открытых его р - 1 предприятии может быть решена точно за полиномиальное время при фиксированном параметре г.

• Для задачи о (г|р)-центроиде в дискретном варианте и на плоскости разработаны алгоритмы локального поиска, которые по точности получаемых решений превосходят известные ранее приближенные алгоритмы на тестовых примерах из библиотеки «Дискретные задачи размещения».

Список литературы

[1] Alekseeva E., Kochetova N., Kochetov Y., Plyasunov A. A hybrid memetic algorithm for the competitive p-median problem // Proceedings of INCOM (Moscow, Russia, June 3-5, 2009). -P. 1516-1520.

[2] Barahona F.. Cliudak F.A. Near-optimal solutions to large-scale facility location problems // Discrete Optimization. —2005. —V. 2. —P. 35-50.

|3| Drezner T., Eiselt H.A. Consumers in competitive location models //' In: Z. Drezner, H. Hamacher (Eds.) Facility Location. Applications and Theory. —2004, Berlin: Springer. -P. 151-178.

[4] Drezner Z. Competitive location strategies for two facilities // Regional Science and Urban Economics. -1982. -V.12., -P. 485-493.

[5] Hakimi, S.L. Locations with spatial interactions: competitive locations and games, in: P. Mirchandaiii, R. Francis (Eds.) Discrete Location Theory. -1990, Wiley. —P. 439-478.

[Gj Hansen P., Mladenovic N. Variable neighborhood search: principles and applications // European J. Oper. Res. -2001. -V. 130 -P. 449-467.

[7] Noltemeier H., Spoerhase J., Wirth H. Multiple voting location and single voting location on trees // European J. Oper. Res. —2007. —V. 181. —P. 654-667.

Публикации автора по теме диссертации

1. Давыдов И.А. Локальный поиск с запретами для дискретной задачи о (г|р)-центроиде // Дискретный анализ и исследование операций. -2012. -Т. 19, № 2. -С. 19-40.

2. Davydov I., Kochetov Yu., Carrizosa E. VNS heuristic for the (ф)-centroid problem on the plane // Electronic Notes in Discrete Mathematics. -2012. -Vol. 39. -P. 5-12

3. Davydov I., Kochetov Y., Carrizosa E. A local search heuristic for the (r|p)-centroid problem in the plane //' Computers and Operations Research. —2013. D01:10.1016/j.cor.2013.05.003.

4. Davydov I., Kochetov Y., Plyasunov A. On the complexity of the {r\p)~ centroid problem on the plane // TOP. -2013. D01:10.1007/sll750-013-0275-y.

5. Carrizosa E., Davydov I., Kochetov Y. A new alternating heuristic for the (r|p)-centroid problem on the plane. // Operations Research Proceedings. -2011, Berlin: Springer. - 2012, —P. 100-106.

6. Davydov I., Kochetov Yu., Mladenovic N., Urosevic D. Fast metaheuristics for the discrete (r|p)-centroid problem. // Международная конференция «Дискретная оптимизация и исследование операций»: Материалы конференции. —Новосибирск: Изд-во Ин-та математики, 2013. —С. 59.

7. Давыдов H.A. Локальный поиск для задачи о (г|р)-центроиде на плоскости // «Проблемы оптимизации и экономические приложения»: материалы V Всероссийской конференции. — Омск, Изд-во Ом. гос. унта, 2012. -С. 119.

8. Давыдов И.А. Новая альтернирующая эвристика для задачи об (ф)-центроиде на плоскости. // Тезисы XV Байкальской международной школы-семинара «Методы оптимизации и их приложения». Т.4: Дискретная оптимизация. Иркутск: РИО ИДСТУ СО РАН, 2011. -С. 88-94

9. Давыдов И.А. Модифицированная альтернирующая эвристика для непрерывной задачи о (г,р)-центроиде.// Информационный бюллетень Ассоциации математического программирования. №12. Екатеринбург: УрО РАН, 2011. -С. 170

10. Давыдов И.А. Верхние и нижние оценки в локальном поиске для задачи о (г|р)-цеитроиде// Российская конференция «Дискретная оптимизация и исследование операций»: Материалы конференции. —Новосибирск: Изд-во Ин-та математики, 2010. —С. 112.

11. Давыдов И.А. Поиск с запретами для задачи о (г|р)-центроиде // «Проблемы оптимизации и экономические приложения»: материалы IV Всероссийской конференции. — Омск, Изд-во Ом. гос. ун-та, 2009 —С.122

12. Давыдов И.А. Вероятностный поиск с запретами для задачи о (г|р)-центроиде // Труды ИВМ и МГ, Информатика, 9, Новосибирск 2009, —С. 157-1С2.

Давыдов Иван Александрович

Алгоритмы локального поиска для задачи о (ф)-цеитроиде

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 20.10.13. Формат 60x84 1/16. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ № 115.

Отпечатано в ООО "Омега Принт" пр. Ак. Лаврентьева, 6, 630090 Новосибирск

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Давыдов, Иван Александрович, Новосибирск

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ МАТЕМАТИКИ им. С.Л. СОБОЛЕВА СИБИРСКОГО ОТДЕЛЕНИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК

На правах рукописи

О 2 СИ -4 5 3 02 4

ДАВЫДОВ Иван Александрович

АЛГОРИТМЫ ЛОКАЛЬНОГО ПОИСКА ДЛЯ ЗАДАЧИ О (г|р)-ЦЕНТРОИДЕ

01.01.09 — Дискретная математика и математическая кибернетика

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель д.ф.-м.н. Ю.А. Кочетов

Новосибирск — 2013

Оглавление

Введение 4

1 Вычислительная сложность задачи о (г|р)-центроиде 22

1.1 Математическая модель........................................33

1.2 Сложность задачи на плоскости ..............................34

1.3 Сложность задачи конкурента................................41

1.4 Основные результаты первой главы ..........................45

2 Поиск с чередующимися окрестностями для задачи о [г\р)~ центроиде на плоскости 46

2.1 Постановка задачи..............................................51

2.2 Задача конкурента..............................................52

2.3 Альтернирующая эвристика....................................54

2.4 Подзадача для одного предприятия лидера..................56

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

2.6 Вычислительные эксперименты................................65

2.7 Основные результаты второй главы..........................70

3 Локальный поиск с запретами для дискретной задачи о (г|/;)-центроиде 73

3.1 Постановка задачи..............................................77

3.2 Лагранжева релаксация........................................79

3.3 Метод локального поиска с запретами........................86

3.4 Экспериментальные исследования............................90

3.5 Стохастический поиск с запретами для задачи конкурента 96

3.6 Основные результаты третьей главы.............100

Заключение 102

Литература

103

Введение

Актуальность темы. Задачи размещения предприятий имеют широкий круг приложений, возникающих при планировании и реконструкции производства, проектировании сетей обслуживания, в стандартизации, кластерном анализе и других областях. Значительный интерес к задачам так же связан с их высокой сложностью. Исследования в области задач размещения ведутся в Институте математики им. C.J1. Соболева СО РАН с конца 60-х годов прошлого столетия. Актуальность этих исследований обусловлена их важными практическими приложениями. Об этом свидетельствует большое число работ, посвященных задачам размещения. Среди них в первую очередь стоит отметить работы Бересиева B.JL, Гимади Э.Х., Дементьева В.Т., Гермейера Ю.Б., Шамардина Ю.В., Колоколова A.A., Антипина A.C., Хамисова О.В., Васильева И.Л., Забуд-ского Г.Г., Левановой Т.В. и др. В настоящее время область дискретной оптимизации, связанная с задачами размещения, активно развивается. Ведутся исследования структуры и вычислительной сложности задач, выделяются полиномиально разрешимые случаи, развиваются точные и приближенные методы их решения.

Цель диссертации состоит в разработке и исследовании методов локального поиска для решения задач о (г|р)-цеитропде и о

(г|Хр)-медианоиде, а так же исследовании сложностного статуса данных задач.

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

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

Научная новизна. Оригинальность и научная новизна полученных результатов состоит в следующем.

1. Проведено исследование сложности дискретной и непрерывной задач о (г|р)-центроиде. Доказано, что непрерывная задача на евклидовой плоскости является Е^-трудной, а дискретная задача является Т,^-трудной даже в случае евклидовых расстояний.

2. Разработан итерационный метод локального поиска для задачи на плоскости. Установлена полиномиальная разрешимость задачи о (г + +1)-центроиде при фиксированном параметре г.

Основные результаты диссертации заключаются в следующем.

1. Установлено, что задача о (г|р)-центроиде является Е^-трудной в дискретном варианте, на плоскости и на сети даже в случае евклидовых расстояний между предприятиями и потребителями. Показано, что задача о (г|Хр)-медианоиде в каждом из указанных случаев является ИР-трудной в сильном смысле.

2. Установлено, что задача о + 1)-центроиде на плоскости, т.е. задача оптимального размещения нового предприятия лидера при уже открытых его р — 1 предприятии, может быть решена точно за полиномиальное время при фиксированном параметре г.

3. Для задачи о (г|р)-центроиде в дискретном варианте и на плоскости разработаны алгоритмы локального поиска, которые по точности получаемых решений превосходят все известные ранее приближенные алгоритмы на тестовых примерах из библиотеки «Дискретные задачи размещения».

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