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