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

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

Оглавление диссертации кандидат наук Давыдов, Иван Александрович

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Литература

103

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

Введение

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

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

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

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

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

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

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

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

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

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

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

2. Установлено, что задача о + 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 — множество клиентов. Обозначим через Шj величину дохода, получаемого игроком от обслуживания ^'-го клиента. Будем предполагать, что это положительная величина для каждого j £ 3. Предпочтения клиентов на множестве предприятий будем задавать матрицей (д^). Если д^ > д^, то клиент ^ из открытых предприятий г и к выбирает предприятие к. Для наглядности можно считать, что матрица (д^) задает расстояния от клиентов до предприятий, и клиент предпочитает наименее удаленное предприятие независимо от того, какому игроку оно принадлежит. Введем переменные задачи:

О в противном случае

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

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

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

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

Пусть вектор х задает решение лидера. Определим множество предприятий позволяющих конкуренту захватить клиента ^ т.е. 1^{х) = = {г Е / | дц < тт/е/(^| ж/ = 1)}. Из определения этого множества следует, что в случае равных расстояний до предприятий лидера и конкурента клиент отдает предпочтение лидеру [52]. Другие варианты поведения клиентов можно найти в [41].

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

где и*Лх),у1{х) - оптимальное решение задачи конкурента: найти

тах

X

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

жге{0,1}, ге/,

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

ге!

0,1},

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

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

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

Тогда доход конкурента IV(У -< X) определяется как суммарный вес соответствующих клиентов:

\¥(У -< X) = (Ч- | у б и(У ~< X)).

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

щей задачи:

W*(X) = max W(Y -< X).

Y, \Y\=r

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

W\X*) = min W\X). х,\х\ =р

п

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

з=i

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

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

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

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

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

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

метрикой.

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

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

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

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

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

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

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

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

Рассмотрим точный алгоритм для решения задачи конкурента. Он со-

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

I 1, если конкурент открывает свое предприятие в области к, У к = <

I 0 в противном случае,

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

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

Е

.7=1

тах > \jjjzj

при ограничениях < ^^ а^Ук, 3 — 1,.. -, п,

к=1

к-= 1

Ук, ^ е {0,1}, к = 1,..., т, з = 1,..., п.

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

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

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

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

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

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

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

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

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

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

В разд. 2.7 приводятся результаты численных экспериментов. Представленный алгоритм запрограммирован в среде Delphi 7.0 и тестировался на примерах из электронной библиотеки «Дискретные Задачи Размещения». Во всех примерах п = 50, клиенты размещены случайным образом с равномерным распределением на квадрате 7000x7000. Рассматривается два типа покупательной способности: равная Wj = 1 и диффе-

ренцированная, когда покупательная способность выбирается с равномерным распределением из интервала, Wj G [1,200]. Для всех примеров изучается поведение алгоритма при р = г = 10. Результаты численных экспериментов свидетельствуют о существенном улучшении качества получаемых решений по сравнению с предшествующими алгоритмами.

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

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

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

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

) ■

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

(1)

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

(2)

ieij(x)

Vi > yij i е i,j е J,

(з)

(4)

iel

yi,Vij£{ 0,1}, iel,jeJ.

(5)

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

LR{А) = max ^(ол,- - Xj) У] уц + V Xj (6)

УаУг] . т г / \ • т

jeJ JeJ

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

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

Ji(x) = {je.J\ie lj(x)}.

Для каждого г Е / вычислим доход конкурента от открытия этого предприятия, равный (д.) max{0, ujj — Xj} и выберем г наиболее доходных предприятий. Легко проверить, что такое решение дает точное значение величины LR(А). Она является верхней оценкой на максимальный доход конкурента при любых неотрицательных значениях величин Xj. Решение двойственной задачи

DP = min LR( X)

А>0

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

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

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

• базового, с движением в направлении субградиента;

• модифицированного, где движение происходит в направлении разности двух последовательных субградиентов;

• так называемого объемного метода, предложенного в работе [20].

Проведенные численные эксперименты показали предпочтительность второго метода. В разд. 3.3 приводится описание алгоритма поиска с запретами для дискретной задаче о центроиде.

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

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

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

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

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

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

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

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

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.

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

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

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

Давыдов И.А. Модифицированная альтернирующая эвристика для

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

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

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

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

