Авдеев В.С.
Эксперт РОО «Город 21век», аспирант Российской академии народного хозяйства и государственной службы при Президенте Российской Федерации.
Со статьёй можно ознакомиться в журнале «Альманах «Казачество» № 5 (47). 2020».
Распределение пассажиропотока на примере транспортной системы Московского Метрополитена
На сегодняшний день, транспортная система идет в ногу со временем, предоставляет и улучшает качество пассажирских сервисов во всех видах общественного транспорта. В первую очередь, большое развитие транспорта и всей транспортной системы Москвы способствовала государственная программа “Развитие транспортной системы”. Цели данной программы: обеспечение комфортных условий жизнедеятельности населения города Москвы путем развития устойчиво функционирующей, безопасной, привлекательной и удобной для всех групп населения транспортной системы как части Московского транспортного узла. Ключевым видом транспорта на всей территории Москвы и ближайшего Подмосковья несомненно является метро. Ежедневно поезда метро перевозят тысячи москвичей и гостей столицы. Опираясь на статистические данные за 2019 год, метрополитен перевез 2560,7 млн. пассажиров. Количество поездов, пропускаемых за сутки по линиям метрополитена составляет более 12 тыс. Таким образом, Московский метрополитен является одной из наиболее загруженных метросистем в мире по пассажиропотоку и занимает 6-е место.
Перед метрополитеном стоит множество задач для обеспечения комфортного пребывания пассажиров в городской подземке. Одна из главных задач по уменьшению загруженности системы является управление пассажиропотоком. Правильное планирование, реагирование на изменения и распределение потока является ключом к решению транспортной задачи Москвы.
Прежде всего, определим само понятие пассажиропоток – это движение пассажиров по определенной части транспортной сети, выраженное в количестве пассажиров, проезжающих за единицу времени через конкретное сечение транспортной сети в одном направлении. Пассажиропотоки имеют две основные характеристики: мощность и направление.
Направление пассажиропотока показывает распределение передвижений между транспортными районами. По направлению пассажиропотоки бывают в прямом и обратном направлениях. Если пассажиры следуют в какой-либо район через промежуточный (с пересадкой) при отсутствии прямых транспортных связей, то такой пассажиропоток называют транзитным.
Мощностью пассажирских потоков называется количество пассажиров, проезжающих за единицу времени через конкретное сечение транспортной сети в одном направлении. Так как пассажиропотоки по часам суток могут значительно колебаться (часы «пик», «межпиковый» период и т.д.), то для характерных периодов суток можно использовать подвижной состав разной вместимости. Но на практике не у всех перевозчиков есть возможность в течение суток производить замену подвижного состава с меньшей вместимости на большую и наоборот. Поэтому для работы по маршруту выбирают какой-либо один тип подвижного состава, вместимость которого устанавливают на основе данных о часовой мощности пассажиропотока по наиболее загруженному участку маршрута для часов «пик» либо о его мощности за сутки по маршруту в целом.
Математическое представление транспортной системы
По публичным данным представленным на сайте метро, на март 2020 года Московский метрополитен насчитывает около 334 станций (238 станций метрополитена, 31 станция МЦК, 6 станций Московского монорельса, 55 станций Московских центральных диаметров) (1). Эту развитую систему можно представить в виде двунаправленного графа, где каждая станция метро представлена в виде вершины графа, а перегоны в виде ребер (Рис. 1, Альманах «Казачество» № 5 (47). 2020). Каждая вершина графа будет иметь порядковое значение в соответствии с количеством станций (2).
Большинство пассажиров не задумываются о том, какой маршрут является оптимальным. В среднем пассажир каждый день перемещается по одному и тому же направлению и заранее планирует свою поездку. Благодаря современным гаджетам, пассажир с легкостью рассчитывает свой маршрут не задумываясь об алгоритмах их поиска.
Существует большой множество алгоритмов поиска кратчайшего пути по графу между двумя заданными точками. В качестве наиболее оптимального алгоритма предлагается использовать доработанный алгоритм Дейкстра, а именно алгоритм A* (A-star).
Данный алгоритм нашел широкое применение в видеоиграх для нахождения кратчайшего пути между двумя заданными точками. Его относят к информированным алгоритмам поиска, так как для решения задач используются данные о стоимости пути и принципы эвристики. Можно выделить два основных свойства:
- - оптимальность, что означает что он гарантированно найдет наилучшее из возможных решений;
- - полнота, то есть если решение существует, то алгоритм гарантированно его найдет.
Также можно отметить, что алгоритм не просто стремимся найти кратчайшее расстояние, а также учитывает и его длительность движения (3).
Особенностью данного алгоритма является то, что он является более точным и не распространяется по всем вершинам графа в отличии от Дейкстры, а опирается на эвристику и придерживается ее направлению. В качестве эвристики предлагается использовать Евклидову эвристику и в качестве точек измерения расстояния использовать широту и долготу станций.
Для понимания работы алгоритма А* необходимо владеть следующими терминами:
- - Узел (или вершина) — все потенциальные уникальные позиции или остановки;
- - Переход — само перемещение между вершинами или узлами;
- - Начальный узел — тот, от которого начинается путь;
- - Конечный узел — тот, в котором путь должен завершиться;
- - Пространство поиска — коллекция всех допустимых узлов;
- - Стоимость — числовое значение (например, расстояние, время или денежная стоимость), характеризующее отрезок пути от одного узла к другому.
Каждый раз при посещении узла подсчитывается его стоимость f(n) (за n принимается соседний узел). Таким образом, алгоритм посещает все соседние узлы и высчитывает тот, у которого данный показатель минимален (4).
Реализацию алгоритма можно описать следующими этапами:
- Создается два списка вершин – ожидающие рассмотрения и уже рассмотренные. В ожидающие добавляется точка старта, список рассмотренных пока пуст.
- В процессе работы алгоритма для вершин рассчитывается функция стоимости:
, где
g (n) – стоимость пути от начального узла до любого узла n
h (n) – эвристическая расчетная стоимость от узла n до целевого узла.
В нашем случае используется Евклидова эвристика и она имеет следующий вид:
Также каждая точка хранит ссылку на точку, из которой в нее пришли.
- Из списка точек на рассмотрение выбирается точка с наименьшим F. Обозначим ее X.
- Если X – цель, то мы нашли маршрут.
- Переносим X из списка ожидающих рассмотрения в список уже рассмотренных.
- Для каждой из точек, соседних для X (обозначим эту точку Y), делаем следующее:
- - если Y уже находится в рассмотренных – пропускаем ее;
- - если Y еще нет в списке на ожидание – добавляем ее туда, запомнив ссылку на X и рассчитав Y.G (это X.G + расстояние от X до Y) и Y.H;
- - если же Y в списке на рассмотрение – проверяем, если X.G + расстояние от X до Y < Y.G, значит мы пришли в точку Y более коротким путем, заменяем Y.G на X.G + расстояние от X до Y, а точку, из которой пришли в Y, на X;
- - если список точек на рассмотрение пуст, а до цели мы так и не дошли значит маршрут не существует.
Определив алгоритм поиска оптимального маршрута, далее рассмотрим загруженность метрополитена. Опираясь на статистические данные за 2019 год, была составлена тепловая карта загруженность в час пик (Рис. 2, Альманах «Казачество» № 5 (47). 2020).
Загруженность линий на схеме обозначена цветами: от зеленого («слабая загруженность») до черного («очень сильная загруженность»). Почти полностью черной обозначена фиолетовая ветка метро. На эту схему не нанесен недавно открытый участок розовой ветки с переходом на станции «Лермонтовский проспект». Также большая загруженность наблюдается на участках синей ветки: от «Курской» до «Бауманской» и от «Киевской» до «Парка Победы». Меньше пассажиров в час пик ездят от станции «Строгино» до «Пятницкого шоссе».
Как можно наблюдать загруженность метро начинается с центра и начинает затухать ближе к к концу линий. Метросистема имеет кольцевую структуру, что позволяет произвести аналогию с волнами от капли воды на поверхности жидкости. Не имея статистических данных о количестве пассажиров на станции и в подвижном составе, введем случайные показатели загруженности в зависимости от кольцевой структуры.
Сперва разделим граф на три зоны и введем весовые значения для ребер графа: Таблица 1. Зональное деление (Альманах «Казачество» № 5 (47). 2020).
Для начали построим маршрут без учета весов и зональности метро, построим маршрут Коммунарка - Алтуфьево для прохождения маршрута сквозь все зоны:
[39, 38, 37, 36, 35, 34, 33, 26, 24, 23, 22, 21, 20, 19, 18, 17, 222, 221, 218, 211, 209, 205, 198, 195, 192, 190, 189, 188]
Как можно видеть на рис. 3 слева алгоритм беспрепятственно проходит сквозь все зоны загруженность и доходит до конечной точки.
Далее введем весовые значения в зависимости от зоны и прогоним алгоритм еще раз по тому же маршруту:
[39, 38, 37, 36, 35, 34, 33, 26, 24, 23, 22, 21, 20, 19, 171, 173, 174, 176, 177, 211, 209, 205, 198, 195, 192, 190, 189, 188]
Теперь мы наблюдаем иную картину на рис. 3 справа и можем сделать вывод, что граф начал обходить некоторые нагруженные ребра и предлагать более оптимальный маршрут.
Таким образом, зная фактор загруженность метро можно управлять пассажиропотоками и правильно распределять нагрузку на общественный транспорт Москвы. Данный показатель может кардинально решить транспортную задачу Москвы дополнительную регулирую как мощность пассажиропотока так и его направление.
Заключение
В данной статье была наглядно рассмотрена методика распределения пассажиропотока на примере Московского метрополитена и предложен инструментарий по мониторингу и возможному распределению пассажира внутри транспортной системы.
Список литературы:
1. Официальный сайт Московского метрополитена – Метрополитен в цифрах, 2019. // URL: https://mosmetro.ru/press/digits
2. Таланов В.А. Нахождения кратчайших путей в графе // Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных. – Н. Новгород: Изд-во Нижегор. гос. ун-та, 2005. Гл. 3.4. С. 236–237. // ISBN 5–85747–810–8.
3. Галкина В.А. Построение кратчайших путей в ориентированном графе // Галкина В.А. Дискретная математика. Комбинаторная оптимизация на графах, 2003.
4. Миков Е.П., Бондарь В.А. - Алгоритм поиска пути из пункта А в пункт Б*, 2017 - Сборник научных трудов НГТУ. 2017. № 2 (88). С. 33-40.
