Автоматика и телемеханика, № 4, 2014
© 2014 г. И.А. ДАВЫДОВ, Ю.А. КОЧЕТОВ, д-р физ.-мат. наук (Новосибирский государственный университет, Институт математики СО РАН, Новосибирск), Н. МЛАДЕНОВИЧ, профессор, Д. УРОСЕВИЧ, профессор (Институт математики Сербской академии наук и искусств, Белград)
БЫСТРЫЕ МЕТАЭВРИСТИКИ ДЛЯ ДИСКРЕТНОЙ ЗАДАЧИ О (r|p)-ЦЕНТРОИДЕ1
Два игрока, лидер и его конкурент, открывают предприятия, стараясь захватить как можно большую долю рынка. Лидер открывает р предприятий. Затем конкурент открывает г предприятий. Каждый клиент выбирает ближайшее предприятие в качестве поставщика. Требуется так выбрать р предприятий лидера, чтобы максимизировать его долю рынка. Эта задача может быть представлена в виде задачи двухуровневого программирования. Опираясь на это представление, в работе предлагаются два численных метода: локальный поиск с чередующимися окрестностями и стохастический поиск с запретами. Основное внимание уделяется сокращению трудоемкости методов без ущерба качеству получаемых решений. Результаты численных экспериментов подтверждают возможность быстрого нахождения точного решения задачи и решений с малой погрешностью.
1. Введение
Задачи размещения предприятий составляют широкий пласт математических моделей исследования операций. Это богатая тема как для теоретических и экспериментальных исследований, так и для приложений, возникающих при размещении предприятий и складов, полицейских участков и служб пожарной безопасности, станций скорой помощи, создании беспроводных сетей связи и др. [1]. В большинстве таких моделей одно лицо принимает решение, стремясь максимизировать получаемую прибыль или минимизировать суммарные затраты на обслуживание клиентов. В настоящей работе рассматривается более сложная ситуация, когда два лица (игрока) последовательно принимают решения о размещении предприятий. Эта область конкурентных задач размещения. Она обязана своим рождением пионерской работе Хотте-линга [2]. В ней исследуются эгоистические стратегии поведения двух игроков в предположении, что клиенты располагаются на линии (шоссе, береговая линия и т.п.) Позже появились более богатые модели, интересные как, с точки
1 Работа первых двух авторов выполнена в Новосибирском госуниверситете при финансовой поддержке Министерства образования и науки РФ (договор № 02.G25.31.0054).
зрения экономики и теории игр, так и для методов оптимизации и исследования операций. С обзором таких моделей и результатов их исследования можно познакомиться, например, в [3, 4] (см. также [5]).
Одну из таких задач, задачу о центроиде, впервые исследовал Хакими [3]. Рассмотрим конечное множество I возможных мест размещения предприятий и конечное множество ■ мест расположения клиентов. Матрица (й^), г € I, ] € ■, задает расстояние от клиентов до предприятий. Величина Wj определяет доход игрока при обслуживании клиента ]. Игроки последовательно принимают решения об открытии предприятий, стремясь максимизировать свой доход. Сначала на рынок выходит первый игрок (лидер) и открывает р предприятий. Зная это решение, второй игрок (конкурент) открывает свои г предприятий. Каждый клиент из открытых р + г предприятий выбирает ближайшее к нему предприятие в качестве своего поставщика. В итоге множество клиентов делится на две части: клиенты лидера и клиенты конкурента. Задача состоит в том, чтобы найти р предприятий лидера, которые дают ему максимальный доход (долю рынка) при наиболее сильном ответном ходе конкурента. На сегодняшний день основные исследования задачи разделились на три направления:
- дискретная задача, когда множества клиентов и предприятий конечны [6-8];
- задача на сети, когда клиенты размещаются в вершинах графа, а предприятия можно открывать в любых точках на ребрах [9, 10];
- задача в евклидовом пространстве, когда клиенты представлены конечным множеством точек, а предприятия могут размещаться в произвольных точках или в заданной ограниченной области [11].
Выделяют еще случай, когда множество клиентов не является конечным, а задается некоторой областью на плоскости с заданной плотностью распределения, но в данной работе он рассматриваться не будет.
Известно [12], что задача о центроиде в каждом из указанных трех случаев является -трудной, а задача конкурента при заданном решении лидера — КР-трудной в сильном смысле, даже если матрица (й^) задает евклидовы расстояния на плоскости. Далее будем рассматривать только дискретную задачу, когда множества I и ■ конечны и совпадают друг с другом.
Несмотря на высокий сложностной статус задачи, для ее решения разработаны точные и приближенные методы, опирающиеся на ее комбинаторную природу. Методы неявного перебора [13], метод ветвей и отсечений [14], а также итерационный метод, основанный на последовательном наращивании семейства решений конкурента [6], гарантируют нахождение глобального оптимума, но требуют больших вычислительных затрат уже при |11 = |■ | = 100, р = г ^ 10. Эвристики, основанные на решениях задачи о р-медиане, генетические алгоритмы, алгоритмы роя частиц и алгоритмы локального поиска показали высокую точность при сравнительно малом числе итераций [7], но трудоемкость каждой итерации все-таки остается достаточно высокой. Это обстоятельство связано, в первую очередь, с тем, что вычисление целевой функции лидера требует точного решения задачи конкурента. Так как эта задача является КР-трудной в сильном смысле, а решать ее приходится мно-
гократно, то высокая трудоемкость представляется неизбежной. В [15] для сокращения трудоемкости применяются жадные алгоритмы для задачи конкурента. В [16] для этих целей использовались лагранжевы релаксации. В [6] ослаблялись условия целочисленности переменных и задача конкурента формулировалась как задача линейного программирования. Получаемая верхняя оценка на доход конкурента использовалась при локальной перестройке решений лидера. В [17] алгоритм роя частиц применялся вместо линейного программирования для решения задачи конкурента.
В настоящей работе предпринята попытка дальнейшего сокращения трудоемкости методов локального поиска. Исследуются две схемы: локальный поиск с чередующимися окрестностями (Variable Neighborhood Search, VNS) и стохастический локальный поиск с запретами (Stochastic Tabu Search, STS). Основная идея состоит в адаптации этих хорошо зарекомендовавших себя схем к рассматриваемой задаче двухуровневого программирования. В обеих схемах используется окрестность Swap для переменных лидера. Ускорение локального поиска достигается за счет деления этой окрестности на три части. Две из них являются наиболее перспективными и просматриваются в первую очередь. Их малая мощность позволяет быстро найти направление подъема и сократить трудоемкость одной итерации. Для решения задачи конкурента применяются точные методы или линейное программирование и метаэвристики, что также приводит к сокращению трудоемкости. Наконец, рандомизация локального поиска применяется в обоих методах для диверсификации поиска. В результате получены эффективные методы решения задачи о центроиде, позволяющие на порядок быстрее находить точные решения при p = r ^ 15 и впервые получить решения для p = r = 25 и p = r = 30, чего раньше сделать не удавалось из-за высоких вычислительных затрат. Более того, для p = r = 30 эти методы работают в среднем быстрее, чем для p = r = 15.
Статья организована следующим образом. В разделе 2 приводится точная математическая постановка задачи. В разделе 3 представлен метод с чередующимися окрестностями. В разделе 4 описывается стохастический метод поиска с запретами. В разделе 5 приводятся результаты численных экспериментов на примерах из электронной библиотеки Дискретные задачи размещения (http://math.nsc.ru/AP/benchmarks/). Результаты этих экспериментов показывают, что оба метода быстро находят известные оптимальные решения, а на тестовых примерах, где оптимум неизвестен, их решения мало отличаются друг от друга.
2. Постановка задачи
Обозначим через X множество предприятий, открываемых лидером, а через У — множество предприятий конкурента. Расстояние между клиентом 0 и ближайшим предприятием лидера обозначим через ). Аналогично,
((0, У) — расстояние до ближайшего предприятие конкурента. Будем говорить, что клиент 0 предпочитает У, если (1(0, У) < (1(0, X), и предпочитает X в противном случае. Через 3(У — X) обозначим множество клиентов, пред-
почитающих Y, т.е.
J(Y x X) = {j e J | d(j, Y) <d(j,X)}.
Тогда доход конкурента W (Y x X) определяется как сумма доходов от его клиентов:
W (Y x X )= £ wj.
jeJ (Y <X)
При заданном решении X, конкурент стремится максимизировать свой доход. Значение этого дохода W*(X) определяется как решение следующей задачи:
W*(X) = max W (Y x X).
Y,|Y |=r
Будем называть ее задачей конкурента или задачей о медианоиде [3]. Лидер стремится максимизировать собственный доход или, что то же самое, минимизировать доход конкурента. Минимальное значение W*(X*) потерь лидера определяется из решения следующей задачи:
W *(X *) = min W *(X).
X,|X|=p
Наилучшее решение лидера X* определяет его доход ^j€jWj — W*(X*). В задаче о (г|р)-центроиде требуется найти X* и W*(X*).
Представим эту минимаксную задачу в терминах двухуровневого целочисленного программирования. Введем переменные
J 1, если лидер открывает предприятие i, г 1 0 в противном случае,
J 1, если конкурент открывает предприятие i, Уг 1 0 в противном случае,
1, если клиент j обслуживается из предприятия лидера, 0, если клиент j обслуживается из предприятия конкурента.
Тогда X = {i e I|жг = 1}, Y = {i e I|уг = 1}. Для каждого клиента j определим множество предприятий Ij (X), позволяющее конкуренту "захватить" клиента j, т.е.
Ij (X) = |i e I dij < niin{d1j = 1}
Заметим, что в случае равных расстояний до предприятий лидера и конкурента клиент отдает предпочтение лидеру [3]. С использованием введенных обозначений задача о (г|р)-центроиде может быть представлена следующим образом [6, 8]:
max^ Wj z*(X), Х jeJ
^жг = p, ге/
жг e {0,1}, i e I,
где z*(X),y*(X) — оптимальное решение задачи конкурента:
шахУ" (1 - ^),
^
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.