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

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

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

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

Задачи о размещении объектов рассматривают ситуации, в которых необходимо спланировать местоположение объектов, предназначенных для обслуживания заданного множества клиентов. Цель обычно заключается в минимизации суммы затрат на открытие объектов и затрат на обслуживание их клиентами с учетом различных ограничений – таких как количество и тип клиентов, которых может обслуживать объект. Существует множество вариантов этой задачи, зависящих от структуры стоимостной функции и ограничений, налагаемых на решение. Первые исследования задачи о размещении объектов выполнили Кюн и Гамбергер [35], Балински и Волф [8], Манн [40] и Балински [7]. Обзорные работы представили Краруп и Прузан [34], а также Мирчандани и Фрэнсис [42]. Любопытно отметить, что одним из самых эффективных алгоритмов решения задачи о размещении объектов без ограничений на пропускную способность является прямо-двойственный алгоритм в сочетании с алгоритмом ветвления и границ, предложенный Эрленкоттером [16] еще в 1978 году. Его прямо-двойственная схема близка к техникам, используемым в современной литературе, посвященной алгоритмам аппроксимации.

В последние годы были проведены масштабные исследования алгоритмов аппроксимации для задач о размещении объектов. Обзорные материалы по этим исследованиям выпустили Шмойс [49, 50] и Вайген [55]. Помимо их теоретической и практической важности, задачи о размещении объектов представляют собой яркую демонстрацию применения широко распространенных техник в области алгоритмов аппроксимации, поскольку многие из этих техник (например, округление LP-алгоритма, прямо-двойственные методы и локальный поиск) успешно применяются к этому семейству задач. Далее будут рассмотрены насколько задач о размещении объектов, выполнен экскурс в историю и перечислены алгоритмы аппроксимации с опорой на результаты, полученные в работе Шмойса, Тардош и Аардал [51]. Техники, применяемые к задаче о размещении объектов без ограничений на пропускную способность (uncapacitated facility location, UFL), будут рассмотрены более подробно.

В задаче UFL заданы множество $\mathcal{F}$ из $n_f$ объектов и множество $\mathcal{C}$ из $n_c$ клиентов (которые также могут называться городами или точками спроса). Каждому объекту $i\in \mathcal{F}$ назначена стоимость открытия объекта $f_i$. Кроме того, для каждого объекта $i\in \mathcal{F}$ и клиента $j\in \mathcal{C}$ задана стоимость соединения $c_{ij}$. Задача заключается в открытии подмножества объектов и соединении каждого клиента с открытым объектом таким образом, чтобы общая стоимость была минимальной. Заметим, что после определения множества открытых объектов оптимальным является соединение каждого клиента с открытым объектом, имеющее минимальную стоимость. Таким образом, задача заключается в нахождении множества $S\subseteq \mathcal{F}$, минимизирующего значение $\sum _{i\in S}{f}_i+\sum _{j\in C}mi{n}_{i\in S}\{c_{ij}\}$. Это определение и определения других вариантов задачи о размещении объектов далее будут предполагать единичный спрос у каждого клиента. Обобщение определений до случая с заданным спросом у каждого отдельного клиента является тривиальным. Задачу UFL можно сформулировать в виде следующей целочисленной программы, предложенной Балински [7]. Пусть $y_i,i\in \mathcal{F},$ равно 1 в случае, если объект открыт, и 0 в противном случае. $Пустьx_{ij},i\in \mathcal{F},j\in \mathcal{C}$, – доля клиента j, назначенная объекту i.

(1) $min\sum _{i\in \mathcal{F}}{f}_i{y}_i+\sum _{i\in \mathcal{F}}\sum _{j\in \mathcal{C}}{c}_{ij}{x}_{ij}$

(2) при условии $\sum _{i\in \mathcal{F}}{x}_{ij}=1$ для всех $j\in \mathcal{C}$,

(3) $x_{ij}-y_i\le 0$ для всех $i\in \mathcal{F},j\in \mathcal{C}$ (3)

(4) $x\ge 0,y\in \{0,1{\}}^{n_f}$

