=Paper=
{{Paper
|id=Vol-2391/paper9
|storemode=property
|title=Public transport route planning in the stochastic network based on the user individual preferences
|pdfUrl=https://ceur-ws.org/Vol-2391/paper9.pdf
|volume=Vol-2391
|authors=Aleksandr Borodinov,Alexander Yumaganov,Anton Agafonov
}}
==Public transport route planning in the stochastic network based on the user individual preferences ==
https://ceur-ws.org/Vol-2391/paper9.pdf
Public transport route planning in the stochastic
network based on the user individual preferences
A A Borodinov1, A S Yumaganov1 and A A Agafonov1
1
Samara National Research University, Moskovskoe Shosse 34А, Samara, Russia,
443086
e-mail: ant.agafonov@gmail.com
Abstract. Nowadays transport systems becomes more and more complex.
Therefore, passengers have difficulty with route planning due to the variety of
possible ways to get from the starting point to the destination one. Since the travel
time often not considered as single and main criteria by passengers, it is important to
take into account their own preferences which may be very different. In this paper,
we proposed a stochastic route planning algorithm, which considers the user
individual preferences. This method is based on the modified Dijkstra’s algorithm.
The proposed algorithm is tested using real public transport dataset obtained from
the transportation network of Samara, Russia.
1. Introduction
Congestion of transport networks is growing everywhere. It is caused both by an increase
in the number of the vehicle in large metropolitan areas and by the a prior unpreparedness
of the road infrastructure created in the past to modern flows. This makes it increasingly
important to solve navigation problems associated with the problems of choosing the optimal
route on personal and public transport. There are many systems and applications for navigation
(Yandex.Navigator and others). However, they work with a simplified static transport network
graph (instead of a stochastic time-dependent graph), do not take into account predictive
information about the public transport movement when building traffic routes, and do not
consider user preferences for solving navigation problems. All this leads to the fact that decision-
making by the user (especially on the usual traffic routes) is carried out according to subjective
criteria and, often, differs from the optimal one. The solution of these problems will reduce
the total time of transport correspondence in the network, increase user satisfaction and the
transport infrastructure efficiency as a whole.
The article is structured as follows. The first section briefly provides a literature overview on
finding the optimal route for public transport in time-dependent deterministic and stochastic
transport networks. The second section describes the transport network model. The third
section provides the proposed algorithm for calculating the optimal way for public transport
in the stochastic network, taking into account the predictive information about the vehicles
arrival time and using the individual participant preferences. The fourth section presents the
formulation and results of experimental studies. In conclusion, presents the conclusion and
possible directions for further research.
V International Conference on "Information Technology and Nanotechnology" (ITNT-2019)
Image Processing and Earth Remote Sensing
A A Borodinov, A S Yumaganov and A A Agafonov
2. Literature review
Existing navigation systems mainly work with static transport networks, i.e. suggest that the
travel time of the road segments is constant and does not depend on the time of day, weather
conditions and other factors. Because the road situation is not static, to improve the movement
time estimation accuracy, it is necessary to take into account the dynamic and stochastic traffic
flows characteristics.
A routing methods overview in time-dependent transport networks is provided in [1].
Hierarchical routing [2] and bidirectional algorithm A* [3] were used to speed up routing
algorithms.
The multicriterial algorithm for finding the shortest path in the stochastic network A* was
presented in [4]. It was assumed in the paper that the transit time values of adjacent road
segments are correlated.
Modern methods for solving the navigation problem in stochastic time-dependent transport
networks simulate the road segments transit time as a random variable with a time-dependent
distribution function [5, 6, 7].
A separate task is to combine the routeing reliability and the expected time of movement.
Most works use the average risk model [8, 9], which takes into account the average and variance
of the road segments travel time within a linear objective function that needs to be optimized.
The objective function coefficients are often chosen heuristically based on experimental studies.
The main problem in multimodal transport systems is a uniform information combination
about the various movement modes [10]. The most common approach is to build a transport
network graph, in which various traffic routes are connected by edges, meaning transplants at
stopping points.
Moreover, it is necessary to take into account the importance of user individual preferences,
when routing in multimodal transport systems. Often travel time is not the only criterion for
choosing a route. The transfers number, fare, vehicles waiting time, etc. should be taken into
account. [11]. Therefore, multi-criteria optimization algorithms should be used to improve
accuracy.
A research separate area is finding the optimal navigation strategy, which is a hierarchical
rule for deciding the further route choice based on actual passenger transport movement data.
The spatial and temporal stochastic transit time dependencies of road segments are investigated
in [12]. In the article [13] the authors included actual information on the movement of the
vehicle in the navigation strategy.
In the article [14] presented an algorithm for finding the shortest path on public transport,
taking into account dynamic and stochastic information about the movement of the vehicle.
Emphasis is placed on the practical implementation of the algorithm. The article [15] presents a
routing algorithm that simultaneously takes into account the stochastic transit time of the road
segments and the vehicles waiting time and optimizes both the routes speed and reliability.
This paper presents an algorithm for calculating the optimal way for public transport in a
stochastic network. In contrast to [14, 15], the arrival time is used to take into account waiting
times based on current and predicted information on the movement of the vehicle, instead of
the vehicles movement frequency. In addition, the algorithm takes into account user preferences
when choosing the parameters of the target optimization function.
3. Transport Network Model
The transport network will be considered as a directed graph G = (N, E), vertices ni ∈ N of
which correspond to stops, edges ei j ∈ E, i ∈ V, j ∈ V - to segments of the transport network
with length |eij |, each stop being represented by at least three vertices of the graph.
We introduce the following notation: Sk - stop from set S; Ri - passenger transport route
from the set R.
V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 67
Image Processing and Earth Remote Sensing
A A Borodinov, A S Yumaganov and A A Agafonov
The part of the graph representing the two routes R1 and R2 , containing the common stop
Sk , is shown in figure 1.
emove ewait emove
R1
eout earr
Sk
eout earr
emove ewait emove
R2
Figure 1. The route network graph structure.
The graph contains edges of several types:
• emove - represents the segment of the route between stops, characterized by the average time
µij and the dispersion σij ;
• ewait - waiting for passengers boarding/alighting at the bus stop, in the work, constant
waiting time is used as the edge weight;
• eout - alighting edge, in the work as the edge weight is used constant alighting time;
• earr - boarding edge (vehicle waiting) is determined by the vehicle arrival time of the
corresponding route to stop;
• ewalk (not shown in the figure) - walk from stops to the points of departure/arrival, the edge
weight depends on the transition distance;
The route finding task is reduced to the task of finding the shortest path in the graph. The
algorithm for solving the problem in a time-dependent stochastic transport network, taking into
account the road users individual preferences, is presented in the next section.
4. Algorithm for finding the shortest path
Dijkstra’s modified algorithm is used to find the shortest path in a time-dependent stochastic
transport network [14] (algorithm 1).
The algorithm uses the pair (ni , costi ) as the vertex label li , containing the vertex ni and
the multidimensional route price costi , which must be spent to reach the vertex ni from the
departure vertex ns . The route price is represented as a pair costi = (ci , ti ), where ci - the
generalized price, ti - the trip time.
The queue with priority pq determines the next vertex to be viewed based on the generalized
price ci . Associative arrays predM ap and costsM ap respectively are used to store the previous
vertex for the given and the trip price to the specified vertex.
In the algorithm, the getCost() and getTime() functions - getting the generalized price ci and
time ti from the price of reaching the vertex costi .
The main interest is the estimation obtaining function of the passing the graph edge price
calculateCost(). The proposed method for determining the cost of an edge depending on its
type is described in Algorithm 2. In algorithm 2, the following notation is used:
• twait = 30 (seconds) - alighting/boarding time;
• tout = 10 (seconds) - alighting time;
V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 68
Image Processing and Earth Remote Sensing
A A Borodinov, A S Yumaganov and A A Agafonov
Algorithm 1: Algorithm for finding the shortest path
Input data: departure vertex ns , arrival vertex nd ,
departure time t
Output data: shortest path
// Initialization
PriorityQueue pq = ∅
Map predM ap = ∅
Map costsM ap = ∅
Label ls = Label(ns , costs )
pq.insert(ls )
while !pq = ∅ do
Label li = pq.pop()
ni = li .getNode()
foreach eij ∈ E do
costj = calculateCost(eij , t + li .getCost().getTime())
if costj .getCost() > costsM ap.get(ni ).getCost() then
continue;
end
costsM ap.put(nj , costj )
predM ap.put(nj , ni )
Label lj = Label(nj , costj )
pq.insert(lj )
end
end
• tarr - the vehicle arrival estimated time at the stop;
• swalk = 1 (m/s) - walking speed;
• α0 , α1 , α2 -individual preferences parameters that affect the reliable path choice, the
transfers number and walking distance.
5. Experiment
Experimental studies of the developed method were carried out for the Samara street-road
network. The road network consists of 48139 segments. The data on the passenger transport
bus routes movement were used to predict the time of arrival.
Six pairs of different departure and arrival vertices on the transport network graph were
chosen to study the algorithm quality, after which for each pair they solved the problem of
finding a way on public transport, varying the departure time.
Two standard metrics were used to compare the prediction quality: Mean Absolute
Percentage Error (MAPE) and Mean Absolute Error (MAE).
N
1 X |ti − t̂i |
MAPE = × 100%
N ti
i=1
N
1 X
MAE = |ti − t̂i |
N
i=1
where ti - is the actual route time value, t̂i - the predicted value, N - number of experiments.
V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 69
Image Processing and Earth Remote Sensing
A A Borodinov, A S Yumaganov and A A Agafonov
Algorithm 2: calculateCost
Input data: graph edge ei j, arrival time t to the vertex i
Output data: cost costj = (cj , tj )
if eij is emove then
// route segment between stops
√
return (µij + α0 σij , µij );
end
else if eij is ewait then
// alighting/boarding
return (twait , twait );
end
else if eij is eout then
// alighting
return (tout , tout );
end
else if eij is earr then
// waiting for transport
return (α1 (tarr − t), tarr − t);
end
else if eij is ewalk then
// foot transition
return (α2 |eij |/swalk , |eij |/swalk );
end
The average trip time was tavg = 2645 seconds. The following values were obtained from the
experimental analysis results: M AP E = 6.62%, M AE = 179.8 seconds. The obtained values
allow us to conclude about the good quality of the proposed algorithm..
6. Conclusion
The paper presents an algorithm for calculating the shortest path on public transport in a
stochastic time-dependent transport network that takes into account the average time and
variance of the road segment travel time when building a route. The proposed algorithm uses
real-time data and forecast data on the movement of vehicles to estimate the waiting time for
public transport at bus stops. Algorithm parameters are selected according to individual user
preferences.
Experimental analysis of the proposed algorithm showed high accuracy in estimating the time
of movement, which is close to real time along the selected route.
A further work direction includes comparing the proposed algorithm with other algorithms
for solving the navigation problem, as well as modifying the edge weight estimating function to
increase the found route reliability of motion.
7. References
[1] Delling D and Wagner D 2009 Time-dependent route planning Lecture Notes in Computer
Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in
Bioinformatics) 5868 207-230
[2] Delling D and Nannicini G 2012 Core routing on dynamic time-dependent road networks
INFORMS Journal on Computing 24 187-201
V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 70
Image Processing and Earth Remote Sensing
A A Borodinov, A S Yumaganov and A A Agafonov
[3] Nannicini G, Delling D, Schultes D and Liberti L 2012 Bidirectional A* search on
time-dependent road networks Networks 59 240-251
[4] Chen B Y, Lam W H K, Sumalee A and Li Z -l. 2012 Reliable shortest path finding in
stochastic networks with spatial correlated link travel times International Journal of
Geographical Information Science 26 365-386
[5] Miller-Hooks E D and Mahmassani H S 2000 Least expected time paths in
stochastic, time-varying transportation networks Transportation Science 34 198-215
[6] Sun S, Duan Z, Sun S and Yang D 2014 How to find the optimal paths in stochastic time-
dependent transportation networks? 17th IEEE International Conference on Intelligent
Transportation Systems, ITSC 2348-2353
[7] Agafonov A A and Myasnikov V V 2016 Method for the reliable shortest path search in
time-dependent stochastic networks and its application to GIS-based traffic control Computer
Optics 40(2) 275-283 DOI: 10.18287/2412-6179-2016-40-2-275-283
[8] Lim S, Sommer C, Nikolova E and Rus D 2013 Practical route planning under delay
uncertainty: Stochastic shortest path queries Robotics: Science and Systems 8 249-256
[9] Nikolova E 2010 Approximation algorithms for reliable stochastic combinatorial
optimization Lecture Notes in Computer Science (including subseries Lecture Notes in
Artificial Intelligence and Lecture Notes in Bioinformatics) 6302 338-351
[10] Grasman S E 2006 Dynamic approach to strategic and operational multimodal routing
decisions International Journal of Logistics Systems and Management 2 96-106
[11] Grbener T, Berro A and Duthen Y 2010 Time dependent multiobjective best path for
multimodal urban routing Electronic Notes in Discrete Mathematics 36 487-494
[12] Gao S, Frejinger E and Ben-Akiva M 2010 Adaptive route choices in risky traffic networks:
A prospect theory approach Transportation Research Part C: Emerging Technologies 18
727-740
[13] Wu C, Zhang X and Dong Y 2014 Adaptive route guidance based on real-time
information in stochastic time-dependent transportation networks 17th IEEE International
Conference on Intelligent Transportation Systems, ITSC 2392-2397
[14] Demeyer S, Audenaert P, Pickavet M and Demeester P 2014 Dynamic and stochastic
routing for multimodal transportation systems IET Intelligent Transport Systems 8 11223
[15] Ni P, Vo H T, Dahlmeier D, Cai W, Ivanchev J and Aydt H 2015 DEPART:
Dynamic Route Planning in Stochastic Time-Dependent Public Transit Networks IEEE Conference
on Intelligent Transportation Systems, Proceedings, ITSC 16727
Acknowledgments
The reported study was funded by the Ministry of Science and Higher Education of the Russian
Federation (unique project identifier RFMEFI57518X0177).
V International Conference on "Information Technology and Nanotechnology" (ITNT-2019) 71