Глава 1

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

Задачи размещения производства составляют широкий пласт математических моделей исследования операций. Это богатая тема как для теоретических и экспериментальных исследований, так и для приложений, возникающих при размещении предприятий и складов, полицейских участков и служб пожарной безопасности, станций скорой помощи, создании беспроводных сетей связи и др. [39]. В большинстве таких моделей одно лицо принимает решение, стремясь максимизировать получаемую прибыль или минимизировать суммарные затраты на обслуживание клиентов. В настоящей диссертации рассматривается более сложная ситуация, когда два лица (игрока) последовательно принимают решения. Эта область — конкурентных задач размещения. Она обязана своим рождением пионерской работе Хоттелинга [58]. В ней исследуются эгоистические стратегии поведения двух игроков в предположении, что клиенты располагаются на линии (шоссе, береговая линия и т.п.). Позже появились более богатые модели, интересные как с точки зрения

экономики и теории игр, так и для методов оптимизации и исследования операций. С обзором таких моделей и результатов их исследования можно познакомиться, например, в [52, 56, 63] (см. также [10, 22]).

Интерес к задачам о центроиде связан с пионерскими работами Сл-эйтера [75] и Хакими [52]. Само название (г|т?)-центроид введено в [51]. Содержательно задача формулируется следующим образом. Рассмотрим конечное множество / возможных мест размещения предприятий и конечное множество 3 мест расположения клиентов. Матрица Е Е 1,э Е 3, задает расстояние от клиентов до предприятий. Величина Wj определяет доход игрока при обслуживании клиента у. Игроки последовательно принимают решения об открытии предприятий, стремясь максимизировать свой доход. Сначала на рынок выходит первый игрок (лидер) и открывает р предприятий. Зная это решение, второй игрок (конкурент) открывает свои г предприятий. Каждый клиент из открытых р + г предприятий выбирает ближайшее к нему предприятие в качестве своего поставщика. В итоге, множество клиентов делится на две части: клиенты лидера и клиенты конкурента. Задача состоит в том, чтобы найти р предприятий лидера, которые дают ему максимальный доход (долю рынка) при наиболее сильном ответном ходе конкурента. На сегодняшний день основные исследования задачи разделились на три направления:

- дискретная задача, когда множества клиентов и мест для размещения предприятий конечны [4, 12, 15, 59];

- задача на сети, когда клиенты размещаются в вершинах графа, а предприятия можно открывать в любых точках на ребрах [67];

- задача в евклидовом пространстве, когда клиенты представлены конечным множеством точек на двумерной евклидовой плоскости, а предприятия могут размещаться в произвольных точках или в заданной ограниченной области на плоскости [34].

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

Дискретная задача является вариантом одношаговой игры Вороного [82] для случая р = г. Игра Вороного является геометрической моделью конкурентного размещения предприятий, в которой два игрока размещают равное количество предприятий на графе. Каждая вершина графа представляет место для размещения предприятия или клиента. Клиент контролируется игроком — владельцем ближайшего открытого предприятия, и приносит этому игроку определенный доход. Каждый игрок стремится максимизировать свой доход. В случае, если конкурент начинает расставлять предприятия только после того, как лидер установил все свои р предприятий, игра называется игрой Вороного. Этот факт позволяет применять подходы из области экономики и теории игр при исследовании задачи.

Список литературы диссертационного исследования кандидат наук Давыдов, Иван Александрович, 2013 год

Литература

[1] Алексеева Е.В., Кочетова H.A. Верхние и нижние границы для конкурентной задачи о р-медиане // Труды XIV-й Байкальской международной школы-семинара Методы оптимизации и их приложения. -Иркутск, РИО ИДСТУ СО РАН. -2008. -Т. 1. -С. 563-569.

[2] Васильев И.Л., Климентова К.Б., Кочетов Ю.А. Новые нижние оценки для задачи размещения с предпочтениями клиентов // Журнал вычислительной математики и математической физики. -2009. -Т. 49, №6. -С. 1055-1066.

[3] Гончаров Е. Н., Кочетов Ю. А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискретный анализ и исследование операций. —2002. —Сер. 2. —Т. 9, №2. —С. 13-30.

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

