Гений места в цепочках поставок

30/04/2010
Подписка RSS

выбор местоположения

Цель настоящей публикации - дать обзор основных подходов к выбору местоположения элементов инфраструктуры цепочек поставок.

Вас никогда не удивляло, как удаётся археологам находить места потенциальных городищ там, где самый профессиональных геоморфолог с трудом распознает в рельефе последствия деятельности человека? Почему при посещении монастыря или старинной крепости, почти всегда охватывает удивление от того, насколько глубока связь назначения объекта и его окружения: рельефа, растительности, речной сети, полезных ископаемых и даже жителей? Не правда ли, глядя на современные творения, подобное ощущение посещает крайне редко?

Сторонники иррационального могут апеллировать к тому, что древние строители были ближе к маленькому божеству, Genius Loci, "гению места", как называли его римляне. У почитателей рационального свой расчёт.

С самых древних времён выбор местоположения был ключём к реализации эффективной логистической (считай, политической) стратегии. Выбирая место для церкви, города или крепости, правители рассматривали множество факторов:

  • технологические;
  • военные;
  • макроэкономические;
  • инфраструктурные;
  • ресурсные.

Не смотря на всё разнообразие критериев принятия решений, цель инвестиций в большинство крупных инфраструктурных объектов была одна: улучшить время отклика. Время на доставку грузов, время реагирования на внешние угрозы, время на мобилизацию населения и сбор налогов, время на передачу информации. На другой чаше управленческих весов размещалась стоимость и риски: капитальные и текущие затраты, риски потери контроля или разрушения объекта.

Response time

Если на карте для каждого из городов отобразить равноудалённые
линии, иначе называемые изохронами, мы получим карту влияния городов на окружающие территории. Это идеализированная картинка. В реальности, материальные и, вслед за ними, информационные потоки распространяются вовсе не так, как свет в вакууме. Распространению этих потоков препятствует сопротивление среды.

Представьте себе, как деформировалось бы поле влияния городов из-за неоднородности ландшафта, растительности, наличия рек и дорог. Представили? Посмотрите на современную карту административного деления страны - это и есть визуализация поля влияния городов. Административные границы, чаще всего, проходят по территории с одинаковым влиянием двух соседних городов. Причём, это границы очень консервативны и могут отражать ситуацию XVIII-го века и ранее.

На рисунке ниже показано, как построить равноудалённые границы между тремя городами в идеальном случае, когда не учитывается рельеф и дорожная сеть.

Voronoi diagram

Если продолжить логику построения границ на всю карту, мы получим ячеистый математический объект, называемый диаграммой Вороного.

Voronoi diagram example

Диаграммы Вороного используются для привязки географически распределённых клиентов к центрам обслуживания в том случае, если дорожная сеть не играет большой роли. Внимательно взглянув на диаграмму Вороного, можно понять, почему сети мобильных операторов называют "сотовыми" (с таким же успехом, они могли бы называться "Вороными"). Описанным методом можно разграничивать кварталы городов, обслуживаемые станциями скорой помощи или пожарными и другими службами. В случае плотной дорожной сети, её неоднородностями можно пренебречь, используя эффективные алгоритмы построения диаграмм Вороного для определения круга клиентов, закреплённых за магазином или складом: все клиенты, попавшие внутрь ячейки, обслуживаются из её центра. При решении задач выбора расположения объектов используют и более сложные диаграммы, строящиеся с учётом дорожной сети.

Идея поля влияния нашла интересное продолжение применительно к задаче поиска оптимального положения объектов в цепочке поставок. Представим себе физическую аналогию: каждый из городов является центром притяжения и обладает определённым весом (потребительским потенциалом). Чем дальше мы будем удаляться от города, тем меньшая сила притяжения будет на нас действовать. Эмпирически показано, что в случае потребительского спроса работает тот же принцип, что и с силой тяготения: чем дальше потребитель находится от магазина, тем меньше вероятность его посещения, причём, обратно пропорционально времени на поездку к магазину. Эта модель называется моделью Хаффа (Huff retail model, 1963). Она активно используется при выборе местоположения супер-маркетов и сервисных центров.

