ANALYZING DATA ON PUBLIC TRANSPORT NETWORK STRUCTURE (CASE OF VOLGOGRAD)
Journal: VESTNIK OF ASTRAKHAN STATE TECHNICAL UNIVERSITY. SERIES: MANAGEMENT, COMPUTER SCIENCE AND INFORMATICS
№ 1
, 2022
Rubrics: MANAGEMENT, MODELING, AUTOMATION
Authors:
1.
Kamyshin Technological Institute, branch of Volgograd State Technical University
(Postgraduate Student of the Department of Automated Systems of Data Processing and Control)
Russian Federation
Russian Federation
2.
Kamyshin Technological Institute, branch of Volgograd State Technical University
(Doctor of Technical Sciences, Assistant Professor; Director;)
Russian Federation
Russian Federation
3.
Kamyshin Technological Institute, branch of Volgograd State Technical University
(Candidate of Technical Sciences; Professor of the Department of Automated Systems of Data Processing and Control)
Russian Federation
Russian Federation
4.
Kamyshin Technological Institute, branch of Volgograd State Technical University
(Candidate of Technical Sciences, Assistant Professor; Assistant Professor of the Department of Automated Systems of Data Processing and Control)
Russian Federation
Russian Federation
5.
Kamyshin Technological Institute, branch of Volgograd State Technical University
(Candidate of Technical Sciences, Assistant Professor; Assistant Professor of the Department of Automated Systems of Data Processing and Control)
Russian Federation
Russian Federation
Type:
Article
Pages:
from 33
to 41
Status:
Published
Received:
27.01.2022
Accepted:
28.01.2022
Published:
28.01.2022
Subject area:
UDK 004 Информационные технологии. Вычислительная техника...
Language:
Russian
Keywords:
public transport, population, number of inhabitants, route, transport network, stopping point, passenger, reachability of stops, the Floyd-Warshall algorithm
Funding:
public transport, population, number of inhabitants, route, transport network, stopping point, passenger, reachability of stops, the Floyd-Warshall algorithm
Abstract (English):
The paper is focused on collecting and analyzing the data on the population density in the districts of a megapolis was carried out. Each district is further divided into sections to improve the accuracy of the study. The analysis of data on the location of passenger public transport stops in residential areas and areas with socially significant objects was carried out. Visualization of the analysis results was performed by superimposing isochronous accessibility of the main objects of attracting passengers onto the map of the city. Using the algorithm of the minimum cstop of the way there have been found the points of destination in all the routes of the public transport network, which the passenger will be able to reach in 15 or 30 minutes. The route network is presented as a graph, whose vertices are public transport stops. The weights of the graph correspond to the travel time from one stop to another. The shortest paths between all vertices of the graph have been found. The Floyd-Warshell algorithm is selected for calculations. The obtained data are prepared for using them in the transport network model to solve a multi-criteria optimization problem. When adding a new vertex, it becomes possible to calculate a new route with minimal time cstops. Based on the results of the study, the initial data were prepared for constructing a model for generating data on the passenger traffic of urban land transport.
The paper is focused on collecting and analyzing the data on the population density in the districts of a megapolis was carried out. Each district is further divided into sections to improve the accuracy of the study. The analysis of data on the location of passenger public transport stops in residential areas and areas with socially significant objects was carried out. Visualization of the analysis results was performed by superimposing isochronous accessibility of the main objects of attracting passengers onto the map of the city. Using the algorithm of the minimum cstop of the way there have been found the points of destination in all the routes of the public transport network, which the passenger will be able to reach in 15 or 30 minutes. The route network is presented as a graph, whose vertices are public transport stops. The weights of the graph correspond to the travel time from one stop to another. The shortest paths between all vertices of the graph have been found. The Floyd-Warshell algorithm is selected for calculations. The obtained data are prepared for using them in the transport network model to solve a multi-criteria optimization problem. When adding a new vertex, it becomes possible to calculate a new route with minimal time cstops. Based on the results of the study, the initial data were prepared for constructing a model for generating data on the passenger traffic of urban land transport.
Keywords:
public transport, population, number of inhabitants, route, transport network, stopping point, passenger, reachability of stops, the Floyd-Warshall algorithm
public transport, population, number of inhabitants, route, transport network, stopping point, passenger, reachability of stops, the Floyd-Warshall algorithm
Введение
Одним из важнейших показателей системы транспортного обслуживания населения города [1], которые влияют на уровень удовлетворенности горожан, наряду со стоимостью проезда, комфортабельностью транспортных средств является время, затрачиваемое на дорогу. Данный показатель является составным и включает в себя следующие компоненты:
– время, затрачиваемое от дома до остановки общественного транспорта;
– время в пути;
– время от остановки прибытия до пункта назначения.
В ряде научных работ [2–4] решаются задачи оптимизации транспортной сети. В качестве исходных данных для построения транспортных моделей используются данные о существующих остановках общественного транспорта. В предлагаемых решениях реорганизации маршрутной карты города [5] при расчете времени пути не учитывается время, которое пассажир затрачивает на дорогу от пункта своего отправления до остановки общественного транспорта и от остановки прибытия до конечного пункта своего маршрута. Встречаются случаи, когда значительный временной интервал пешего пути оказывает более негативное влияние на удовлетворенность горожан уровнем жизни, чем значительное время в пути на общественном транспорте [6].
Для регулирования обеспеченности объектов городской инфраструктуры остановками пассажирского общественного транспорта в России разработан социальный стандарт транспортного обслуживания населения [7]. В данном документе установлены предельные расстояния кратчайшего пешеходного пути от границ участков объектов различного типа до остановочных пунктов.
Анализ плотности населения
Результаты анализа данных о структуре маршрутной сети пассажирского транспорта планируется использовать при построении модели генерации данных о пассажиропотоке на остановках общественного транспорта [8]. Для построения реалистичной модели необходимо определить количество человек, проживающих в пределах каждой из остановок городской транспортной сети.
Далее представлены данные исследования сети городского пассажирского транспорта на примере г. Волгограда, численность жителей которого приравнивается к 1 млн человек.
На первом этапе проведения исследования был выполнен анализ плотности населения города [9].
В качестве исходных данных были приняты официальные сведения о численности населения города, включая численность каждого из районов города.
Вся географическая территория, занимаемая городом, была разбита на тайлы в координатной системе UTM [10]. Размер каждого тайла 500 × 500 м. Общее число тайлов, занятых объектами городской инфраструктуры и относящихся к транспортной системе города, составило 1 020 шт.
Для определения численности населения территориально внутри каждого района были использованы открытые данные сервисов просмотра улиц (Google, Яндекс) и картографических данных (Google, Яндекс, 2GIS, OpenStreetMap). По полученным данным был произведен подсчет домов
в каждом из тайлов. При этом многоэтажные дома были сведены по численности жителей к одноэтажным с помощью коэффициентов этажности, количества квартир на этаже. Многоэтажный дом – это несколько (как правило, десятков) одноэтажных домов в одной точке, т. е. использовался механизм приведения всех домов к статусу индивидуальных домов.
Плотность распределения жителей по жилым домам в каждом районе города принималась константой (т. е. считается, что в каждом доме живет одинаковое число жителей для данного района) [11]. Погрешности измерения численности жителей (относительно официальных данных) по каждому из районов находятся в пределах от 0,1 до 1,7 %. Общая средняя погрешность определения численности – 0,6 %.
Основные источники полученной погрешности: расположение многоэтажного дома на границе тайлов, погрешность в подсчете домов. Общий вид плотности населения всего города представлен на рис. 1.
Рис. 1. Диаграмма плотности населения г. Волгограда
Fig. 1. Diagram of the distribution of the population density of Volgograd
Данные о численности жителей каждого тайла были распределены между остановочными пунктами в зависимости от близости домов к остановочному пункту. Пример распределения представлен в табл. 1.
Таблица 1
Table 1
Фрагмент распределения числа жителей тайла относительно остановок общественного транспорта
на отдельно взятом участке транспортной сети
A fragment of the distribution of the number of tile residents relative to public transport stops
on a particular section of the transport network
Название остановочного пункта Район города Число жителей в районе остановки
Ост_1 Район 1 6 472
Ост_2 Район 2 2 174
Ост_3 Район 2 312
Погрешность расчета численности жителей по районам города относительно общей численности населения составляет 0,02 %.
Из-за особенностей города авторами было введено несколько дополнений:
1. Два остановочных пункта введены искусственно. Они необходимы для моделирования пассажиропотока кольцевых маршрутов, их численность условная – 1/2 человека, что приведет к нулевому числу пассажиров на конечных остановочных пунктах кольцевых маршрутов.
2. Для ряда остановочных пунктов, расположенных в пределах дачных массивов, установлена численность менее 100 человек. Исходя из того, что официально на дачных участках никто не живет, но фактически это не так, было принято решение о назначении некоторого количества «условных жителей».
3. Количество жителей одного тайла пропорционально разделяется между остановками, расположенными в пределах данного тайла. Таким образом, указанная численность – это медианные значения.
Анализ рациональности расположения остановок на маршрутных линиях пассажирского общественного наземного транспорта и их доступности населению
Социальный стандарт транспортного обслуживания населения регламентирует расстояние кратчайшего пешеходного пути следования от ближайшей к остановочному пункту точки границы земельного участка, на котором расположен объект (жилой дом, предприятие торговли, больница или терминал внешнего транспорта) до ближайшего остановочного пункта.
Авторами проанализировано обеспечение выполнения норм пп. 3.1.1 данного социального стандарта маршрутами, которые обслуживаются муниципальным транспортным предприятием города Волгограда. Для удобного визуального представления полученные данные отражены на карте города. Рассматриваемый город имеет некоторые инфраструктурные особенности [12]. В маршрутной схеме выделяются опорные и вспомогательные маршруты в соотношении 1 : 3 соответственно.
В качестве примера выполнения норм предельных расстояний кратчайшего пешеходного пути следования пассажира от ближайшей к остановочному пункту точки границы земельного участка,
на котором расположены жилые дома, до ближайшего остановочного пункта, который обслуживается регулярным маршрутом, рассмотрим расположение остановок в жилых зонах одного из поселковых поселений.
Установленное нормативное значение расстояния кратчайшего пешеходного пути для индивидуального жилого дома – не более в 800 м (для г. Волгограда может также применяться норма, которая допускается для субъектов Российской Федерации
с особыми природно-климатическими условиями,
в 700 м); для многоквартирного дома установлено значение не более 500 м (400 м для г. Волгограда).
На рис. 2 приведены зоны, покрываемые остановочными пунктами, по маршрутам, обслуживаемым транспортным предприятием: окружности со штриховкой соответствуют территории радиусом
в 800 м (вторая внутренняя окружность 700 м) –
в зонах индивидуальных жилых домов; окружности, залитые сплошным цветом, обозначают территории радиусом в 500 м (вторая внутренняя окружность 400 м) – в зонах многоэтажных домов; центры окружностей – остановочные пункты маршрутов М, Q, проходящих через остановки, расположенные на рис. 2, обозначенные точками.
Рис. 2. Охват жилых зон транспортной инфраструктурой в районе поселка P (маршруты М, Q)
Fig. 2. Coverage of residential areas with transport infrastructure around the village P (routes М, Q)
Маршруты транспортного предприятия охватывают достаточно большое количество жилых домов, это связано, прежде всего, с особенностями расположения жилых домов и дорог. По результатам исследования обеспеченность территории поселковых поселений остановками общественного транспорта в выражении на число жителей поселковых поселений составляет 63,7 %.
На основе данных о достижимости объектов городской инфраструктуры различных типов (жилой дом, предприятие торговли, больница или терминал внешнего транспорта) были построены так называемые «изохроны» (рис. 3), на изохронах большими окружностями показаны объекты «притяжения» пассажиропотока, малыми – достижимые остановки на маршрутной сети, затемненная область соответствует 15-минутной изохроне, более светлая область – 30-минутной изохроне (рис. 3).
Рис. 3. Карта доступности объекта «притяжения» пассажиров
Fig. 3. The map of the object of passenger attraction accessibility
В данном случае изохроны показывают доступность основных объектов «притяжения» пассажиров (т. е. объектов с высокой концентрацией посетителей, например торговые центры, больницы, крупные предприятия) за два промежутка времени: 30 и 15 минут. При построении изохрон учитывается расположение остановок общественного транспорта на имеющихся маршрутах. Из анализа изохрон следует, что маршрутная сеть позволяет пассажирам за
30 минут перемещаться между основными аттракторами. В каждой 30-минутной изохроне находятся медучреждения и торговые предприятия.
Расчет маршрутов с минимальными временными затратами
Данные, полученные в ходе анализа общей достижимости остановок, являются основой для построения транспортной модели генерации данных
о транзакциях пассажиров между остановками общественного транспорта [13]. Так, в состав критерия оптимизации сети общественного транспорта входит такой пункт, как уменьшение времени, затраченного пассажиром на поездку.
Для составления маршрутной карты с минимальными временными затратами авторами было предложено пассажирскую транспортную сеть представить на основе теории графов и произвести расчет
с помощью алгоритма Флойда–Уоршелла [14], который позволит определять кратчайшие пути между всеми остановками общественного транспорта.
Для выполнения алгоритма Флойда–Уоршелла требуется построить две матрицы:
– матрицу весов графа маршрутной сети G, соответствующую времени перемещения между остановками общественного транспорта , где w – время передвижения между двумя остановками; i – остановка отправления; j – остановка прибытия; k – порядковый номер матрицы;
– матрицу путей , где p – номера возможных остановок прибытия; k – порядковый номер матрицы.
Заполнение начальной матрицы весов W(0) происходит следующим образом: элементу wij присваивается время в пути от остановки отправления
i до остановки прибытия j.
Далее wij присваивается значение ∞, если в графе нет ребра (i, j), ориентированного из i-й вершины в j-ю.
Элемент во всех случаях, когда i = j.
На основании исходной матрицы W(0) по алгоритму происходит формирование последовательности матриц , , ..., , ..., . Составляющими элементами конечной матрицы являются элементы wij(min), которые соответствуют кратчайшим расстояниям между i-й и j-й вершинами в графе G.
Матрица весов W(k) рассчитывается на основании матрицы W(k–1). Формула для расчета каждого элемента новой матрицы выглядит следующим образом:
.
Одной матрицы весов W(k) недостаточно для решения задачи. В дополнение к ней формируется матрица путей P(k). Данная матрица используется для того, чтобы помимо кратчайших расстояний сформировать последовательности переходов от одной вершины к другой, т. е. пути. Исходная матрица путей P(0) содержит элементы, которые образуются по принципу, приведенному ниже:
– элементу pij(0) присваивается значение i в том случае, если соответствующий элемент wij(0) в матрице весов W(0) графа G не равен ∞ и не является одним из элементов основной диагонали матрицы;
– во всех остальных случаях элементу pij(0) матрицы путей P(0) присваивается значение 0.
Расчет последовательности матриц путей P(1), P(2), ..., P(k), ..., P(m) происходит одновременно
с расчетом матриц весов. Согласно алгоритму Флойда–Уоршела в итоговой матрице путей P(m) элемент матрицы pij(m) соответствует вершине, которая является предшествующей вершине j в кратчайшем пути от i-й к j-й вершине. Кратчайший путь от i-й вершины до j-й вершины формируется из последовательности вершин i, ..., u – 2, u – 1, u, j, где u = pij(m), u – 1 = piu(m), u – 2 = pu,u-1(m) и т. д., пока не дойдет до начальной вершины i.
Далее рассмотрим работу алгоритма Флойда–Уоршелла для участка маршрутной сети общественного транспорта. Алгоритм позволит рассчитать время в пути от каждого остановочного пункта до каждой возможной остановки. При этом при работе программы расчеты будут произведены один раз, не потребуется задействовать ресурсы компьютера каждый раз при выборе конкретной остановки для расчета стоимости пути (в отличие, например, от алгоритмов Дейкстры или Форда–Беллмана).
При расчетах выбран шаг расчетной сетки –
20 м, скорость автобусов на маршруте – 20 км/ч, скорость пешехода вне дорог – 2 км/ч. Характеристики дорожной сети считались неизменными (пропускная способность, уровень загруженности, отсутствует взаимное влияние пользователей транспортной сети).
На первом этапе был составлен граф для каждого из существующих маршрутов транспортной сети г. Волгограда (G, где m – номер маршрута). У каждого графа имеется Nm вершин. Каждый граф является ориентированным, т. к. имеются кольцевые маршруты, по которым транспортные средства движутся только в одном направлении. На графе обозначены следующие элементы:
– вершины, соответствующие существующим остановкам транспортной сети (обозначены по номеру остановки в общем перечне остановок – Stop1, Stop2, Stop3, …, StopN);
– ребра графа, которые соответствуют пути от остановки до остановки каждого маршрута;
– веса – время, затрачиваемое на дорогу от одной остановки маршрута до другой (в минутах).
Алгоритм может применяться не только для расчета времени на перемещение транспортных средств по существующим маршрутам, но также для оценки временных затрат при добавлении новой остановки на линию.
Пример участка маршрутной сети, представ-ленного в виде совокупности графов с введенной остановкой (stop 6), отражен на рис. 4.
Рис. 4. Участок транспортной сети, представленный в виде графов
Fig. 4. Section of the transport network shown in graphs
Линии разного типа соответствуют трем различным маршрутам. Двойной линией обозначены возможные пути от вводимой остановки.
В первую очередь составляются начальные матрицы весов и пути для данного участка маршрутной сети, с учетом новой предполагаемой остановки (табл. 2, 3).
Таблица 2
Table 2
Начальная матрица весов W0
Initial Weight Matrix W0
Stop1 Stop2 Stop3 Stop4 Stop5 Stop6
Stop1 0 1 ∞ ∞ ∞ ∞
Stop2 1 0 3 2 ∞ ∞
Stop3 ∞ 3 0 2 ∞ 6
Stop4 ∞ 2 2 0 3 ∞
Stop5 ∞ ∞ ∞ 3 0 1
Stop6 ∞ ∞ 6 ∞ 1 0
Таблица 3
Table 3
Начальная матрица путей P0
Initial Path Matrix P0
Stop1 Stop2 Stop3 Stop4 Stop5 Stop6
Stop1 1 1 0 0 0 0
Stop2 2 2 2 2 0 0
Stop3 0 3 3 3 0 3
Stop4 0 4 4 4 4 0
Stop5 0 0 0 5 5 5
Stop6 0 0 6 0 6 6
На следующем этапе с помощью алгоритма Флойда–Уоршелла рассчитывается расстояние
и путь между всеми вершинами графа (табл. 4, 5).
Таблица 4
Table 4
Конечная матрица весов W(min)
Terminal Weight Matrix W(min)
Stop1 Stop2 Stop3 Stop4 Stop5 Stop6
Stop1 0 1 4 3 6 7
Stop2 1 0 3 2 5 6
Stop3 4 3 0 2 5 6
Stop4 3 2 2 0 3 4
Stop5 6 5 5 3 0 1
Stop6 7 6 6 4 1 0
Таблица 5
Table 5
Конечная матрица путей P(min)
Terminal Path Matrix P(min)
Stop1 Stop2 Stop3 Stop4 Stop5 Stop6
Stop1 1 1 2 2 2, 4 2, 4, 5
Stop2 2 2 2 2 4 4, 5
Stop3 2 3 3 3 4 3
Stop4 2 4 4 4 4 5
Stop5 4,2 4 4 5 5 5
Stop6 5, 4, 2 5, 4 6 5 6 6
Заключительный этап предполагает построение изохрон достижимости городских объектов от каждого пункта, выбранного пользователем.
Из анкетирования населения, выполненного
в смежных работах, наиболее существенными проблемами в сфере транспортного обслуживания населения автобусными маршрутами, по мнению горожан, являются интервалы движения автобусов
и стоимость проезда. Исходя из выполненного анализа и с учетом анкетирования транспортному предприятию города рекомендуется:
– обеспечить на опорных маршрутах, обслуживаемых предприятием, интервальность движения транспортных средств не более 10 минут;
– рассмотреть вариант паритетности охвата социальных объектов и поселковых поселений между всеми крупными перевозчиками в городе, тем самым снизив количество малоэффективных маршрутов и одновременно не нарушив выполнение показателей социального стандарта.
Заключение
В ходе проведения анализа структуры маршрутной сети общественного транспорта на примере г. Волгограда были собраны данные для создания модели генерации данных о пассажиропотоке. Разработанный алгоритм определения численности населения городских участков позволяет рассчитать количество жителей каждого района города
с незначительной средней погрешностью (0,6 %).
При анализе изохрон достижимости объектов городской инфраструктуры г. Волгограда выявлено, что существующая маршрутная сеть позволяет пассажиру в течение 30 минут добраться до объектов социального значения (например, медучреждения).
Применение теории графов для анализа маршрутной карты города позволило оценить временные затраты пассажиров на перемещения между существующими остановками общественного транспорта. Алгоритм Флойда–Уоршелла позволит рассчитать новые маршруты транспортной сети с минимальными временными издержками при добавлении новых остановок общественного транспорта
1. Bai Y., Sun Z., Zeng B., Deng J., Li C. A multi-pattern deep fusion model for short-term bus passenger flow forecasting // Applied Soft Computing. 2017. N. 58. P. 669-680.
2. Huang Z., Li Q., Li F., Xia J. A novel bus-dispatching model based on passenger flow and arrival time prediction // IEEE Access. 2019. N. 7. P. 106453-106465. DOIhttps://doi.org/10.1109/ACCESS.2019.2932801.
3. Katrakazas C., Quddus M., Chen W., Deka L. Real-time motion planning methods for autonomous on-road driving: State-of-the-art and future research directions // Transportation Research Part C: Emerging Technologies. 2015. N. 60. P. 416-442. DOIhttps://doi.org/10.1016/j.trc.2015.09.011.
4. Loder A., Ambühl L., Menendez M., Axhausen K. W. Empirics of multi-modal traffic networks - using the 3D macroscopic fundamental diagram // Transportation Re-search Part C: Emerging Technologies. 2017. N. 82. P. 88-101. DOIhttps://doi.org/10.1016/j.trc.2017.06.009.
5. Hirano K., Kitao Y. A study on connectivity and accessibility between tram stops and public facilities // Am. J. Epidemiol. 2009. N. 171 (2). P. 247-264.
6. Katrakazas C., Quddus M., Chen W., Deka L. Real-time motion planning methods for autonomous on-road driving: State-of-the-art and future research directions // Transportation Research Part C: Emerging Technologies. 2015. N. 60. P. 416-442. DOIhttps://doi.org/10.1016/j.trc.2015.09.011.
7. Social'nyy standart transportnogo obsluzhiva-niya naseleniya pri osuschestvlenii perevozok passazhirov i bagazha avtomobil'nym transportom i gorodskim nazemnym elektricheskim transportom (utv. rasporyazheniem Ministerstva transporta RF ot 31 yanvarya 2017 g. № NA-19-r). URL: https://www.garant.ru/products/ipo/prime/doc/71508414/ (data obrascheniya: 17.11.2021).
8. Gonzalez M. C., Hidalgo C. A., Barabasi A.-L. Understanding individual human mobility patterns // Nature. 2008. N. 453 (5). P. 779-782.
9. Bure V. M., Mazalov V. V., Plaksina N. V. Estimating passenger traffic characteristics in transport systems // Automation and Remote Control. 2015. N. 76. P. 1673-1680.
10. Calabrese F., Diao M., Lorenzo G. D., Ferreira J. Understanding individual mobility patterns from urban sensing data: a mobile phone trace example // Transportation Research Part C Emerging Technologies. 2013. N. 26. P. 301-313.
11. Maghraoui O. A., Vallet F., Puchinger J., Bernard Y. Modeling traveler experience for designing urban mobility systems // Design Science. 2019. N. 5. DOIhttps://doi.org/10.1017/dsj.2019.6.
12. Krushel E. G., Stepanchenko I. V., Panfilov A. E., Berisheva E. D. An experience of optimization approach application to improve the urban passenger transport structure // Communications in Computer and Information Science. 2014. N. 466. P. 27-39. DOIhttps://doi.org/10.1007/978-3-319-11854-3_3.
13. Krushel E., Stepanchenko I., Panfilov A., Lyutaya T. Detection of the Patterns in the Daily Route Choices of the Urban Social Transport System Clients Based on the Decoupling of Passengers’ Preferences Between the Levels of Uncertainty // Creativity in Intelligent Technologies and Data Science. CIT&DS 2019. V. 1083. URL: https://doi.org/10.1007/978-3-030-29743-5_14 (data obrascheniya: 17.11.2021).
14. Lian H., Chen C., Chang J., Shen C., Jan R. Shortest path routing with reliability requirement in delay tolerant networks // 1st International Conference on Future Information Networks, ICFIN 2009. IEEE Xplore. 2009. P. 292-297. DOIhttps://doi.org/10.1109/ICFIN.2009.5339556
