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

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

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

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

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

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

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

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

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

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

Для заданного множества точек P ⊂ ${\displaystyle \mathbb {R} ^{d}}$ найдите множество точек S ⊂ , | S | = k , ${\displaystyle \mathbb {R} ^{d}}$ так, чтобы max _{p ∈ P} (min _{q ∈ S} (d( p , q )) было минимальным.

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

твердость НП

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

Задачи размещения объектов часто решаются как целочисленные программы . В этом контексте задачи размещения объектов часто ставятся следующим образом: предположим, что есть объекты и клиенты. Мы хотим выбрать (1) какой из объектов открыть, и (2) какие (открытые) объекты использовать для поставок клиентам, чтобы удовлетворить некоторый фиксированный спрос с минимальными затратами. Мы вводим следующие обозначения: пусть обозначим (фиксированную) стоимость открытия объекта , для . Пусть обозначим стоимость доставки продукта с объекта клиенту для и . Пусть обозначим спрос клиента на . Далее предположим, что каждый объект имеет максимальный выпуск. Пусть обозначим максимальный объем продукта, который может быть произведен объектом , то есть пусть обозначим мощность объекта . Оставшаяся часть этого раздела следует ^[14] ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\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}$

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

В нашей первоначальной формулировке введем бинарную переменную для , где если объект открыт, и в противном случае. Далее введем переменную для и , которая представляет собой долю спроса, удовлетворенную объектом . Так называемая задача размещения объекта с емкостью затем задается как ${\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}}$

Другая возможность формулировки для проблемы размещения необеспеченных мощностей заключается в разукрупнении ограничений по мощности (больших ограничений). То есть, замене ограничений на ограничения На практике эта новая формулировка работает значительно лучше, в том смысле, что она имеет более жесткую релаксацию линейного программирования, чем первая формулировка. ^[14] Обратите внимание, что суммирование новых ограничений вместе дает исходные большие ограничения. В случае с обеспеченными мощностями эти формулировки не эквивалентны. Более подробную информацию о проблеме размещения необеспеченных мощностей можно найти в Главе 3 «Теории дискретного размещения». ^[15] ${\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}$$ ${\displaystyle M}$

Приложения

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

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

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

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

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

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

Чтобы увидеть, как можно рассматривать (читать «преобразовывать» или «редуцировать») задачу кластеризации на основе центроида как (метрическую) задачу размещения объектов, рассмотрим каждую точку данных в первой как точку спроса во второй. Предположим, что данные, которые должны быть кластеризованы, являются элементами метрического пространства (например, пусть будет -мерным евклидовым пространством для некоторого фиксированного ). В задаче размещения объектов, которую мы строим, мы разрешаем размещать объекты в любой точке внутри этого метрического пространства ; это определяет набор разрешенных местоположений объектов . Мы определяем затраты как попарные расстояния между парами местоположение-точка спроса (например, см. метрический k-центр ). В задаче кластеризации на основе центроида данные разбиваются на классы эквивалентности (т. е. цвета), каждый из которых имеет центроид. Давайте посмотрим, как решение нашей построенной задачи размещения объектов также достигает такого разбиения. Допустимое решение — это непустое подмножество местоположений . Эти местоположения в нашей задаче размещения объектов включают набор центроидов в нашей задаче кластеризации на основе центроида. Теперь назначьте каждую точку спроса местоположению , которое минимизирует ее стоимость обслуживания; то есть назначьте точку данных центроиду (разрывайте связи произвольно). Это обеспечивает разбиение при условии, что затраты задачи размещения объектов определены таким образом, что они являются изображениями функции расстояния задачи кластеризации на основе центроида. ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle M}$ ${\displaystyle L}$ ${\displaystyle c_{\ell ,d}}$ ${\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}}$

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

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

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

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

Ссылки

