Оптимальное расположение объекта

Исследование проблем размещения объектов (FLP) , также известное как анализ местоположения , представляет собой отрасль исследования операций и вычислительной геометрии, связанную с оптимальным размещением объектов для минимизации транспортных расходов с учетом таких факторов, как избежание размещения опасных материалов рядом с жилыми домами и действия конкурентов. удобства. Эти методы также применимы к кластерному анализу .

Минимальное расположение объекта

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

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

Задачу размещения объектов на общих графах NP-трудно решить оптимально путем сокращения (например, задачи покрытия множества ) . Для задачи размещения объектов и многих ее вариантов разработан ряд аппроксимирующих алгоритмов.

Без предположений о наборе расстояний между клиентами и площадками (в частности, без предположения, что расстояния удовлетворяют неравенству треугольника ), задача известна как неметрическое расположение объекта и может быть аппроксимирована с точностью до коэффициента O(log n ). Этот коэффициент является точным за счет сохраняющей аппроксимацию редукции из задачи о покрытии множеств.

Если мы предположим, что расстояния между клиентами и объектами ненаправлены и удовлетворяют неравенству треугольника, мы говорим о проблеме метрического местоположения объекта (MFL) . MFL по-прежнему NP-труден, и его трудно аппроксимировать с точностью до коэффициента лучше 1,463. Самый известный в настоящее время алгоритм аппроксимации достигает коэффициента аппроксимации 1,488.

Расположение объекта Минимакс

Задача минимаксного определения местоположения объекта ищет место, которое минимизирует максимальное расстояние до объектов, где расстояние от одной точки до объектов равно расстоянию от точки до ближайшего к нему объекта. Формальное определение выглядит следующим образом:

