Проблема с расположением объекта - Facility location problem

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

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

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

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

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

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

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

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

В минимакс расположение объекта Задача ищет место, которое минимизирует максимальное расстояние до сайтов, где расстояние от одной точки до сайтов - это расстояние от точки до ближайшего к ней сайта. Формальное определение выглядит следующим образом: для заданного набора точек п ⊂ ℝ^d, найдите набор точек S ⊂ ℝ^d, |S| = k, так что max_п ∈ п(мин._q ∈ S(d (п, q))) сводится к минимуму.

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

Твердость NP

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

Формулировки целочисленного программирования

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

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

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

$${\displaystyle {\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}}}$$

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

Неработоспособное расположение объекта

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

$${\displaystyle {\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}}}$$

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

Еще одна возможность постановки проблемы размещения недееспособного предприятия состоит в следующем: дезагрегировать ограничения мощности (большая-${\displaystyle M}$ ограничения). То есть заменить ограничения

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

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

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

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

Приложения к кластеризации

Определенное подмножество кластерный анализ проблемы можно рассматривать как проблемы с расположением объекта. В задаче кластеризации на основе центроидов цель состоит в разделении ${\displaystyle n}$ точки данных (элементы общего метрического пространства) в классы эквивалентности - часто называемые цвета—Такие точки одного цвета находятся близко друг к другу (то есть, точки разного цвета находятся далеко друг от друга).^[16]

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

Учебник по популярным алгоритмам Разработка алгоритма ^[17] предоставляет соответствующее описание проблемы и приближенный алгоритм. Авторы обращаются к метрической проблеме размещения объекта (т.е. к проблеме кластеризации на основе центроидов или метрической ${\displaystyle k}$-центральная задача) как проблема выбора центра, тем самым увеличивая список синонимов.

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

Расположение медицинского учреждения

Проблемы расположения широко используются при размещении медицинских учреждений. Недавний обзорный документ ^[18] обзоры исследований по этой теме.

Смотрите также

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

Рекомендации

1. Хохбаум, Д.С. (1982). «Эвристика для решения проблемы медианы фиксированной стоимости». Математическое программирование. 22: 148–162. Дои:10.1007 / BF01581035.
2. Guha, S .; Хуллер, С. (1999). «Жадный ответный удар: улучшенные алгоритмы определения местоположения объекта». Журнал алгоритмов. 31: 228–248. CiteSeerX  10.1.1.47.2033. Дои:10.1006 / jagm.1998.0993.
3. Ли, С. (2011). «Алгоритм аппроксимации 1.488 для проблемы размещения неработающих производственных объектов». Автоматы, языки и программирование. LNCS. 6756. С. 77–88. CiteSeerX  10.1.1.225.6387. Дои:10.1007/978-3-642-22012-8_5. ISBN  978-3-642-22011-1.
4. Fowler, R.J .; Патерсон, М. С .; Танимото, С. Л. (1981), "Оптимальная упаковка и покрытие в плоскости являются NP-полными", Письма об обработке информации, 12 (3): 133–137, Дои:10.1016/0020-0190(81)90111-3.
5. Мегиддо, Нимрод; Тамир, Ари (1982), «О сложности размещения линейных объектов на плоскости» (PDF), Письма об исследованиях операций, 1 (5): 194–197, Дои:10.1016/0167-6377(82)90039-6.
6. Гонсалес, Теофило (1985), «Кластеризация для минимизации максимального межкластерного расстояния» (PDF), Теоретическая информатика, 38: 293–306, Дои:10.1016/0304-3975(85)90224-5, заархивировано из оригинал (PDF) на 2013-01-24.
7. Федер, Томас; Грин, Дэниел (1988), «Оптимальные алгоритмы приближенной кластеризации», Материалы двадцатого ежегодного симпозиума ACM по теории вычислений: 434–444, Дои:10.1145/62212.62255, ISBN  0897912640
8. HWang, R. Z .; Lee, R. C. T .; Чанг, Р. С. (1993), "Подход к разделению плиты для решения проблемы евклидова p-центра", Алгоритмика, 9 (1): 1–22, Дои:10.1007 / BF01185335
9. HWang, R. Z .; Chang, R.C .; Ли, Р. К. Т. (1993), "Обобщенная стратегия поиска по разделителям для решения некоторых NP-трудных задач за субэкспоненциальное время", Алгоритмика, 9 (4): 398–423, Дои:10.1007 / bf01228511
10. Бадою, Михай; Хар-Пелед, Сариэль; Индик, Петр (2002), «Примерная кластеризация по core-сетам» (PDF), Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений: 250–257, Дои:10.1145/509907.509947, ISBN  1581134959
11. Кумар, Панкадж; Кумар, Пиюш (2010), «Практически оптимальные решения задач k-кластеризации» (PDF), Международный журнал вычислительной геометрии и приложений, 20 (4): 431–447, Дои:10.1142 / S0218195910003372
12. Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия - Введение. Springer-Verlag. ISBN  978-0-387-96131-6. 1-е издание; 2-е издание, исправленное и расширенное, 1988 г .; Русский перевод, 1989., п. 256
13. Дж. Т. Туссен, «Вычисление самых больших пустых кругов с ограничениями местоположения», Международный журнал компьютерных и информационных наук, т. 12, № 5, октябрь 1983 г., стр. 347–358.
14. Конфорти, Микеле; Корнежоль, Жерар; Замбелли, Джакомо (2014). Целочисленное программирование | SpringerLink. Тексты для выпускников по математике. 271. Дои:10.1007/978-3-319-11008-0. ISBN  978-3-319-11007-3.
15. Теория дискретного размещения. Мирчандани, Питу Б., Фрэнсис, Р. Л. Нью-Йорк: Wiley. 1990 г. ISBN  9780471892335. OCLC  19810449.
16. Хасти, Тревор; Тибширани, Роберт; Фридман, Джером (2009). Элементы статистического обучения (Второе изд.). Springer.
17. Клейнберг, Джон; Тардос, Ева (2006). Разработка алгоритма. Пирсон.
18. Ахмади-Джавид, А .; Seyedi, P .; Сям, С. (2017). «Обследование месторасположения лечебного учреждения». Компьютеры и исследования операций. 79: 223–263. Дои:10.1016 / j.cor.2016.05.018.

внешняя ссылка

• EWGLA Рабочая группа EURO по локационному анализу.
• ИНФОРМАЦИЯ раздел по анализу местоположения, профессиональное общество, занимающееся размещением объекта.
• Библиография по местонахождению объекта собраны Тревор Хейл, содержащий более 3400 статей.
• Библиотека алгоритмов локации
• Веб-утилита для определения местоположения объекта (одно предприятие)
• Оптимизатор местоположения объекта, инструмент на основе MATLAB для решения задач размещения объектов.