Авдеев В.С.
IT специалист издательства «Этносоциум», эксперт РОО «Город 21век», аспирант РАНХиГС (Российская академия народного хозяйства и государственной службы при Президенте Российской Федерации).
Со статьёй можно ознакомиться в журнале «Этносоциум и межнациональная культура» 9 (147). 2020. Стр. 36.
Распределение пассажиропотока на примере транспортной системы Московского Метрополитена
На сегодняшний день, транспортная система идет в ногу со временем предоставляю и улучшаю качество пассажирских сервисов во всех видах общественного транспорта. В первую очередь, большое развитие транспорта и всей транспортной системы Москвы способствовала государственная программа “Развитие транспортной системы”. Цели данной программы: обеспечение комфортных условий жизнедеятельности населения города Москвы путем развития устойчиво функционирующей, безопасной, привлекательной и удобной для всех групп населения транспортной системы как части Московского транспортного узла. Ключевым видом транспорта на всей территории Москвы и ближайшего Подмосковья несомненно является метро. Ежедневно поезда метро перевозят тысячи москвичей и гостей столицы. Опираясь на статистические данные за 2019 год, метрополитен перевез 2560,7 млн. пассажиров. Количество поездов, пропускаемых за сутки по линиям метрополитена составляет более 12 тыс. Таким образом, Московский метрополитен является одной из наиболее загруженных метросистем в мире по пассажиропотоку и занимает 6-е место.
Перед метрополитеном стоит множество задач для обеспечения комфортного пребывания пассажиров в городской подземке. Одна из главных задач по уменьшению загруженности системы является управление пассажиропотоком. Правильное планирование, реагирование на изменения и распределение потока является ключом к решению транспортной задачи Москвы.
Прежде всего, определим само понятие пассажиропоток – это движение пассажиров по определенной части транспортной сети, выраженное в количестве пассажиров, проезжающих за единицу времени через конкретное сечение транспортной сети в одном направлении. Пассажиропотоки имеют две основные характеристики: мощность и направление.
Направление пассажиропотока показывает распределение передвижений между транспортными районами. По направлению пассажиропотоки бывают в прямом и обратном направлениях. Если пассажиры следуют в какой-либо район через промежуточный (с пересадкой) при отсутствии прямых транспортных связей, то такой пассажиропоток называют транзитным.
Мощностью пассажирских потоков называется количество пассажиров, проезжающих за единицу времени через конкретное сечение транспортной сети в одном направлении. Так как пассажиропотоки по часам суток могут значительно колебаться (часы «пик», «межпиковый» период и т.д.), то для характерных периодов суток можно использовать подвижной состав разной вместимости. Но на практике не у всех перевозчиков есть возможность в течение суток производить замену подвижного состава с меньшей вместимости на большую и наоборот. Поэтому для работы по маршруту выбирают какой-либо один тип подвижного состава, вместимость которого устанавливают на основе данных о часовой мощности пассажиропотока по наиболее загруженному участку маршрута для часов «пик» либо о его мощности за сутки по маршруту в целом.
Обзор исследований
Тема пассажиропотока весьма популярная в транспортной среде. Существует множество исследований в данной области, рассмотрим некоторые из них.
На Ленинградском метрополитене проведено комплексное обследование пассажиропотоков талонным методом со 100%-ым охватом пассажиров. Руководство подготовкой и обработкой его материалов осуществляло ПО «Ленсистемотехника». Результаты, вычисленные на ЭВМ ЕС-1022, показали, что за период, прошедший между обследованиями 1976 и 1981 годов, произошли значительные изменения в распределении пассажиропотоков.
Перераспределение пассажиропотоков привело к «перемещению» критических, то есть наиболее загруженных, перегонов. Если на Московско-Петроградской и Невско-Василеостровской линиях такие перегоны остались практически прежними («Электросила» — «Московские ворота» и «Маяковская» — «Гостиный двор»), то на Кировско-Выборгской критический перегон «переместился» с юга на север и с I на II путь. Максимальная часовая загрузка на участке «Площадь Мужества» — «Лесная» по II пути составила 47 850 пассажиров за период с 7 час. 30 мин. до 8 час. 30 мин. На этом же перегоне выявлена наибольшая 15-минутная нагрузка: с 7 час. 45 мин. до 8 часов — 12 305 пассажиров. Вечерами наиболее загружен теперь перегон «Чернышевская» — «Площадь Ленина» по I пути, где с 17 час. 30 мин. до 18 час. 30 мин. зафиксирован поток в 37 456 пассажиров. Наибольшая 15-минутная загрузка этого перегона с 17 час. 45 мин. до 18 часов выразилась в цифре — 10 152 пассажира. Причина столь резкого перераспределения — в интенсивном жилищном строительстве районов, расположенных вблизи периферийных станций северного участка. Соответственно возросло наполнение вагонов. Лишь на Невско-Василеостровской линии оно снизилось на 32,4 % за счёт прицепки шестого вагона в составе (1).
Мониторинг пассажиропотока также имеет важное место управлении. Вести подсчет пассажиров можно с помощью простых телефонов. Пассажир, войдя в салон общественного транспортного средства, отправляет соответствующее смс-сообщение, в котором указывается идентификационный номер средства. Этот номер должен находиться на видном месте в салоне. В ответ ему приходит сообщение об успешной оплате проезда в данном средстве. По времени отправки емс-сообщения и идентификационному номеру легко определить местонахождение пассажира, если это транспортное средство оборудовано системой ГЛОНАСС. С учетом быстрого темпа развития электронных способов оплаты проезда наиболее перспективными методами мониторинга пассажиропотока представляются предлагаемые в статье терминальные методы, основанные на применении терминалов для контроля и оплаты проезда (2).
Что касается алгоритмов поиска кратчайшего маршрута рассмотрим некоторые из них. Алгоритм Дейкстры. Самый известный и широко распространенный алгоритм. Был разработан голландским ученым Эдсгером Дейкстрой в 1959 году и используется для нахождения пути в графе из одной вершины до всех остальных. Алгоритм работает исключительно для графов с ребрами положительного веса. Данный алгоритм считается одним из самых простых. Он хорошо выполняется в графах с небольшим количеством вершин. В случае с сетью связи, количество вершин в графе может доходить до нескольких тысяч. Тогда использование данного алгоритма не будет являться оптимальным выбором для решения задачи построения трассы подключения абонента сети связи. Также,недостатком алгоритма Дейкстры в нашем случае является то, что он ищет кратчайшие пути от одной вершины графа до всех остальных.
Алгоритм Беллмана-Форда. Это алгоритм поиска кратчайшего пути во взвешенном графе, который находит путь от одной вершины до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда допускает наличие в графе ребер с отрицательным весом. Был предложен независимо американцами Ричардом Белл-маном и Лестором Фордом. Данный алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. Условие нашей задачи — нахождение рационального пути между двумя точками сети связи. Избыточная информация о дополнительных маршрутах будет использовать дополнительные ресурсы вычислительной машины Алгоритм использует полный перебор всех вершин графа, что приведет к большой потери времени и займет больший объем памяти вычислительной машины (3).
Математическое представление транспортной системы
По публичным данным представленным на сайте метро, на март 2020 года Московский метрополитен насчитывает около 334 станций (238 станций метрополитена, 31 станция МЦК, 6 станций Московского монорельса, 55 станций Московских центральных диаметров) (4). Эту развитую систему можно представить в виде двунаправленного графа, где каждая станция метро представлена в виде вершины графа, а перегоны в виде ребер (Рис. 1, журнал «Этносоциум и межнациональная культура» 9 (147). 2020. Стр. 36). Каждая вершина графа будет иметь порядковое значение в соответствии с количеством станций (5).
Большинство пассажиров не задумываются о том, какой маршрут является оптимальным. В среднем пассажир каждый день перемещается по одному и тому же направлению и заранее планирует свою поездку. Благодаря современным гаджетам, пассажир с легкостью рассчитывает свой маршрут не задумываясь об алгоритмах их поиска.
Существует большой множество алгоритмов поиска кратчайшего пути по графу между двумя заданными точками. В качестве наиболее оптимального алгоритма предлагается использовать доработанный алгоритм Дейкстра, а именно алгоритм A* (A-star).
Данный алгоритм нашел широкое применение в видеоиграх для нахождения кратчайшего пути между двумя заданными точками. Его относят к информированным алгоритмам поиска, так как для решения задач используются данные о стоимости пути и принципы эвристики. Можно выделить два основных свойства:
- оптимальность, что означает что он гарантированно найдет наилучшее из возможных решений;
- полнота, то есть если решение существует, то алгоритм гарантированно его найдет. Также можно отметить, что алгоритм не просто стремимся найти кратчайшее расстояние, а также учитывает и его длительность движения (6).
Особенностью данного алгоритма является то, что он является более точным и не распространяется по всем вершинам графа в отличии от Дейкстры и использует эвристику, которая определяет порядок обхода вершин. В качестве эвристики предлагается использовать маршруты в статике и в качестве точек измерения расстояния использовать широту и долготу станций.
Для понимания работы алгоритма А* необходимо владеть следующими терминами:
- Узел (или вершина) — все потенциальные уникальные позиции или остановки;
- Переход — само перемещение между вершинами или узлами;
- Начальный узел — тот, от которого начинается путь;
- Конечный узел — тот, в котором путь должен завершиться;
- Пространство поиска — коллекция всех допустимых узлов;
- Стоимость — числовое значение (например, расстояние, время или денежная стоимость), характеризующее отрезок пути от одного узла к другому.
Каждый раз при посещении узла подсчитывается его стоимость f(n) (за n принимается соседний узел). Таким образом, алгоритм посещает все соседние узлы и высчитывает тот, у которого данный показатель минимален (7).
Реализацию алгоритма можно описать следующими этапами:
1. Создается два списка вершин – ожидающие рассмотрения и уже рассмотренные. В ожидающие добавляется точка старта, список рассмотренных пока пуст.
2. В процессе работы алгоритма для вершин рассчитывается функция стоимости:
f(n) = g(n) + h(n), где
g (n) – стоимость пути от начального узла до любого узла n
h (n) – эвристическая расчетная стоимость от узла n до целевого узла.
В нашем случае используется маршрут в статике и она имеет следующий вид:
h(n) =√((x1-x2)^2+(y1-y2)^2 )
Также каждая точка хранит ссылку на точку, из которой в нее пришли.
3. Из списка точек на рассмотрение выбирается точка с наименьшим F. Обозначим ее X.
4. Если X – цель, то мы нашли маршрут.
5. Переносим X из списка ожидающих рассмотрения в список уже рассмотренных.
6. Для каждой из точек, соседних для 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, журнал «Этносоциум и межнациональная культура» 9 (147). 2020. Стр. 39).
Загруженность линий на схеме обозначена цветами: от зеленого («слабая загруженность») до черного («очень сильная загруженность»). Почти полностью черной обозначена фиолетовая ветка метро. На эту схему не нанесен недавно открытый участок розовой ветки с переходом на станции «Лермонтовский проспект». Также большая загруженность наблюдается на участках синей ветки: от «Курской» до «Бауманской» и от «Киевской» до «Парка Победы». Меньше пассажиров в час пик ездят от станции «Строгино» до «Пятницкого шоссе».
Как можно наблюдать загруженность метро начинается с центра и начинает затухать ближе к к концу линий. Метросистема имеет кольцевую структуру, что позволяет произвести аналогию с волнами от капли воды на поверхности жидкости. Имея статистические данные о количестве пассажиров на одной из станций, проведем анализ данных. Линейный график временного ряда может дать глубокое понимание потока (Рис. 3, журнал «Этносоциум и межнациональная культура» 9 (147). 2020. Стр. 40).
На оси ординат находится кол-во пассажиров, а по абсцисс деление в час начиная с 21.09.2020 00:00. Опираясь на графика можно сделать вывод, что наблюдается тенденция потока. Это означает что события связанные с пассажиропотоком повторяются со временем. Подключим библиотеки pandas,sklearn,math в среде разработки Python. И найдем спрогнозированное значение потока на следующий час:
# load data
series = Series.from_csv('dataset.csv')
# prepare data
X = series.values
X = X.astype('float32')
train_size = int(len(X) * 0.50)
train, test = X[0:train_size], X[train_size:]
# walk-forward validation
history = [x for x in train]
predictions = list()
for i in range(len(test)):
# predict
yhat = history[-1]
predictions.append(yhat)
# observation
obs = test[i]
history.append(obs)
print('>Predicted=%.3f, Expected=%3.f' % (yhat, obs))
Вывод:
>Predicted=404, Expected=485
Далее присвоим веса для ребер графа в зависимости от загруженности станций метро. Как видно на графике пассажиропоток может достигать до 4000 человек в час. Разделим на четыре диапазона и зададим веса графа. (Табл. 1, журнал «Этносоциум и межнациональная культура» 9 (147). 2020. Стр. 41)
Для начала построим маршрут с учета весов и зональности метро до прогноза, построим маршрут Коммунарка - Алтуфьево для прохождения маршрута сквозь все зоны:
[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]
Как можно видеть на рис. 4 слева алгоритм беспрепятственно проходит сквозь все зоны загруженность и доходит до конечной точки.
Далее прогоним алгоритм еще раз по тому же маршруту с учетом прогноза:
[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]
Теперь мы наблюдаем иную картину на рис. 4 справа и можем сделать вывод, что граф начал обходить некоторые нагруженные ребра и предлагать более оптимальный маршрут.
Благодаря свой кольцевой структуре, пассажиропоток имеет поведение маятника, что обуславливает введение такого фактора как направленность пассажиропотока в зависимости от времени суток. Необходимо учитывать двунаправленность графа при управлении потоком и обеспечить прогноз в зависимости от направления движения пассажира (Рис. 5, журнал «Этносоциум и межнациональная культура» 9 (147). 2020. Стр. 44).
Таким образом, зная фактор загруженность метро можно управлять пассажиропотоками и правильно распределять нагрузку на общественный транспорт Москвы. Данный показатель может кардинально решить транспортную задачу Москвы дополнительную регулирую как мощность пассажиропотока так и его направление.
Заключение
В данной статье была наглядно рассмотрена методика распределения пассажиропотока на примере Московского метрополитена и предложен инструментарий по мониторингу и возможному распределению пассажиропотока внутри транспортной системы.
Список литературы:
1. Изотова Т.Ю., “Обзор алгоритмов поиска кратчайшего пути в графе” – Новые информационные технологии в автоматизированных системах, 2016. С. 341-344.
2. Ширшиков А.С., Вахидов Р.Р., Босалаев А.В., “Мониторинг пассажиропотоков в автомобильном общественном транспорте”, сборник научных трудов кафедры «Организация перевозок и управление на транспорте» в рамках Международной научно-практической конференции. Сибирская государственная автомобильно-дорожная академия (СибАДИ). 2016.
3. Елсуков В., Дерябин В., Шаманский БС. «Распределение пассажиропотоков на Ленинградском метрополитене», журнал «Метрострой», 1983. № 8.
4. Официальный сайт Московского метрополитена – Метрополитен в цифрах, 2019 // URL: https://mosmetro.ru/press/digits.
5. Таланов В.А. Нахождения кратчайших путей в графе // Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных. – Н. Новгород:Изд-во Нижегор. гос. ун-та, 2005. Гл. 3.4. С. 236-237.
6. Миков Е.П., Бондарь В.А. Алгоритм поиска пути из пункта а в пункт б*, 2017 - Сборник научных трудов нгту. 2017. № 2 (88). С. 33-40.