На этом физические аналогии с гравитацией не заканчиваются. Рассмотрим несколько городов на плоской карте. Пусть каждый город обладает определённым весом. Как найти место для новой столицы, являющейся центром масс этой системы? Визуальное представление задачи поиска центра масс системы материальных точек на плоскости приведено на рисунке. Если в пластине проделать отверстия, пропустить через них нити с грузами соответствующей массы, то узел, скрепляющий все нити, уравновесится в точке, являющейся центром масс.

Для аналитического решения этой задачи можно использовать шаблон (вкладка Mercator) нахождения центра масс системы точек на плоскости с заданными географическими координатами и массами. На динамической карте приведены результаты расчёта для четырёх точек с разными массами, взятыми из представленного шаблона.

Развитием гравитационной модели является подход, в котором оптимальному расположению центра обслуживания соответствует точка, минимизирующая произведение масс перевозимых клиентских грузов на расстояние перевозки (задача Вебера, 1903). При решении этой оптимизационной задачи, используют два способа расчёта расстояний:

  • расстояние по кратчайшему пути между точками на плоскости (евклидово расстояние);
  • манхэттеновское расстояние, соответствующее расстоянию по улицам города с прямоугольными кварталами.

В реальности расстояния между точками на местности не являются ни евклидовыми, ни манхэттеновскими. В статье "Связность дорожной сети" мы проводили расчёт расстояний между основными городами европейской части РФ и пришли к выводу, что среднее отношение расстояния "по воздуху" (т.е. евклидового расстояния) к расстоянию по дорогам составляет 1,28. Если провести вычислительный эксперимент методом Монте-Карло, равновероятно выбирая случайный угол (в диапазовне 0-90 градусов) между катетом и единичной гипотенузой в манхэттеновском треугольнике, то в серии из 15 тыс. опытов среднее значение манхэттеновского расстояния будет в диапазоне 1,27-1,28 (минимальное - 1, а максимальное - корень из 2). Выводом из вышесказанного следует то, что, манхэттеново расстояние ближе к истинному расстоянию по дорожной сети, чем евклидово. В любом случае, если есть возможность, в расчётах следует использовать обе метрики.

В рассмотренных выше способах выбора месторасположения мы ориентировались на непрерывных подход, когда "центр масс" или "равноудалённую" точку можно было получить в любом месте на карте. Иногда, с некоторой долей иронии, такой подход называют моделированием "голубого неба" или "зелёного поля". В реальности, у нас есть ограниченное число мест, в которых мы могли бы построить завод или склад. Чем меньше вариантов в задаче выбора, тем больше шансов надеяться на возможность успешного нахождения оптимального решения, ведь для N возможных точек существует 2^N-1 географических конфигураций (E. Gardner, 2003). 

Если рассматривать дерево задач оптимального выбора расположения, то всё многообразие можно свести к следующим классам (A. Klose, A. Drexl, 2003):