Учитывая множество точек P ⊂ $\mathbb {R} ^{d}$,найти множество точек S ⊂ $\mathbb {R} ^{d}$, | С | = к , так что max _{p ∈ P} (min _{q ∈ S} (d( p , q )) минимизируется.

В случае евклидовой метрики для k = 1 она известна как проблема наименьшей охватывающей сферы или проблема с 1 центром . Его изучение относится по крайней мере к 1860 году.

Дополнительная информация: Наименьший охватывающий круг и ограничивающая сфера.

Твердость NP

Доказано, что точное решение проблемы k -центров NP-трудно. Было обнаружено, что аппроксимация задачи также является NP-трудной, когда ошибка мала. Уровень ошибки в алгоритме аппроксимации измеряется как коэффициент аппроксимации, который определяется как отношение аппроксимации к оптимуму. Доказано, что аппроксимация задачи k -центров является NP-трудной, когда коэффициент аппроксимации меньше 1,822 (размерность = 2). или 2 (размерность > 2).

Алгоритмы

Точный решатель

Существуют алгоритмы для получения точных решений этой задачи. Один точный решатель работает во времени $n^{O({\sqrt {k}})}$.

1 + ε приближение

Аппроксимация 1 + ε заключается в нахождении решения с коэффициентом аппроксимации не более 1 + ε . Это приближение является NP-трудным, поскольку ε произвольно. один подход, основанный на концепции основного набора , со сложностью выполнения Предлагается $O(2^{O(k\log k/\varepsilon ^{2})}dn)$. В качестве альтернативы доступен другой алгоритм, также основанный на базовых наборах. Он работает в $O(k^{n})$. Автор утверждает, что время работы намного меньше, чем в худшем случае, и поэтому можно решить некоторые проблемы, когда k мало (скажем, k < 5).

Кластеризация в самой дальней точке

Из-за сложности задачи получить точное решение или точное приближение непрактично. широко используется аппроксимация с коэффициентом = 2 Вместо этого для больших случаев k . Это приближение называется алгоритмом кластеризации самой дальней точки (FPC) или обходом самой дальней точки . Алгоритм довольно прост: выберите любую точку множества как один центр; поиск самой дальней точки от остальных, установленной в качестве другого центра; повторяйте процесс, пока не будут найдены k центров.

Легко видеть, что этот алгоритм работает за линейное время. Поскольку аппроксимация с коэффициентом менее 2 оказалась NP-трудной, FPC считался лучшим приближением, которое можно найти.

Что касается производительности выполнения, временная сложность позже улучшается до O( n log k ) с помощью техники коробочной декомпозиции.

Расположение объекта Maxmin

Задача о максимальном минимальном расположении объекта или проблеме неприятного местоположения объекта ищет место, которое максимизирует минимальное расстояние до объектов. В случае евклидовой метрики она известна как проблема наибольшей пустой сферы . Плоский случай ( задача о наибольшем пустом круге ) может быть решен за оптимальное время Θ( n log n).

программирования

Задачи размещения объектов часто решаются с помощью целочисленных программ . В этом контексте проблемы размещения объектов часто ставятся следующим образом: предположим, что имеются $n$ объекты и $m$ клиенты. Мы хотим выбрать (1) какой из $n$ объекты открыть, и (2) какие (открыть) объекты использовать для снабжения $m$ клиентов, чтобы удовлетворить некоторый фиксированный спрос при минимальных затратах. Введем следующие обозначения: пусть $f_{i}$ обозначают (фиксированную) стоимость открытия объекта $i$, для $i=1,\dots ,n$. Позволять $c_{ij}$обозначают стоимость доставки продукта с предприятия $i$ клиенту $j$ для $i=1,\dots ,n$ и $j=1,\dots ,m$. Позволять $d_{j}$ обозначить требование клиента $j$ для $j=1,\dots ,m$. Далее предположим, что каждое предприятие имеет максимальную производительность. Позволять $u_{i}$ обозначают максимальное количество продукции, которое может быть произведено предприятием $i$, то есть пусть $u_{i}$ обозначают мощность объекта $i$. Оставшаяся часть этого раздела следует

Расположение мощного объекта

В нашей первоначальной формулировке введем двоичную переменную $x_{i}$ для $i=1,\dots ,n$, где $x_{i}=1$ если объект $i$ открыт, и $x_{i}=0$ в противном случае. Далее вводим переменную $y_{ij}$ для $i=1,\dots ,n$ и $j=1,\dots ,m$ который представляет собой долю спроса $d_{j}$ заполнено объектом $i$. Тогда так называемая проблема размещения мощного объекта определяется выражением

$${\begin{array}{rl}\min &\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{m}c_{ij}d_{j}y_{ij}+\sum _{i=1}^{n}f_{i}x_{i}\\{\text{s.t.}}&\displaystyle \sum _{i=1}^{n}y_{ij}=1{\text{ for all }}j=1,\dots ,m\\&\displaystyle \sum _{j=1}^{m}d_{j}y_{ij}\leqslant u_{i}x_{i}{\text{ for all }}i=1\dots ,n\\&y_{ij}\geqslant 0{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m\\&x_{i}\in \{0,1\}{\text{ for all }}i=1,\dots ,n\end{array}}$$

Обратите внимание, что второй набор ограничений гарантирует, что если $x_{i}=0$, то есть объект $i$ не открыт, тогда $y_{ij}=0$ для всех $j$, то есть ни один спрос ни на одного клиента не может быть удовлетворен с предприятия. $i$.

Расположение недееспособного объекта

Распространенным случаем описанной выше проблемы размещения мощного объекта является случай, когда $u_{i}=+\infty$ для всех $i=1,\dots ,n$. В этом случае всегда оптимально удовлетворить весь спрос заказчика. $j$ от ближайшего открытого объекта. Поэтому мы можем заменить непрерывные переменные $y_{ij}$ сверху с двоичными переменными $z_{ij}$, где $z_{ij}=1$ если клиент $j$ поставляется предприятием $i$, и $z_{ij}=0$ в противном случае. Тогда задача размещения неиспользуемого объекта определяется выражением

$${\begin{array}{rl}\min &\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{m}c_{ij}d_{j}z_{ij}+\sum _{i=1}^{n}f_{i}x_{i}\\{\text{s.t.}}&\displaystyle \sum _{i=1}^{n}z_{ij}=1{\text{ for all }}j=1,\dots ,m\\&\displaystyle \sum _{j=1}^{m}z_{ij}\leqslant Mx_{i}{\text{ for all }}i=1\dots ,n\\&z_{ij}\in \{0,1\}{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m\\&x_{i}\in \{0,1\}{\text{ for all }}i=1,\dots ,n\end{array}}$$

где $M$ — константа, выбранная достаточно большой. Выбор $M$ может повлиять на результаты вычислений — лучший выбор в этом случае очевиден: взять $M=m$. Тогда, если $x_{i}=1$, любой выбор $z_{ij}$ будет удовлетворять второму набору ограничений.

Другая возможность постановки проблемы размещения немощных предприятий состоит в дезагрегировании ограничений мощности (больших $M$ ограничения). То есть заменить ограничения

$$\sum _{j=1}^{m}z_{ij}\leqslant Mx_{i}{\text{ for all }}i=1,\dots ,n$$

с ограничениями

$$z_{ij}\leqslant x_{i}{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m$$

На практике эта новая формулировка работает значительно лучше, в том смысле, что она имеет более жесткое смягчение линейного программирования , чем первая формулировка. Обратите внимание, что суммирование новых ограничений дает исходную большую величину. $M$ ограничения. В емкостном случае эти формулировки не эквивалентны. Более подробную информацию о проблеме размещения недееспособных объектов можно найти в главе 3 «Теории дискретного размещения».

Приложения

Здравоохранение

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

Управление твердыми отходами

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

Кластеризация

Определенную подгруппу проблем кластерного анализа можно рассматривать как проблемы размещения объектов. В задаче кластеризации на основе центроидов цель состоит в том, чтобы разделить $n$ точки данных (элементы общего метрического пространства) в классы эквивалентности, часто называемые цветами , такие, что точки одного цвета расположены близко друг к другу (эквивалентно, так, что точки разных цветов находятся далеко друг от друга).

Чтобы увидеть, как можно рассматривать (читай «преобразовать» или «уменьшить») проблему кластеризации на основе центроидов как проблему (метрического) местоположения объекта, рассмотрите каждую точку данных в первом случае как точку спроса во втором. Предположим, что данные, подлежащие кластеризации, являются элементами метрического пространства. $M$ (например, пусть $M$ быть $p$-мерное евклидово пространство для некоторых фиксированных $p$). В задаче размещения объектов, которую мы строим, мы допускаем размещение объектов в любой точке этого метрического пространства. $M$; это определяет набор разрешенных мест расположения объектов $L$. Мы определяем затраты $c_{\ell ,d}$ быть попарными расстояниями между парами точек местоположения и спроса (например, см. метрику k-center ). В задаче кластеризации на основе центроидов данные разбиваются на $k$ классы эквивалентности (т.е. цвета), каждый из которых имеет центроид. Давайте посмотрим, как решение нашей проблемы размещения построенных объектов также обеспечивает такое разделение. Допустимое решение - это непустое подмножество $L'\subseteq L$ из $k$ локации. Эти места в нашей задаче о расположении объектов представляют собой набор $k$ центроиды в нашей задаче кластеризации на основе центроидов. Теперь назначьте каждую точку спроса $d$ к месту $\ell ^{*}$ это сводит к минимуму стоимость обслуживания; то есть назначить точку данных $d$ к центроиду $\ell ^{*}:=\mathrm {arg\,min} _{\ell \in L}\{c_{\ell ,d}\}$ (разрыв связей произвольно). Это позволяет добиться разделения при условии, что затраты на решение проблемы размещения объекта $c_{\ell ,d}$ определяются так, что они являются изображениями функции расстояния задачи кластеризации на основе центроидов.

Популярный учебник по алгоритмам Algorithm Design предоставляет соответствующее описание проблемы и алгоритм аппроксимации. Авторы обращаются к проблеме размещения метрических объектов (т.е. проблеме центроидной кластеризации или метрической задаче). $k$-центровая проблема) как проблема выбора центра , тем самым увеличивая список синонимов.

Кроме того, обратите внимание, что в приведенном выше определении проблемы размещения объекта целевая функция $f$ является общим. Конкретный выбор $f$ дают разные варианты проблемы размещения объектов и, следовательно, разные варианты задачи кластеризации на основе центроидов. Например, можно решить минимизировать сумму расстояний от каждого местоположения до каждой из назначенных ему точек спроса (как в задаче Вебера ), или можно выбрать минимизацию максимума всех таких расстояний (как в задаче 1 центра). ).

См. также

• Центр графа
• Задача квадратичного назначения
• Расположение-распределение
• Алгоритм Дейкстры
• Список программного обеспечения для пространственного анализа
• Соревновательная игра по расположению объектов
• Проблема вершинного k-центра
• геометрическая медиана

Внешние ссылки

• Европейская рабочая группа EWGLA по локальному анализу .
• Раздел INFORMS по анализу местоположения , профессиональное сообщество, занимающееся местоположением объектов.
• Библиография о местонахождении объекта , собранная Тревором Хейлом , содержит более 3400 статей.
• Библиотека алгоритмов определения местоположения
• Веб-утилита определения местоположения объекта (один объект)
• Оптимизатор местоположения объекта — инструмент на базе MATLAB для решения задач определения местоположения объекта.