Задача о размещении объектов
Ключевые слова и синонимы
Размещение заводов; размещение складов
Постановка задачи
Задачи о размещении объектов рассматривают ситуации, в которых необходимо спланировать местоположение объектов, предназначенных для обслуживания заданного множества клиентов. Цель обычно заключается в минимизации суммы затрат на открытие объектов и затрат на обслуживание их клиентами с учетом различных ограничений – таких как количество и тип клиентов, которых может обслуживать объект. Существует множество вариантов этой задачи, зависящих от структуры стоимостной функции и ограничений, налагаемых на решение. Первые исследования задачи о размещении объектов выполнили Кюн и Гамбергер [35], Балински и Волф [8], Манн [40] и Балински [7]. Обзорные работы представили Краруп и Прузан [34], а также Мирчандани и Фрэнсис [42]. Любопытно отметить, что одним из самых эффективных алгоритмов решения задачи о размещении объектов без ограничений на пропускную способность является прямо-двойственный алгоритм в сочетании с алгоритмом ветвления и границ, предложенный Эрленкоттером [16] еще в 1978 году. Его прямо-двойственная схема близка к техникам, используемым в современной литературе, посвященной алгоритмам аппроксимации.
В последние годы были проведены масштабные исследования алгоритмов аппроксимации для задач о размещении объектов. Обзорные материалы по этим исследованиям выпустили Шмойс [49, 50] и Вайген [55]. Помимо их теоретической и практической важности, задачи о размещении объектов представляют собой яркую демонстрацию применения широко распространенных техник в области алгоритмов аппроксимации, поскольку многие из этих техник (например, округление LP-алгоритма, прямо-двойственные методы и локальный поиск) успешно применяются к этому семейству задач. Далее будут рассмотрены насколько задач о размещении объектов, выполнен экскурс в историю и перечислены алгоритмы аппроксимации с опорой на результаты, полученные в работе Шмойса, Тардош и Аардал [51]. Техники, применяемые к задаче о размещении объектов без ограничений на пропускную способность (uncapacitated facility location, UFL), будут рассмотрены более подробно.
В задаче UFL заданы множество [math]\displaystyle{ \mathcal{F} }[/math] из [math]\displaystyle{ n_f \; }[/math] объектов и множество [math]\displaystyle{ \mathcal{C} \; }[/math] из [math]\displaystyle{ n_c \; }[/math] клиентов (которые также могут называться городами или точками спроса). Каждому объекту [math]\displaystyle{ i \in \mathcal{F} }[/math] назначена стоимость открытия объекта [math]\displaystyle{ f_i \; }[/math]. Кроме того, для каждого объекта [math]\displaystyle{ i \in \mathcal{F} }[/math] и клиента [math]\displaystyle{ j \in \mathcal{C} }[/math] задана стоимость соединения [math]\displaystyle{ c_{ij} \; }[/math]. Задача заключается в открытии подмножества объектов и соединении каждого клиента с открытым объектом таким образом, чтобы общая стоимость была минимальной. Заметим, что после определения множества открытых объектов оптимальным является соединение каждого клиента с открытым объектом, имеющее минимальную стоимость. Таким образом, задача заключается в нахождении множества [math]\displaystyle{ S \subseteq \mathcal{F} }[/math], минимизирующего значение [math]\displaystyle{ \sum_{i \in S} f_i + \sum_{j \in C} min_{i \in S} \{ c_{ij} \} }[/math]. Это определение и определения других вариантов задачи о размещении объектов далее будут предполагать единичный спрос у каждого клиента. Обобщение определений до случая с заданным спросом у каждого отдельного клиента является тривиальным. Задачу UFL можно сформулировать в виде следующей целочисленной программы, предложенной Балински [7]. Пусть [math]\displaystyle{ y_i, i \in \mathcal{F}, }[/math] равно 1 в случае, если объект открыт, и 0 в противном случае. [math]\displaystyle{ Пусть x_{ij}, i \in \mathcal{F}, j \in \mathcal{C} }[/math], – доля клиента j, назначенная объекту i.
(1) [math]\displaystyle{ min \sum_{i \in \mathcal{F}} f_i y_i + \sum_{i \in \mathcal{F}} \sum_{j \in \mathcal{C}} c_{ij} x_{ij} }[/math]
(2) при условии [math]\displaystyle{ \sum_{i \in \mathcal{F}} x_{ij} = 1 }[/math] для всех [math]\displaystyle{ j \in \mathcal{C} }[/math],
(3) [math]\displaystyle{ x_{ij} - y_i \le 0 }[/math] для всех [math]\displaystyle{ i \in \mathcal{F}, j \in \mathcal{C} }[/math] (3)
(4) [math]\displaystyle{ x \ge 0, y \in \{ 0, 1 \}^{n_f} }[/math]
В случае LP-релаксации задачи UFL ограничение [math]\displaystyle{ y \in \{ 0, 1 \}^{n_f} }[/math] заменяется ограничением [math]\displaystyle{ y \in [0, 1]^{n_f} }[/math] . Заметим, что при отсутствии ограничений на пропускную способность нет необходимости в требовании [math]\displaystyle{ x_{ij} \in \{0, 1 \}, i \in \mathcal{F}, j \in \mathcal{C} }[/math], если каждый клиент должен быть обслужен точно одним объектом, поскольку [math]\displaystyle{ 0 \le x_{ij} \le 1 \; }[/math] согласно ограничениям (2) и (4). Более того, если [math]\displaystyle{ x_{ij} \; }[/math] не является целым, то всегда возможно получить целочисленное решение с той же стоимостью, назначив клиента j полностью одному из объектов, обслуживающих j в настоящее время.
Алгоритм [math]\displaystyle{ \gamma \; }[/math]-аппроксимации представляет собой полиномиальный алгоритм, который в задаче минимизации гарантированно дает допустимое решение со значением не более [math]\displaystyle{ \gamma \; z^* }[/math], где [math]\displaystyle{ z^* \; }[/math] - значение оптимального решения, а [math]\displaystyle{ \gamma \ge 1 \; }[/math]. Если [math]\displaystyle{ \gamma = 1 \; }[/math], алгоритм дает оптимальное решение. В задаче минимизации алгоритм дает решение со значением не менее [math]\displaystyle{ \gamma \; z^* }[/math], где [math]\displaystyle{ 0 \le \gamma \le 1 \; }[/math].
Хохбаум [25] разработала алгоритм O(log n)-аппроксимации для задачи UFL. Путем прямой редукции задачи о покрытии множества можно показать, что результат не может быть улучшен иначе как в случае [math]\displaystyle{ NP \subseteq DTIME[n^{O(log \; log \; n)}] }[/math] в силу результата, полученного Фейге [17]. Однако, если стоимость соединения ограничена в силу некоторых свойств расстояния в метрическом пространстве, а именно [math]\displaystyle{ c_{ij} = c_{ji} \ge 0 \; }[/math] для всех [math]\displaystyle{ i \in \mathcal{F}, j \in \mathcal{C} }[/math] (неотрицательность и симметричность) и [math]\displaystyle{ c_{ij} + c_{ji'} + c_{i'j'} \ge c_{i j'} \; }[/math] для всех [math]\displaystyle{ i, i' \in \mathcal{F}, j, j' \in \mathcal{C} }[/math] (неравенство треугольника), то можно получить гарантии константной аппроксимации. Во всех упомянутых выше результатах, за исключением задачи максимизации, предполагается, что стоимости удовлетворяют этим ограничениям. Для случая евклидовых расстояний между объектами и клиентами были получены схемы аппроксимации для некоторых задач о размещении объектов [5].
Варианты и родственные задачи
Вариант задачи о размещении объектов без ограничений на пропускную способность был получен в результате рассмотрения коэффициентов целевой функции [math]\displaystyle{ c_{ij} \; }[/math] как прибыли в пересчете на элемент, полученной в результате обслуживания клиента j из объекта i. Вариант с максимизацией UFL, названный max-UFL, ориентирован на максимизацию прибыли за вычетом стоимости открытия объекта, т. е. [math]\displaystyle{ max \sum_{i \in \mathcal{F}} \sum_{j \in C} c_{ij} x_{ij} - \sum_{i \in \mathcal{F}} f_i y_i }[/math]. Этот вариант предложили Корнюжо, Фишер и Немхаузер [15].
В задаче о k-медианах стоимость открытия объекта не включается в целевую функцию (1), в результате чего она имеет вид [math]\displaystyle{ min \sum_{i \in M} \sum_{j \in N} c_{ij} x_{ij} }[/math], плюс добавляется ограничение k на количество объектов, которые могут быть открыты, [math]\displaystyle{ \sum_{i \in M} y_i \le k }[/math]. В задаче о k-центрах ограничение [math]\displaystyle{ \sum_{i \in M} y_i \le k }[/math] учитывается, а целью является минимизация максимального расстояния по соединению между открытым объектом и клиентом.
В задаче с ограничениями на пропускную способность для всех [math]\displaystyle{ i \in \mathcal{F} }[/math] добавляется ограничение на пропускную способность [math]\displaystyle{ \sum_{j \in C} x_{ij} \le u_i y_i }[/math]. Важно различать случаи с возможностью разделения и с его невозможностью, а также случаи с мягким и жестким ограничением на пропускную способность. В случае с возможностью разделения имеем [math]\displaystyle{ x \ge 0 \; }[/math], что позволяет обслуживать клиента при помощи нескольких депо; в случае с невозможностью разделения необходимо выполнение [math]\displaystyle{ x \in \{ 0, 1 \}^{n_f \times b_c} }[/math]. Если каждый объект может быть открыт не более одного раза (т. е. [math]\displaystyle{ y_i \in \{ 0, 1 \} \; }[/math]), ограничения называются жесткими; если в задаче допускается открытие объекта i любое количество r раз для обслуживания [math]\displaystyle{ ru_i \; }[/math] клиентов, ограничения называются мягкими.
В k-уровневой задаче о размещении объектов заданы следующие начальные данные: множество клиентов C, k непересекающихся множеств [math]\displaystyle{ \mathcal{F}_1, ..., \mathcal{F}_k }[/math] объектов, стоимость открытия каждого объекта и стоимость соединения клиентов и объектов. Задача заключается в соединении каждого клиента j по пути, состоящему из открытых объектов [math]\displaystyle{ i_1, ... , i_k \; }[/math], где [math]\displaystyle{ i_{\ell} = \mathcal{F}_{\ell} }[/math]. Стоимость соединения для этого объекта имеет вид [math]\displaystyle{ c_{ji_1} + c_{i_1 i_2} + ... + c_{i_{k - 1}i_k} \; }[/math]. Задача заключается в минимизации суммы стоимостей соединений и стоимостей открытия объектов.
Все вышеупомянутые задачи были рассмотрены в работе Шмойса, Тардош и Аардал [15] за исключением задач max-UFL, о k-центрах и k-медианах. Вариант max-UFL был добавлен по историческим причинам, а задачи о k-центрах и k-медианах включены в силу их богатой истории и близкого родства с задачей UFL. Результаты для задачи о размещении объектов с жесткими ограничениями на пропускную способность упомянуты, поскольку, по крайней мере с точки зрения приложения, эта модель более реалистична по сравнению с версией с мягкими ограничениями, рассмотренной в [51]. Для k-уровневой задачи о размещении объектов Шмойс и др. рассматривали случай k = 2. Здесь рассматривается задача для k общего вида.
Также существуют различные варианты задачи о размещении объектов, не упоминавшиеся выше. Можно привести такие примеры задач, как размещение объектов с ограничением числом K [33], универсальное размещение объектов [24, 38], размещение объектов в онлайновом режиме [3, 18, 41], отказоустойчивое размещение объектов [28, 30, 54], размещение объектов при наличии выбросов [12, 28], размещение объектов для нескольких товарных потоков [48], размещение объектов с приоритетами [37, 48], размещение объектов с иерархической стоимостью объектов [52], стохастическое размещение объектов [23, 37, 46], размещение объектов с подключением [53], размещение объектов с балансировкой нагрузки [22, 32, 37], размещение объектов с вогнутой функций затрат [24], размещение объектов с ограничением на количество кабелей [37, 47].
Основные результаты
Для решения задач о размещении объектов было предложено множество алгоритмов. Вначале будет приведено краткое описание алгоритмов Шмойса, Тардош и Аардал [51]. Затем будет представлен сжатый обзор основных результатов. Некоторые алгоритмы, дающие наилучшие значения гарантии аппроксимации [math]\displaystyle{ \gamma \; }[/math], основаны на решении задачи LP-релаксации при помощи полиномиального алгоритма, что может потребовать значительного времени; в то же время некоторые авторы предложили быстрые комбинаторные алгоритмы для задач о размещении объектов с менее привлекательными значениями гарантии [math]\displaystyle{ \gamma \; }[/math]. В свете ограничений на объем занимаемой памяти более эффективно уделять внимание алгоритмам, обеспечивающим наилучшие значения гарантии аппроксимации. Дополнительные ссылки можно найти в обзорных статьях Шмойса [49,50] и Вайгена [55].
Алгоритмы Шмойса, Тардош и Аардал
Вначале будет представлен алгоритм решения задачи UFL, а затем перечислены результаты, которые могут быть получены за счет адаптации алгоритма к другим задачам.
Алгоритм выполняет LP-релаксацию, а затем в два этапа модифицирует полученное дробное решение. Первый этап, называемый фильтрацией, предназначен для ограничения стоимости соединения каждого клиента с самым удаленным объектом, частично обслуживающим его. Для этого переменные [math]\displaystyle{ y_i \; }[/math], обозначающие стоимость открытия объектов, пропорционально увеличиваются на константную величину, а затем переменные [math]\displaystyle{ x_{ij} \; }[/math], обозначающие стоимость соединения, корректируются для использования ближайших возможных объектов.
Для второго этапа используется понятие кластеризации, позднее формализованное Чудаком и Шмойсом [13]. Основываясь на дробном решении, экземпляр разбивается на фрагменты, называемые кластерами. У каждого кластера имеется отдельный клиент, называемый центром кластера. Это производится путем итеративного выбора клиента, не охваченного предыдущими кластерами, в качестве центра кластера, и добавления к этому кластеру объектов, обслуживающих этого клиента в дробном решении, а также других клиентов, обслуживаемых этими объектами. Такое построение кластеров гарантирует, что объекты в каждом кластере открыты для количества клиентов, в сумме равного единице и, следовательно, после открытия объекта с наименьшей возможной стоимостью в каждом кластере суммарная уплаченная стоимость открытия объекта не превышает стоимость открытия объекта у дробного решения. Более того, выбирая клиентов в качестве центров кластеров жадным образом, алгоритм добивается того, чтобы каждый центр кластера минимизировал определенную стоимостную функцию для клиентов кластера. Оставшиеся клиента кластера также соединяются с открытым объектом. Для ограничения стоимости этого соединения используется неравенство треугольника для стоимостей соединений. Для задачи UFL этот алгоритм фильтрации и округления представляет собой алгоритм 4-аппроксимации, Шмойс и др. Также показали, что в случае замены этапа фильтрации рандомизированной фильтрацией можно получить гарантию аппроксимации 3,16.
В той же статье была выполнена адаптация алгоритма, с применением рандомизированной фильтрации и без нее, с целью получения алгоритмов аппроксимации для задачи о размещении объектов с мягкими ограничениями на пропускную способность, а также для двухуровневой задачи о размещении объектов без ограничений на пропускную способность. Далее будут обсуждаться результаты работы алгоритма с применением рандомизированной фильтрации.
Были рассмотрены два варианта задачи о размещении объектов с мягкими ограничениями на пропускную способность. Оба предполагают равную пропускную способность, т. е. [math]\displaystyle{ u_i = u \; }[/math] для всех [math]\displaystyle{ i \in \mathcal{F} }[/math]. В первом варианте решение является «допустимым», если y-переменные либо принимают значение 0, либо имеют значение между 1 и [math]\displaystyle{ \gamma' \ge 1 \; }[/math]. Заметим, что [math]\displaystyle{ \gamma' \; }[/math] не обязательно должно быть целым, так что построенное решение не обязательно является целочисленным. Это можно интерпретировать так, что каждому объекту i дозволяется расширяться, обеспечивая пропускную способность [math]\displaystyle{ \gamma' u \; }[/math] со стоимостью [math]\displaystyle{ \gamma' f_i \; }[/math]. Алгоритм [math]\displaystyle{ (\gamma, \gamma') \; }[/math]-аппроксимации представляет собой полиномиальный алгоритм, приводящий к такому допустимому решению, общая стоимость которого не более чем в [math]\displaystyle{ \gamma \; }[/math] раз превышает истинную оптимальную стоимость, имеющую место в случае [math]\displaystyle{ y \in \{0, 1 \}^{n_f} \; }[/math]. Шмойс и др. разработали алгоритм (5,69< 4,24)-аппроксимации для варианта этой задачи с возможностью разделения и алгоритм (7,62< 4,29)-аппроксимации для варианта без возможности разделения.
Во второй модели о размещении объектов с мягкими ограничениями на пропускную способность задача меняется таким образом, чтобы y-переменные могли принимать неотрицательные целочисленные значения, благодаря чему можно открывать несколько объектов с пропускной способностью u в каждом местоположении. Алгоритмы аппроксимации в данном случае дают решение, являющееся допустимым в рамках данной модифицированной модели. Легко показать, что гарантии аппроксимации, полученные для предыдущей модели, выполняются и в данном случае – речь идет о полученных Шмойсом алгоритмах 5,69-аппроксимации для варианта с возможностью разделения спроса и 7,62-аппроксимации для варианта без возможности разделения спроса. Последняя модель чаще всего рассматривается в более современных работах, поэтому именно на нее будут ссылаться авторы в параграфе, посвященном размещению объектов с мягкими ограничениями на пропускную способность.
UFL
Первым алгоритмом с константной гарантией эффективности стал алгоритм аппроксимации с коэффициентом 3,16, разработанный Шмойсом, Тардош и Аардал (см. выше). С тех пор в него были внесены значительные улучшения. Гуха и Хуллер [19, 20] доказали, что нижняя граница аппроксимации составляет 1,463, и предложили жадную процедуру пополнения. Затем была разработана серия алгоритмов аппроксимации на базе LP-округления (см., например, [10, 13]). Существуют также жадные алгоритмы, использующие LP-релаксацию только неявно, для получения нижней границы при анализе прямо-двойственного подхода. В качестве примера можно привести алгоритм аппроксимации JMS с коэффициентом аппроксимации 1,61, разработанный Джейном, Мадьяном и Сабери [29]. Некоторые алгоритмы сочетают несколько разных техник – например, алгоритм аппроксимации Мадьяна, Йе и Чжана [39] с коэффициентом 1,52, использующий алгоритм JMS и жадную процедуру пополнения. Лучшую известную на сегодня гарантию аппроксимации (1,5) получил Бурка [ ]. Она достигается путем сочетания рандомизированного алгоритма LP-округления с жадным алгоритмом JMS.
max-UFL
Первый алгоритм с константным коэффициентом аппроксимации в 1977 году разработали Корнюжо и др. [15] для задачи max-UFL. Они показали, что при открытии одного объекта за раз жадным образом, выбирая для открытия объект с самой высокой маржинальной прибылью, до тех пор, пока не останется объектов с положительной маржинальной прибылью, алгоритм имеет коэффициент аппроксимации (1 — 1/e) & 0,632. Лучший известный на сегодня коэффициент аппроксимации (0,828) получили Агеев и Свириденко [2].
k-медианы, k-центры
Первый алгоритм с константным коэффициентом аппроксимации для задачи о k-медианах был разработан Чарикаром, Гухой, Тардош и Шмойсом [11]. Этот алгоритм LP-округления имеет коэффициент аппроксимации б|. Лучший известный на сегодня коэффициент аппроксимации, 3 + e, при помощи эвристики локального поиска получили Арья и др. [6] (см. также отдельные разделы для метода k-медиан и задачи о размещении объектов).
Первый алгоритм с константным коэффициентом аппроксимации (равным 2) для задачи о k-центрах разработали Хохбаум и Шмойс [26]. Эта гарантия эффективности является наилучшей за исключением случая P = NP.
Задача о размещении объектов с ограничениями на пропускную способность
Для задачи о размещении объектов с мягкими ограничениями, в которой пропускная способность всех объектов равна, первые алгоритмы аппроксимации с константным коэффициентом разработали Шмойс и др. [51] для обоих вариантов – с возможностью разделения спроса и без таковой возможности (см. выше). Недавно был предложен алгоритм аппроксимации с коэффициентом 2 для решения задачи о размещении объектов с ограничениями на пропускную способность с единичным спросом без возможности разделения, разработанный Мадьяном и др. [39]. Разрыв целостности LP-релаксации для этой задачи также равен 2. Следовательно, для улучшения гарантии аппроксимации необходимо получить улучшенную нижнюю границу в оптимальном решении.
В варианте с жесткими ограничениями на пропускную способность важно разрешить разделение спроса, поскольку в противном случае даже задача существования становится слишком сложной. В случае возможности разделения спроса можно различать случаи с равными значениями пропускной способности, в которых u i = u для всех i 2 F, и общий случай. Для задачи с равными значениями пропускной способности Чудак и Уильямсон получили алгоритм аппроксимации с коэффициентом 5,83 [14]. Первый алгоритм с константным коэффициентом аппроксимации, у = 8:53 + e, для задачи разработали Пал, Тардош и Уэкслер [ ]. Позднее Чжан, Чен и Йе улучшили его, получив коэффициент 5,83 для задачи со значениями пропускной способности общего вида.
k-уровневая задача
Первый алгоритм с константным коэффициентом аппроксимации для k = 2 разработали Шмойс и др. [ ], получив у = 3,16. Для k общего вида первый алгоритм с у = 3, предложиди Аардал, Чудак и Шмойс [ ]. Для случая k = 2 Чжан [56] разработал алгоритм с коэффициентом апроксимации 1,77. Он также показал, что для k = 3 и k = 4 задачу можно аппроксимировать в при у = 2,523 1 и у = 2,81, соответственно.
1 Это значение у слегка отличается от значения 2,51, приведенного в статье. Исходное рассуждение содержало небольшую ошибку в расчетах.
Применение
Задача о размещении объектов широко применяется в области исследования операций. В книге под редакцией Мирчандани и Фрэнсиса [42], а также в книге Немхаузера и Уолси [43] можно найти обзоры и описание способов применения алгоритмов размещения объектов в таких задачах, как размещение заводов и локализации банковских счетов. Недавно эти алгоритмы также нашли применение в таких задачах проектирования сетей, как размещение маршрутизаторов и кэш-памяти [22, 36], агломерация трафика или данных [4, 21], а также репликация веб-серверов в сети распространения контента [31, 45].