Задача о размещении объектов ({g;gcg k jg[bypyunn kQaytmkf)

Задача о размещении объектов, известная также как анализ расположения оборудования или задача k-центра, — это ветвь исследования операций и вычислительной геометрии, исследующей оптимальное расположение объектов с целью минимизировать цены перевозок с учётом таких ограничений, как размещение опасных материалов вблизи жилищ. Техника применима также к кластерному анализу.

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

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

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

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

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

Если мы предполагаем, что расстояния между клиентами и местами размещения объектов неориентированны и удовлетворяют неравенству треугольника, мы говорим о задаче метрического размещения объектов (МРО). МРО остаётся NP-трудной задачей и её трудно аппроксимировать с множителем, лучшим 1.463^[2]. На настоящее время лучший аппроксимационный алгоритм имеет коэффициент 1.488.^[3].

Минимаксное размещение объектов

Минимаксная задача о размещении объектов ищет размещение, минимизирующее максимальные расстояния до мест размещения, где расстояние от некоторой точки до мест размещения — это расстояние от точки до ближайшего места размещения. Формальное определение следующее: Если задано множество точек P ⊂ ℝ^d, нужно найти множество точек S ⊂ ℝ^d, |S| = k, такое, что значение max_p ∈ P(min_q ∈ S(d(p, q)) ) будет минимальным.

В случае евклидовой метрики при k = 1 задача известна как задача о наименьшей ограничивающей сфере или задача 1-центра. Изучение задачи прослеживается по меньшей мере до 1860 года, см. статью «Ограничивающая сфера» для деталей.

NP-трудность

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

Алгоритмы

Точное решение

Существуют алгоритмы, дающие точное решение задачи. Один из таких алгоритмов даёт решение за время $n^{O({\sqrt {k}})}$ ^[8]^[9].

Аппроксимация 1 + ε

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

Выделение отдалённых точек

Из-за трудности задачи непрактично искать точное решение или близкую аппроксимацию. Вместо этого для больших k широко используется аппроксимация с коэффициентом 2. Эта аппроксимация известна под названием «Алгоритм выделения отдалённых точек» (ВОТ = Farthest-point clustering, FPC) или как алгоритм обхода «сначала дальний»^[англ.] ^[6]. Алгоритм довольно прост — выбираем произвольную точку множества как центр, находим самую дальнюю из оставшегося множества и считаем её следующим центром. Продолжаем процесс, пока не наберём k центров.

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

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

Максиминное размещение объектов

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

Свободно распространяемое программное обеспечение для решения задач размещения объектов

Название (в алфавитном порядке)	Лицензия	Краткая информация
FLP Spreadsheet Solver	Creative Commons Attribution 4.0 International License	Система на основе Microsoft Excel и VBA с открытым кодом для решения задачи о размещении объектов со ссылкой на ГИС общего доступа. link Видео уроки link ^[14].
ODL Studio	LGPL	Ограниченный кластерный компонент в ODL Studio решает задачу P-медианы (размещения с минимизацией взвешенной суммы расстояний). Программа включает планы размещения, отчёты и загрузку/выгрузку в Excel. [1]
SITATION	freeware	Может решать пяти классов задач, включая: P-медиана, P-центр, Покрытие множествами, Максимальное покрытие и Задача с фиксированными затратами без ограничения пропускной способности. [2] ^[14]

http://www.opendoorlogistics.com/tutorials/tutorial-territory-design/step-3-automated-territory-design/

См. также

Примечания

↑ Hochbaum, 1982, p. 148–162.
↑ Guha, Khuller, 1999, p. 228.
↑ Li, 2011, p. 77–88.
↑ Fowler, Paterson, Tanimoto, 1981, p. 133–137.
↑ Megiddo, Tamir, 1982, p. 194–197.
↑ ¹ ² ³ Gonzalez, 1985, p. 293–306.
↑ ¹ ² Feder, Greene, 1988, p. 434–444.
↑ Hwang, Lee, Chang, 1993, p. 1–22.
↑ Hwang, Chang, Lee, 1993, p. 398–423.
↑ Bādoiu, Har-Peled, Indyk, 2002, p. 250–257.
↑ Kumar & Kumar, 2010.
↑ Препарата и Шеймос, 1989.
↑ Toussaint, 1983, p. 347–358.
↑ ¹ ² Csoke, 2015.

Литература

Препарата Ф., Шеймос М. . Вычислительная геометрия: Введение. — М.: Мир, 1989. — ISBN 5-03-001041-6.
Bādoiu M., Har-Peled S., Indyk P. Approximate clustering via core-sets // Proceedings of the thirty-fourth annual ACM symposium on Theory of Computing. — 2002. — P. 250–257.
Csoke M. The Facility Location Problem. — Governors State University, 2015.
Feder T., Greene D. Optimal algorithms for approximate clustering // Proceedings of the twentieth annual ACM symposium on Theory of Computing. — 1988. — P. 434–444.
Fowler R. J., Paterson M. S., Tanimoto S. L. Optimal packing and covering in the plane are NP-complete // Information Processing Letters. — 1981. — Vol. 12. — P. 133–137. — doi:10.1016/0020-0190(81)90111-3.
Gonzalez T. Clustering to minimize the maximum intercluster distance // Theoretical Computer Science. — 1985. — Vol. 38. — P. 293–306. — doi:10.1016/0304-3975(85)90224-5. Архивировано 24 января 2013 года.
Guha S., Khuller S. Greedy Strikes Back: Improved Facility Location Algorithms // Journal of Algorithms. — 1999. — Vol. 31. — P. 228. — doi:10.1006/jagm.1998.0993.
Hochbaum D. S. Heuristics for the fixed cost median problem // Mathematical Programming. — 1982. — Vol. 22. — P. 148–162. — doi:10.1007/BF01581035.
Hwang R. Z., Lee R. C. T., Chang R. C. The slab dividing approach to solve the Euclidean p-center problem // Algorithmica. — 1993. — Vol. 9, no. 1. — P. 1–22. — doi:10.1007/BF01185335.
Hwang R. Z., Chang R. C., Lee R. C. T. The generalized searching over separators strategy to solve some NP-Hard problems in subexponential time // Algorithmica. — 1993. — Vol. 9, no. 4. — P. 398–423. — doi:10.1007/bf01228511.
Kumar P., Kumar P. Almost optimal solutions to k-clustering problems // International Journal of Computational Geometry & Applications. — 2010. — Vol. 20, no. 4.
Li Shi. . A 1.488. Approximation Algorithm for the Uncapacitated Facility Location Problem // Automata, Languages and Programming. — Lecture Notes in Computer Science. — 2011. — Vol. 6756. — P. 77–88. — ISBN 978-3-642-22011-1. — doi:10.1007/978-3-642-22012-8_5.
Megiddo N., Tamir A. On the complexity of locating linear facilities in the plane // Operations Research Letters. — 1982. — Vol. 1, no. 5. — P. 194–197. — doi:10.1016/0167-6377(82)90039-6.
Toussaint G. T. Computing largest empty circles with location constraints // International Journal of Computer and Information Sciences. — 1983. — Vol. 12, no. 5. — P. 347–358.

Ссылки

INFORMS section on location analysis, профессиональное общество изучения проблем размещения.
Библиография по задачам размещения, собранная Тревором Хале и содержащая более 3400 статей.
Библиотека алгоритмов размещения
Утилита размещения производства в Web-варианте)
Оптимизатор производства размещения, основанное на MATLAB средство решения задач размещения производства.

[_48d69bdada39f6e7-1] Hochbaum, 1982, p. 148–162.

[_78686257a239f51d-2] Guha, Khuller, 1999, p. 228.

[_1774fabff56604d1-3] Li, 2011, p. 77–88.

[_0a01c9ea7164c1df-4] Fowler, Paterson, Tanimoto, 1981, p. 133–137.

[_ce1c592e6d49b2fb-5] Megiddo, Tamir, 1982, p. 194–197.

[_2676da208f8a69b2-6] ¹ ² ³ Gonzalez, 1985, p. 293–306.

[_f031d07af3df2343-7] ¹ ² Feder, Greene, 1988, p. 434–444.

[_88d6a9c8706ecb63-8] Hwang, Lee, Chang, 1993, p. 1–22.

[_7a386a31a45d1feb-9] Hwang, Chang, Lee, 1993, p. 398–423.

[_8c86c94b7463ec3a-10] Bādoiu, Har-Peled, Indyk, 2002, p. 250–257.

[_8b31262ea4f166c0-11] Kumar & Kumar, 2010.

[_20a1a21ee334c36e-12] Препарата и Шеймос, 1989.

[_0f5063959c52d1f7-13] Toussaint, 1983, p. 347–358.

[_9f16dab96a8c1778-14] ¹ ² Csoke, 2015.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]