В случае LP-релаксации задачи UFL ограничение $y\in \{0,1{\}}^{n_f}$ заменяется ограничением $y\in [0,1{]}^{n_f}$ . Заметим, что при отсутствии ограничений на пропускную способность нет необходимости в требовании $x_{ij}\in \{0,1\},i\in \mathcal{F},j\in \mathcal{C}$, если каждый клиент должен быть обслужен точно одним объектом, поскольку $0\le x_{ij}\le 1$ согласно ограничениям (2) и (4). Более того, если $x_{ij}$ не является целым, то всегда возможно получить целочисленное решение с той же стоимостью, назначив клиента j полностью одному из объектов, обслуживающих j в настоящее время.

Алгоритм $\gamma$-аппроксимации представляет собой полиномиальный алгоритм, который в задаче минимизации гарантированно дает допустимое решение со значением не более $\gamma z^{\ast }$, где $z^{\ast }$ - значение оптимального решения, а $\gamma \ge 1$. Если $\gamma =1$, алгоритм дает оптимальное решение. В задаче минимизации алгоритм дает решение со значением не менее $\gamma z^{\ast }$, где $0\le \gamma \le 1$.

Хохбаум [25] разработала алгоритм O(log n)-аппроксимации для задачи UFL. Путем прямой редукции задачи о покрытии множества можно показать, что результат не может быть улучшен иначе как в случае $NP\subseteq DTIME[n^{O(loglogn)}]$ в силу результата, полученного Фейге [17]. Однако, если стоимость соединения ограничена в силу некоторых свойств расстояния в метрическом пространстве, а именно $c_{ij}=c_{ji}\ge 0$ для всех $i\in \mathcal{F},j\in \mathcal{C}$ (неотрицательность и симметричность) и $c_{ij}+c_{j{i}^{\prime }}+c_{i^{\prime }{j}^{\prime }}\ge c_{i{j}^{\prime }}$ для всех $i,i^{\prime }\in \mathcal{F},j,j^{\prime }\in \mathcal{C}$ (неравенство треугольника), то можно получить гарантии константной аппроксимации. Во всех упомянутых выше результатах, за исключением задачи максимизации, предполагается, что стоимости удовлетворяют этим ограничениям. Для случая евклидовых расстояний между объектами и клиентами были получены схемы аппроксимации для некоторых задач о размещении объектов [5].

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

Вариант задачи о размещении объектов без ограничений на пропускную способность был получен в результате рассмотрения коэффициентов целевой функции $c_{ij}$ как прибыли в пересчете на элемент, полученной в результате обслуживания клиента j из объекта i. Вариант с максимизацией UFL, названный max-UFL, ориентирован на максимизацию прибыли за вычетом стоимости открытия объекта, т. е. $max\sum _{i\in \mathcal{F}}\sum _{j\in C}{c}_{ij}{x}_{ij}-\sum _{i\in \mathcal{F}}{f}_i{y}_i$. Этот вариант предложили Корнюжо, Фишер и Немхаузер [15].

В задаче о k-медианах стоимость открытия объекта не включается в целевую функцию (1), в результате чего она имеет вид $min\sum _{i\in M}\sum _{j\in N}{c}_{ij}{x}_{ij}$, плюс добавляется ограничение k на количество объектов, которые могут быть открыты, $\sum _{i\in M}{y}_i\le k$. В задаче о k-центрах ограничение $\sum _{i\in M}{y}_i\le k$ учитывается, а целью является минимизация максимального расстояния по соединению между открытым объектом и клиентом.

В задаче с ограничениями на пропускную способность для всех $i\in \mathcal{F}$ добавляется ограничение на пропускную способность $\sum _{j\in C}{x}_{ij}\le u_i{y}_i$. Важно различать случаи с возможностью разделения и с его невозможностью, а также случаи с мягким и жестким ограничением на пропускную способность. В случае с возможностью разделения имеем $x\ge 0$, что позволяет обслуживать клиента при помощи нескольких депо; в случае с невозможностью разделения необходимо выполнение $x\in \{0,1{\}}^{n_f\times b_c}$. Если каждый объект может быть открыт не более одного раза (т. е. $y_i\in \{0,1\}$), ограничения называются жесткими; если в задаче допускается открытие объекта i любое количество r раз для обслуживания $r{u}_i$ клиентов, ограничения называются мягкими.