[5] Еремеев A.B. Вполне полиномиальная рандомизированная аппрок-симационная схема на основе эволюционного алгоритма // Дис-

кретный анализ и исследование операций. —2010. —Т. 17, № 4. —С. 3-17.

[6] Забудский Г.Г., Амзин И.В. Сужение области поиска решения задач Вебера на плоскости с прямоугольными запрещенными зонами // Автоматика и елемеханика. —2012 —№ 5. —С. 71-83.

[7] Кочетов Ю., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. - 2003. Сер. 2. - Т. 10, №1. - С. 11-43.

[8] Кочетов Ю.А., Пащенко М.Г., Плясунов A.B. О сложности локального поиска в задаче о р-медиане // Дискретный анализ и исследование операций. -2005. -Сер. 2. -Т. 12, №2. -С. 44-71.

[9] Леванова Т.В., Лореш М.А. Алгоритмы муравьиной колонии и имитации отжига для задачи о р-медиане // Автоматика и телемеханика. -2004, —№ 3, -С. 80-88.

[10] Панин A.A., Пащенко М.Г., Плясунов A.B. Приближенные алгоритмы для задачи конкурентного размещения производства и ценообразования // АиТ. —2014. настоящий выпуск.

[11] Aarts Е. Ii. L., Lenstra J. К. (Eds.) Local Search in Combinatorial Optimization. — Chichester: John Wiley &; Sons, 1997.

[12] E. Alekseeva, N. Kochetova, Y. Kochetov, A. Plyasunov. Heuristic and exact methods for the discrete (r|p)-centroid problem // Lecture Notes in Computer Science -V.6022, Berlin: Springer. — 2010. - P. 11-22.

[13] 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. 15161520.

[14] Alekseeva E., Kochetov Yu., Plyasunov A. Complexity of local search for the p-median problem // European Journal of Operational Research. -2008. -V. 191. P. 736-752. .

[15] Alekseeva E., Kochetov Y. Matheuristics and exact methods for the discrete (r|p)-centroid problem // In: Talbi E-G., Brotcorne L. (Eds.): Metaheuristics for bi-level optimization. —2013, Berlin: Springer.

[16] Angel E., Zissimopoulos V. On the classification of NP-complete problems in terms of their correlation coefficient // Discrete Appl. Math. -2000. -V. 99. -P. 261-277.

[17] Ausiello G., Cresccnzi P., Gambosi G., Kann V., Marchetti- Spaccamela A., Protasi M. Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties. —Berlin: Springer-Verlag, 1999.

[18] Banik A., Das S., Maheshwari A., Smid M. The discrete voronoi game in a simple polygon, in: D.-Z. Du, G. Zhang (Eds.) Computing and Combinatorics, COCOON, LNCS 7936. -2013, Springer, Berlin. -P. 197-207.

[19] Bauer A., Domshke W., Pesch E. Competitive location on a network // European Journal of Operational R.esearch. —1993. —V. 66. —P. 372- 391.

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

[21] Benati S., Laporte G. Tabu search algorithms for the (r|Xp)-medianoid and (r|p)-centroid problems // Location Science. —1994. —V. 2, No. 2. -P. 193-204.

[22] Beresnev V., Mel'nikov A. Approximate algorithms for the competitive facility location problem //J. Appl. Indust. Math. 2011. —V. 5, No. 2. —P. 180-190.

[23] Bhadury J., Eiselt H.A., Jaramillo J.H. An alternating heuristic for rnedianoid and centroid problems in the plane // Computers and Operations Research. -2003. -V. 30. -P. 553—565.

[24] Brimberg J., Hansen P., Mladenovic N. Attraction probabilities in variable neighborhood search // 40R.. —2010. —V.8, No 2. -P. 181194.

[25] Burke E.K., Kendall G. (Eds.) Search Methodologies. Introductory Tutorials // Optimization and Decision Support Techniques. —Berlin: Springer, 2005.

[26] Campos-R.odriguez C.M., Moreno-Pérez J.A. Relaxation of the condorcet and simpson conditions in voting location // European J. Oper. Res. -2003. V.145. -P. 673-683.

[27] Campos-Rodriguez C.M., Moreno-Pérez J.A. Multiple voting location problems // European J. Oper. R.es. -2008. -V. 191, No.2. -P. 437453.