КритерийКласс моделейТиповые модели
Число сценариевНепрерывный (бесконечное число сценариев)Multi-source Weber problem (MWP). Удовлетворение спроса в нескольких точках с нескольких складов. NP-сложная задача, есть эвристики для решения. Критерий: минимальное суммарное расстояние между складами и точками спроса.
Дискретный (конечное число сценариевP-median problem (PMP). Вариант MWP для дискретного случая (на графе): разместить p узлов так, чтобы удовлетворить спрос. Решается методами линейного программирования.
Число эшелоновОдноэшелонныйMaximum covering location problem (MCLP). Цель: выбрать местоположение так, чтобы обеспечить максимальное покрытие точек спроса.
МногоэшелонныйTwo-stage capacitated facility location problem (TSCFLP). Цель: минимизировать постоянные и переменные издержки производства и распределительных центров.
Ограничения по мощностям ОграниченныйСapacitated facility location problem with single sourcing (CFLPSS). Цель: удовлетворить спрос при условии ограниченности пропускной способности складов или транспорта, обеспечив связи между складами и точками спроса один-к-одному. NP-сложная.
НеограниченныйUncapacitated facility location problem (UFLP). Цель: разместить производства так, чтобы обеспечить минимальные постоянные и переменные издержки.
 Учёт времени СтатическийВсе вышеперечисленные
ДинамическийDynamic UFLP. В любой период времени доступна возможность закрытия или открытия одного из складов. Нелинейная оптимизация.
Неопределённость данныхДетерминированный Все вышеперечисленные
ВероятностныйВероятностный вариант PMP: спрос и время доставки ("расстояния") носят вероятностный характер.
Число продуктовОднопродуктовыйВсе вышеперечисленные
МногопродуктовыйMulti-activity uncapacitatedfacility location problem (MUFLP). Аналог UFLP с дополнительным условием необходимости определения того, какие продукты отгружаются с каких складов.

В рассмотренном выше примере, минимизация расстояния, умноженного на массу перевозимой продукции, соответствует минимизации совокупных затрат на транспортировку, - один из наиболее часто используемых критериев принятия решений при выборе местоположения. На графике (S. Chopra, 2000) показаны основные компоненты совокупных затрат и их динамика при росте числа складов/магазинов/заводов в цепочке поставок.

Не смотря на свою популярность, минимум затрат - далеко не единственный критерий принятия решений. Например, для выбора месторасположения медицинского центра могут быть использованы следующие критерии:

  • максимальная занятость персонала (1);
  • минимизация расстояния до центра на душу населения (2);
  • минимизация времени на визит (3);

На рисунке показаны результаты расчёта оптимального местоположения мед. центра по трём вышеприведённым критериям для небольшого региона в США, включающего 3 города:

Как видно из абриса, выбор критерия оптимизации, фактически, определяет город, в котором будет находиться центр.

В обзоре "Многокритериальный анализ задач по размещению объектов" авторы разделили критерии оптимизации из 45 проанализированных ими работ на четыре группы:

ГруппаКритерии
Минимизация затрат
  • Минимизация суммы расстояний до точек спроса
  • Минимизация суммы расстояний от объектов до ближайшего конкурента
  • Минимизация расстояний до самых дальних точек спроса
  • Минимизация максимального расстояния между парами объектов (например, складами)
  • Минимизация расстояния от каждой точки спроса до ближайшего объекта
  • Минимизация числа объектов
  • Минимизация совокупных затрат на недвижимость
  • Минимизация затрат, превышающих бюджет
  • Минимизация операционных издержек
  • Минимизация транспортных издержек
  • Минимизация постоянных и переменных затрат
  • Минимизация затрат клиентов
Удовлетворение спроса
  • Максимизация объёма спроса на каждый объект (например, склад)
  • Максимизация удовлетворённого спроса
  • Максимизация расстояния до остальных объектов и конкурентов
  • Максимизация географического покрытия спроса
Максимизация прибыли
  • Максимизация возврата инвестиций
  • Максимизация производительности
  • Максимизация доли рынка
Уменьшение ущерба
окружающей среде
  • Минимизация ухудшения показателей качества воздуха/воды
  • Минимизация потребности в очистных сооружениях
  • Минимизация числа населения, подверженного риску
  • Максимизация показателей качества жизни

Задача оптимизации может заключаться не только в открытии новых точек, но и в закрытии старых. Англиканская церковь, испытывающая резкое падение числа постоянных прихожан с середины 60-х годов, проводила исследование по выбору приходов-кандидатов на закрытие в Лондоне. В этом исследовании функция оптимизации оценивала человеко-мили, затрачиваемые прихожанами из закрываемого прихода, на переход в оставшиеся открытыми церкви.

Мы рассмотрели основные подходы в области поиска оптимального местонахождения для объектов цепочки поставок. Как видим, существует множество методов, ограничений и взглядов. Тем не менее, остался открытым вопрос о том, почему решения людей, не вооружённых вычислительными мощностями и теорией оптимизации, принятые многие сотни лет назад, продолжают удивлять нас своей рациональностью? Думаю, ответ прост: комбинация здравого смысла, наблюдательности, интуиции и хороших отношений с genius loci стоит большего, чем сухая статистика и супер-сложные алгоритмы.