1. Хохбаум, Д.С. (1982). «Эвристика для задачи медианы с фиксированной стоимостью». Математическое программирование . 22 : 148–162. doi :10.1007/BF01581035. S2CID  3451944.
2. Гуха, С.; Хуллер, С. (1999). «Жадность наносит ответный удар: улучшенные алгоритмы определения местоположения объектов». Журнал алгоритмов . 31 : 228–248. CiteSeerX 10.1.1.47.2033 . doi : 10.1006/jagm.1998.0993. S2CID  5363214. 
3. Ли, С. (2011). «Алгоритм приближения 1,488 для задачи определения местоположения неиспользуемых объектов». Автоматы, языки и программирование . LNCS . Т. 6756. С. 77–88. CiteSeerX 10.1.1.225.6387 . doi :10.1007/978-3-642-22012-8_5. ISBN  978-3-642-22011-1.
4. Фаулер, Р. Дж.; Патерсон, М. С.; Танимото, С. Л. (1981), «Оптимальная упаковка и покрытие на плоскости являются NP-полными», Information Processing Letters , 12 (3): 133–137, doi :10.1016/0020-0190(81)90111-3.
5. Мегиддо, Нимрод ; Тамир, Ари (1982), «О сложности размещения линейных объектов на плоскости» (PDF) , Operations Research Letters , 1 (5): 194–197, doi :10.1016/0167-6377(82)90039-6.
6. Гонсалес, Теофило (1985), «Кластеризация для минимизации максимального межкластерного расстояния», Теоретическая информатика , 38 : 293–306, doi : 10.1016/0304-3975(85)90224-5.
7. Федер, Томас; Грин, Дэниел (1988), «Оптимальные алгоритмы для приблизительной кластеризации», Труды двадцатого ежегодного симпозиума ACM по теории вычислений - STOC '88, стр. 434–444, doi :10.1145/62212.62255, ISBN 0897912640, S2CID  658151
8. HWang, RZ; Lee, RCT; Chang, RC (1993), «Подход к разделению плит для решения евклидовой проблемы p-центра», Algorithmica , 9 (1): 1–22, doi :10.1007/BF01185335, S2CID  5680676
9. HWang, RZ; Chang, RC; Lee, RCT (1993), «Обобщенная стратегия поиска по сепараторам для решения некоторых NP-трудных задач за субэкспоненциальное время», Algorithmica , 9 (4): 398–423, doi :10.1007/bf01228511, S2CID  2722869
10. Бадоиу, Михай; Хар-Пелед, Сариэль ; Индик, Петр (2002), «Приблизительная кластеризация с помощью основных наборов», Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений (PDF) , стр. 250–257, doi :10.1145/509907.509947, ISBN 1581134959, S2CID  5409535
11. Кумар, Панкадж; Кумар, Пиюш (2010), «Почти оптимальные решения проблем k-кластеризации» (PDF) , Международный журнал вычислительной геометрии и приложений , 20 (4): 431–447, doi :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). Целочисленное программирование . Тексты для аспирантов по математике. Том. 271. дои : 10.1007/978-3-319-11008-0. ISBN 978-3-319-11007-3.
15. Теория дискретного расположения . Мирчандани, Питу Б., Фрэнсис, Р.Л. Нью-Йорк: Wiley. 1990. ISBN 9780471892335. OCLC  19810449.{{cite book}}: CS1 maint: others (link)
16. Ахмади-Джавид, А.; Сейеди, П.; Сайам, С. (2017). «Обследование местонахождения медицинских учреждений». Computers & Operations Research . 79 : 223–263. doi :10.1016/j.cor.2016.05.018.
17. Франко, DGB; Штайнер, MTA; Ассеф, FM (2020). «Оптимизация разделения свалок отходов в штате Парана, Бразилия». Журнал чистого производства . 283 : 125353. doi : 10.1016/j.jclepro.2020.125353. S2CID  229429742.
18. Хасти, Тревор; Тибширани, Роберт; Фридман, Джером (2009). Элементы статистического обучения (Второе изд.). Springer.
19. Кляйнберг, Джон; Тардос, Ева (2006). Алгоритм проектирования . Пирсон.

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

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