Марковская модель принятия решения водителем такси

Е.С. Фарафонова

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

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

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

Постановка задачи.

Такси выполняет перевозки пассажиров внутри и между тремя подмосковными городами, например, Пушкино, Королёв и Ивантеевка. Город, в котором находится такси, является текущим -м состоянием УМЦ (, где в рассматриваемом случае ). Всякий раз, когда водитель освобождается (высаживает очередного пассажира), он оказывается перед выбором одной из альтернатив (, где для данного частного случая ): ездить по текущему городу в поисках пассажира, ждать вызова от диспетчера или ехать на стоянку в текущем городе и стать там в очередь. Задача заключается в поиске для водителя оптимальной стратегии , позволяющей ему в каждом состоянии принимать наилучшее решение . В работе рассматриваются три периода стационарности: дневное время, часы пик, вечернее время.

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

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

Решение задачи.

1-й этап - формирование множества стратегий из дискретного множества решений ().

2-й этап состоит в формировании матриц переходных вероятностей и матриц платежей , для каждой из возможных стратегий .

3-й этап - вычисление вектора вероятностей состояний в установившемся режиме при больших значениях шага процесса .

Средняя величина платежа за один шаг , при условии, что процесс находится в -ом состоянии и применяется -ая стратегия, определится как . А далее, чтобы избавиться от условий (), необходимо усреднить условные средние платежи по множеству условий. Кроме того на данном этапе находим вектор вероятностей предельных состояний УМЦ из уравнения установившегося режима марковской цепи: .

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

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

Для исследования динамики изменения рассматриваемых показателей выполнена имитация работы такси в течение одной смены, для чего в среде MS Excel на основе случайных чисел сформированы изменения состояний и сымитированы решения, принимаемые водителем в разные периоды стационарности. Для выбора решения по двум критериям (доходы, время) применен метод, основанный на Парето-оптимальности.

Выводы.

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

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