[28] Campos-Rodriguez C.M., Santos-Peate D.R., Moreno-Prez J.A. An exact procedure and LP formulations for the leader-follower location problem // TOP. -2010. -V. 18, No.l. -P. 97-121.

[29] Campos-Rodriguez C.M., Moreno-Pérez J.A., Santos-Peñate D.R. Particle swarm optimization with two swarms for the discrete {r\p)-centroid problem // LNCS. -2012. -V. 6927. -P. 432-439.

[30] Carrizosa E., Conde E., Munoz-Marquez M., Puerto J. Simpson points in planar problems with locational constraints. The round-norm case // Mathematics of Operations Research. -1997. —V.22. -P. 276-290.

[31] Carrizosa E., Conde E., Munoz-Marquez M., Puerto J. Simpson points in planar problems with locational constraints. The polyhedral-gauge case // Mathematics of Operations Research. —1997. —V.22. —P. 291300.

[32] Carrizosa E., Davydov I., Kochetov Y. A new alternating heuristic for the (r|]?)-centroid problem on the plane. // Operations R.esearch Proceedings. -2011, Berlin: Springer. - 2012, -P. 100-106.

[33] CPLEX: http://www-142.ibm.com/software/products/ru/ru/ilogcple/

[34] Davydov I., Kochetov Y., Carrizosa E. A local search hcuristic for the (rjp)-centroid problem in the plane // Computers and Operations R.esearch. -2013. DOLIO. 1016/j.cor.2013.05.003.

[35] 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.

[36] Discrete Location Problems. Benchmark library. http:// math.nsc.ru/AP/benchmarks/index.html

[37] Dreo J., Petrowski A., Siarry P., Taillard E. Metaheuristics for Hard Optimization. —2006, Berlin: Springer.

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

[39] Drezner Z. Facility Location. A Survey of Applications and Methods. —1995, Berlin: Springer.

[40] Drezner Z., Suzuki A., Drezner T. Locating multiple facilities in a planar competitive environment //Journal of Operations Research Society of Japan. -2007. -V. 50. -P. 249-262.

[41] 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.

[42] Fathian M., Amiri B., Maroosi A. Application of honey-bee mating optimization algorithm on clustering // Applied Mathematics and Computation. -2007. -V. 190, No. 2. -P. 1502-1513.

[43] Festa P., R.esende M. G. C., GRASP: An annotated bibliography. In: C. C. R.ibeiro, P. Hansen (Eds.) Essays and surveys in metaheuristics. -2002, Kluwer Academic Publishers. , -2002P. 325-368.

[44] Frangeoni A. About Lagrangian methods in integer optimization // Ann. Oper. Res. -2005. -V. 139. -P. 163-193.

[45] Geoffrion A.M. Lagrangean relaxation for integer programming // Math. Programming Study. -1974. -V. 2. -P. 82-114.

[46] Gendreau M., Potvin J. Y. Metaheuristics in combinatorial optimization // Annals of Operations Research. —2005. —V. 140. — P. 189-213.

[47] Glover F., Laguna M. Tabu Search. —1997, Boston: Kluwer Academic Publishers. —408pp.

[48] Glover F. Future paths for integer programming and links to artificial intelligence. // Comp. Oper. Res. -1986. -V. 13. -P. 533-549.

[49] Guinard M. Lagrangian Relaxation // TOP. -2003. -V. 11. -P. 215228.

[50] Hakimi S.L. On locating new facilities in a competitive environment. —1981, ISOLDE Conference, Skodsborg, Denmark.

[51] Hakimi S.L. On locating new facilities in a competitive environment// European Journal of Operational Research. —1983. —V. 12. —P. 29-35.

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

[53] Hansen P., Labbe M. Algorithms for voting and competitive location on a network // Transportation Science. —1988. —V. 22. -P. 278-288.

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

[55] Hansen P., Mladenovic N. First vs best improvement: An empirical study // Discrete Applied Mathematics. —2006. -V. 154. —P. 802817.

[56] Hansen P., Thisse J.F., Wendell R.E. Equilibrium analysis for voting and competitive location problems, in: P. Mirchandani, R.. Francis (Eds.) Discrete Location Theory. -1990, Wiley. - P. 479-502.

