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

Перейти к навигацииПерейти к поиску

Задача о размещении объектов, известная также как анализ расположения оборудования или задача 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 SolverCreative Commons Attribution 4.0 International LicenseСистема на основе Microsoft Excel и VBA с открытым кодом для решения задачи о размещении объектов со ссылкой на ГИС общего доступа. link Видео уроки link [14].
ODL StudioLGPLОграниченный кластерный компонент в ODL Studio решает задачу P-медианы (размещения с минимизацией взвешенной суммы расстояний). Программа включает планы размещения, отчёты и загрузку/выгрузку в Excel. [1]
SITATIONfreewareМожет решать пяти классов задач, включая: 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.

Ссылки