Задача о размещении объектов

Ключевые слова и синонимы

Размещение заводов; размещение складов

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

Задачи о размещении объектов рассматривают ситуации, в которых необходимо спланировать местоположение объектов, предназначенных для обслуживания заданного множества клиентов. Цель обычно заключается в минимизации суммы затрат на открытие объектов и затрат на обслуживание их клиентами с учетом различных ограничений – таких как количество и тип клиентов, которых может обслуживать объект. Существует множество вариантов этой задачи, зависящих от структуры стоимостной функции и ограничений, налагаемых на решение. Первые исследования задачи о размещении объектов выполнили Кюн и Гамбергер [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].

Варианты и родственные задачи