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

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

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

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

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

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

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

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

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

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

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

NP-трудность

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

Алгоритмы

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

Существуют алгоритмы, дающие точное решение задачи. Один из таких алгоритмов даёт решение за время [8][9].

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

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

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

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

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

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

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

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

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

Название
(в алфавитном порядке) 		Лицензия Язык API Краткая информация
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/

См. также

Примечания

  1. ↑ Hochbaum, 1982, p. 148–162.
  2. ↑ Guha, Khuller, 1999, p. 228.
  3. ↑ Li, 2011, p. 77–88.
  4. ↑ Fowler, Paterson, Tanimoto, 1981, p. 133–137.
  5. ↑ Megiddo, Tamir, 1982, p. 194–197.
  6. ↑ 1 2 3 Gonzalez, 1985, p. 293–306.
  7. ↑ 1 2 Feder, Greene, 1988, p. 434–444.
  8. ↑ Hwang, Lee, Chang, 1993, p. 1–22.
  9. ↑ Hwang, Chang, Lee, 1993, p. 398–423.
  10. ↑ Bādoiu, Har-Peled, Indyk, 2002, p. 250–257.
  11. ↑ Kumar & Kumar, 2010.
  12. ↑ Препарата и Шеймос, 1989.
  13. ↑ Toussaint, 1983, p. 347–358.
  14. ↑ 1 2 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.

Ссылки