Nowadays transport systems becomes more and more complex. Therefore, passengers have di culty 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 di erent. In this paper, we proposed a stochastic route planning algorithm, which considers the user individual preferences. This method is based on the modi ed Dijkstra's algorithm. The proposed algorithm is tested using real public transport dataset obtained from the transportation network of Samara, Russia.
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 ows. 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 simpli ed 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 tra c routes, and do not consider user preferences for solving navigation problems. All this leads to the fact that decisionmaking by the user (especially on the usual tra c routes) is carried out according to subjective criteria and, often, di ers 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 e ciency as a whole.
The article is structured as follows. The rst section brie y provides a literature overview on nding 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.
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 tra c ows characteristics.
A routing methods overview in time-dependent transport networks is provided in [
The multicriterial algorithm for nding the shortest path in the stochastic network A* was
presented in [
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 [
A separate task is to combine the routeing reliability and the expected time of movement.
Most works use the average risk model [
The main problem in multimodal transport systems is a uniform information combination
about the various movement modes [
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. [
A research separate area is nding 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 [
In the article [
This paper presents an algorithm for calculating the optimal way for public transport in a
stochastic network. In contrast to [
The transport network will be considered as a directed graph G = (N; E), vertices ni 2 N of which correspond to stops, edges eij 2 E; i 2 V; j 2 V - to segments of the transport network with length jeij j, 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.
The part of the graph representing the two routes R1 and R2, containing the common stop Sk, is shown in gure 1.
R
1 R 2 e
move e move e
out e out e
wait e wait
S k e
arr e arr e
move e
move
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 gure) - walk from stops to the points of departure/arrival, the edge weight depends on the transition distance;
The route nding task is reduced to the task of nding 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 nding the shortest path
Dijkstra's modi ed algorithm is used to nd the shortest path in a time-dependent stochastic
transport network [
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 speci ed 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;
Algorithm 1: Algorithm for nding 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 2 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 a ect the reliable path choice, the transfers number and walking distance.
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 di erent 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 nding 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).
MAPE =
100% 1 XN jti N i=1 ti ^ tij MAE = 1 XN jti N i=1 ^ tij where ti - is the actual route time value, t^i - the predicted value, N - number of experiments.
Algorithm 2: calculateCost
Input data: graph edge eij, arrival time t to the vertex i Output data: cost costj = (cj ; tj ) if eij is emove then // route segment between stops return ( ij + 0p 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 end
return ( 2jeij j=swalk; jeij j=swalk);
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..
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. Acknowledgments The reported study was funded by the Ministry of Science and Higher Education of the Russian Federation (unique project identifier RFMEFI57518X0177).