Задачи размещения объектов (Facility Location Problem): минимакс и графовые медианы

Проектирование крупных инфраструктурных сетей неизбежно сталкивается с проблемой географической оптимизации. Где построить новые региональные склады маркетплейса, чтобы минимизировать суммарные транспортные издержки при доставке товаров тысячам клиентов? В какой точке города разместить станцию скорой помощи или пожарную часть, чтобы гарантировать максимальную скорость реагирования на экстренные вызовы? В исследовании операций этот гигантский класс пространственных и дискретных оптимизационных моделей известен как Задачи размещения объектов (Facility Location Problems, FLP). Их математическое решение требует синтеза теории графов, целочисленного программирования и метрической геометрии.

Исторически первой и наиболее известной непрерывной моделью размещения является задача Вебера (Weber Problem). Она формулируется на декартовой плоскости: заданы координаты нескольких потребителей и объемы их спроса (веса). Необходимо найти такие координаты x и y для одного единственного нового склада, чтобы минимизировать сумму взвешенных евклидовых расстояний до всех потребителей. В отличие от задачи нахождения центра тяжести (которая минимизирует квадрат расстояний), задача Вебера минимизирует само расстояние, что приводит к нелинейной недифференцируемой целевой функции. Для ее аналитического решения в 1937 году был разработан итерационный алгоритм Вайсфельда (Weiszfeld Algorithm), который с помощью метода градиентного спуска с динамическим шагом быстро и безошибочно находит глобальный оптимум на плоскости.

Однако в реальной логистике объекты перемещаются не по прямой (полета птицы), а по дорожной сети. Поэтому современные модели FLP строятся на дискретных графах. Классической дискретной моделью является задача о p-медиане (p-Median Problem). Дан неориентированный взвешенный граф (города и дороги), и необходимо выбрать ровно p вершин, в которых будут открыты склады. Цель — привязать каждый город к ближайшему открытому складу так, чтобы суммарная стоимость доставки по всей сети была минимальной. Задача p-медианы является NP-трудной, поэтому для ее решения применяются методы целочисленного линейного программирования с лагранжевой релаксацией, которая ослабляет жесткое требование «каждый город должен быть обслужен», переводя его в разряд штрафов в целевой функции.

Совершенно иной математический критерий используется в задачах о p-центре (p-Center Problem), которые применяются для размещения экстренных служб. Если склад коммерческой компании волнует минимизация средних затрат, то службу спасения волнует защита от наихудшего сценария. Целевая функция в задаче p-центра — минимаксная. Алгоритм ищет такое размещение p пожарных станций, чтобы максимальное время доезда от станции до самого отдаленного населенного пункта было минимально возможным. В теории графов абсолютный 1-центр может лежать не только в вершинах, но и прямо посредине ребра (на трассе между городами), что требует применения алгоритмов Хакими для выявления локальных экстремумов вдоль каждого отрезка графа.

Самым общим и экономически проработанным классом является задача размещения без ограничений по пропускной способности, но с фиксированными затратами (Uncapacitated Facility Location Problem, UFLP). В этой модели отпадает жесткое требование открыть ровно p складов. Вместо этого вводится баланс: открытие каждого нового склада стоит определенных денег (капитальные затраты), но приближает товар к клиенту (снижает транспортные затраты). Алгоритм должен самостоятельно решить, сколько складов открыть и где именно, чтобы общая сумма капитальных и логистических затрат достигла глобального минимума. Методы ветвей и границ, дополненные эвристикой добавления/удаления узлов (ADD/DROP Heuristics), способны решать такие задачи для тысяч потенциальных локаций, формируя оптимальную топологию глобальных цепей поставок современных транснациональных корпораций.

Оценить