[57] Held M., Wolfe P., Crowder II. P. Validation of subgradient optimization // Math. Programming. —1974. —V. 6, No.l. -P. 62-88.

[58] Hotelling H. Stability in competition // Economic J. —1929. —V. 39. -P. 41-57.

[59] Kochetov Y. A. Facility location: discrete models and local search methods // In: Chvatal V. (Ed.): Combinatorial Optimization. Methods and Applications. —2011, Amsterdam: IOS Press. —P. 97134.

[60] Kochetov Y., Kononov A., Plyasunov A. Competitive facility location models // Computational Mathematics and Mathematical Physics. — 2009. -V. 49, N.6. -P. 994-1009.

[61] Kolokolov A., Kosarev N. Analysis of decomposition algorithms with Benders cuts for p-median problem //J. Math. Model. Algorithms. -2006. -V. 5, N.2. P. 189-199.

[62] Korte B., Vygen J. Combinatorial Optimization. Theory and Algorithms. Third Edition. —2005, Springer. —588pp.

[63] Kress D., Pesch E. Sequential competitive location on networks // European J. Oper. Res. -2012. -V. 217. -P. 483-499.

[64] Lemaréchal C. Lagrangian Relaxation // In: M. Jünger and D. Naddef (eds.). Computational Combinatorial Optimization. —2001, Heidelberg: Springer Verlag. —P. 115-160.

[65] N. Megiddo, K. Supowit. On the complexity of some common geometric location problems // SIAM J. Comput. -1984. -V. 13, No.l. -P. 182196.

[66] Mladenovic N., Brimberg J., Hansen P., Moreno-Pérez J.A. The p-median problem: a survey of metaheuristic approaches // European J. Oper. Res. -2007. -V. 179. -P. 927-939.

[67] 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.

[68] Plastria F., Vanhaverbeke L. Discrete models for competitive location with foresight // Computers & Operations Research. - 2008. —V.35, No.3. -P. 683-700.

[69] Poljak B.T. Subgradient methods: A Survey of Soviet Research // In: Lemaréchal C. and Mifflin R. (Eds.). Nonsmooth Optimization. IIASA Proceedings Series. —1977. —V. 3. —P. 5-30.

[70] Resende M. G. C., Werncck P. F. A hybrid heuristic for the p-median problem // J. of Heuristics. -2004. -V. 10. -P. 59-88.

[71] Roboredo M.C., Pessoa A.A. A branch-and-cut algorithm for the discrete (r|p)-centroid problem // European J. Oper. Res. —2013. —V. 224, No.l. —P. 101-109.

[72] Schaefer M., Umans C. Completeness in the polynomial-time Hierarchy: Part I: A compendium // ACM Sigact News, Complexity Theory Column. -2002, -V.37, No.33. -P. 32-49.

[73] Sherali H.D., Soyster, A.L. Convergence analysis and algorithmic implications of twodynamic processes toward an oligopoly — competitive fringe equilibrium set // Computers and Operations Research. -1988. -V.15. - P. 69-81.

[74] Shor N.Z. Minimization methods for non-differentiable functions. -1985, Berlin: Springer.

[75] Slater P.I. Maximin facility location // Journal of Research of the National Bureau of Standards. Sect. B. -1975. - V.79. -P. 107-115.

[76] Schrijver A. Combinatorial optimization. Polyhedra and efficiency. -2003, Berlin, Springer. -1881pp.

[77] Spoerhase J. Competitive and voting location. Ph.D. Thesis. —2010, University of Wiirzburg.

[78] Spoerhase J., Wirth H. (r,£>)-centroid problems on paths and trees // J. Theor. Comp. Sci. Archive. -2009. -V. 410. -P. 5128-5137.

[79] Stadler P.F. Corelation in landscapes of combinatorial optimization problems // Europhys. Lett. - 1992. -V. 20. -P. 479-482.

[80] Stadler P.F., Schnabl W. The landscape of the traveling salesman problem // Physics Letters A. -1992. -V. 161. -P. 337-344.

[81] Talbi E-G. Metaheuristics: from design to implementation. —2009, Berlin: Wiley.

[82] Teramoto S., Demanie E.D., Uehara R. The Voroni game on graphs and its complexity // Journal of Graph Algorithms and Applications. -2011. -V.15, No.4. -P. 485-501.