Дискретно-событийное моделирование в логистике

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

имитационное моделирование, дискретно-событийное моделирование, SimPy

В данной статье рассмотрен подход к имитационному моделированию цепочек поставок с помощью дискретно-событийных моделей.

Все, кто когда-либо встречал или провожал родственников или коллег в аэропорту Пулково-1, сталкивался с необходимостью получения парковочного талона и оплаты услуг стоянки на выезде (если машина была на территории более 15 минут). Обычно, эта система работает достаточно стабильно: подъезжающие водители выстраиваются у обочины в очередь до шлагбаума, ждут прилёта самолёта и заезжают на территорию по команде пассажиров, полученной по мобильному телефону. Ранней весной этого года, забирая родственников из аэропорта, я наблюдал интересный феномен: буквально за 40 минут очередь ожидающих на выезд с территории  аэропорта стала угрожающе расти, водители заметно нервничали, старась попасть в бесплатный 15-минутный интервал, сигналили "непутёвым" собратьям, которые очень долго мешкали у автоматов оплаты. Наблюдая растерянные лица водителей у автоматов, я пытался понять, что же происходит, почему так долго проходит оплата. Через 15 или 20 минут ожидания наступила моя очередь. Я подошёл к автоматам и попытался поместить купюру в приёмное устройство. Не тут-то было! Автомат не реагировал. Второй автомат, холодно сверкая зелёными огоньками, деньги принял, но транзакция не прошла. В итоге, работал только один аппарат, у которого уже образовалась очередь. Попытки вызвать сотрудников охраны ни к чему не привели: они не желали покидать свои тёплые уютные будки и наотрез отказывались ассистировать недоумевающим водителям.

Расплатившись, я взглянул на гордо возвышающееся чудо инновационных технологий и побежал в машину. По дороге домой, я долго раздумывал над интересными особенностями организации парковки. Первое, что пришло в голову во время наблюдения за разрастающимся кризисом, это то, что рассматриваемая система является системой с положительной обратной связью: чем больше машин в очереди на выезде, тем дольше будет проходить обслуживание каждого водителя, т.к. за время ожидания истекает 15-минутный бесплатный интервал и водитель вынужден покидать машину, тратя дополнительное время на оплату. Очевидно, ситуацию спасли бы терминалы оплаты банковскими картами или автоматы более скромного размера, стоящие рядом с устройствами считывания парковочных талонов. Иррациональным показалось и поведение охраны, которая даже не попыталась обозначить для водителей неработающие автоматы оплаты, увеличивая время на безуспешные попытки расстаться с наличностью.

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

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

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

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

Осталось выбрать платформу для реализации модели, благо, выбор на рынке большой. Существуют мощные коммерческие системы с хорошей визуализационной поддержкой (например, продукт команды российских разработчиков AnyLogic, зарубежные - Arena, SIMSCRIPT, SLAM, SIMAN, AweSim), открытые системы (например, GPSS), а также прикладные библиотеки. Насколько я могу судить, в любом из рассмотренных случаев необходимо обладать навыками разработки/программирования, пусть даже в минимальной мере, как для AnyLogic.

Моим выбором стала открытая библиотека SimPy, разработанная на очень простом для изучения языке Python. Располагая аскетическими графическими возможностями, SimPy содержит всё необходимое для быстрого создания дискретно-событийных моделей и получения численных результатов. Важным фактором выбора являлось наличие хорошей документации по этой системе.

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

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

Что происходит с выручкой? Лучшим показателем для отражения ситуации является процент машин, не попавших в 15-минутный бесплатный коридор от общего числа вошедшего транспорта. График числа оплаченных въездов приведён ниже:

Наша теория подтвердилась. Из графика видно, что низкая пропускная способность выгодна парковщикам.

Представим себя на месте трафик-менеджера, отвечающего за транспортную составляющую работы аэровокзала и не состоящего в доле с организацией парковки. Каким образом можно улучшить пропускную способность с минимальными затратами? Из первого графика видно, что минимальное увеличение "бесплатного" интервала положительно влияет на пропускную способность (например, с 15 до 20 минут). Понятно, что обратной стороной этого улучшения является сокращение свободного пространства в зоне посадки и высадки пассажиров, что в какой-то момент может стать лимитирующим фактором (не смоделированного в нашем сценарии). Очевидно, что и здесь можно найти выход: нужно стимулировать водителей к короткому времени нахождения на территории аэровокзала. Как этого добиться? Во-первых, предоставить водителям актуальную информацию о прилёте самолётов: это может быть информационное табло по дороге к аэропорту или, например, трансляция внутренних сообщений аэровокзала о прилёте/вылете рейсов в незанятом FM-диапазоне, так, чтобы водители могли слушать информацию по радио в машине (другой вариант, используя bluetooth proximity marketing). Вторым стимулом может стать выделение специальных буферных зон ожидания за пределами аэропорта. Сейчас этими зонами являются подъезды к аэропорту, где идёт планомерная борьба со стоящими там автомобилями. В общем, в любой логистической системе найдётся место улучшениям.

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

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

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

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

По ссылке можно загрузить исходный код рассмотренной программы. Для её работы требуется наличие текстового файла schedule0.txt (в том же каталоге, что и сама программа). Пример записей файла:

0   20
15   20
30   20
45   20

Каждая строка означает количество поступающих машин в определённый момент времени по часам модели (20 машин с 0-й минуты, 20 машин с 15-й и т.д.). Столбцы должны быть разделены символом табуляции.