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

Задача о размещении объектов, известная также как анализ расположения оборудования или задача 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.
SITATIONfreewareМожет решать пяти классов задач, включая: P-медиана, P-центр, Покрытие множествами, Максимальное покрытие и Задача с фиксированными затратами без ограничения пропускной способности. [14]

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

См. также

Примечания

Литература

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.