Исследование проблем размещения объектов (FLP) , также известное как анализ местоположения , представляет собой отрасль исследования операций и вычислительной геометрии , связанную с оптимальным размещением объектов для минимизации транспортных расходов с учетом таких факторов, как предотвращение размещения опасных материалов рядом с жильем и конкурентами. удобства. Методы также применимы к кластерному анализу .
Простая задача размещения объекта — это задача Вебера , в которой необходимо разместить один объект, при этом единственным критерием оптимизации является минимизация взвешенной суммы расстояний от заданного набора точечных объектов. Более сложные проблемы, рассматриваемые в этой дисциплине, включают размещение нескольких объектов, ограничения на расположение объектов и более сложные критерии оптимизации.
В базовой формулировке задача размещения предприятия состоит из набора потенциальных площадок предприятия L , где предприятие может быть открыто, и набора точек спроса D , которые необходимо обслуживать. Цель состоит в том, чтобы выбрать подмножество F объектов для открытия, чтобы минимизировать сумму расстояний от каждой точки спроса до ближайшего объекта плюс сумму затрат на открытие объектов.
Задачу размещения предприятия на графах общего вида NP-трудно решить оптимальным образом путем сведения (например) из задачи покрытия множества . Разработан ряд аппроксимационных алгоритмов для задачи размещения объектов и многих ее вариантов.
Без предположений о наборе расстояний между клиентами и сайтами (в частности, без предположения, что расстояния удовлетворяют неравенству треугольника ), задача известна как неметрическое расположение объекта и может быть аппроксимирована с точностью до множителя O (log n ). [1] Этот множитель точен благодаря редукционной редукции, сохраняющей аппроксимацию, из задачи о покрытии множества.
Если мы предполагаем, что расстояния между клиентами и сайтами ненаправлены и удовлетворяют неравенству треугольника, мы говорим о проблеме метрического местоположения объекта (MFL) . MFL по-прежнему является NP-трудным, и его трудно аппроксимировать с коэффициентом лучше, чем 1,463. [2] Самый известный в настоящее время алгоритм аппроксимации достигает коэффициента аппроксимации 1,488. [3]