Acceleration of the reliable shortest path algorithm in a time-dependent stochastic transport network

Abstract

In this paper, we propose a modification of the reliable routing algorithm in a stochastic time-dependent network. We consider a stochastic ontime arrival problem. Reliability means maximization the probability of arrival at a destination within a given period of time. Modification of the shortest-path algorithm is aimed to decrease the computation time of the algorithm. The base idea of the proposed modification is to select a certain subset of nodes and links of the graph which can be used for calculating the shortest path. We propose two methods for selecting subset of nodes: based on a bounding box and based on the k-shortest path algorithm. Experimental studies of the base and modified algorithms are carried out on the transport network of Samara, Russia.

Keywords

• reliable shortest path
• adaptive route
• time-dependent network
• k shortest path algorithm

1. Introduction

Road congestion is a serious problem of modern society, which has several significant consequences. For traffic participants congestion reduces quality of life, consuming their free time. For organizations, congestion reduces employee productivity and increases freight transportation costs. For the society as a whole, traffic jams lead to the disruption of emergency services, and negatively affects the quality of the environment, causing a large amount of exhaust emissions. Traffic jams threaten traffic safety, raising the level of stress and fatigue among drivers. Thus, it becomes increasingly important to solve the optimal routing navigation problems.

In recent decades, a large number of papers have been devoted to the shortest path problem in transport networks. However, most of them focused their attention on finding the least expected travel time. Several types of models are distinguished depending on the weight type of the road segment. In classical models [ 1,2,3 ], the travel time of a road segment is considered to be constant or time-dependent. At the same time, the real situation shows that the travel time is continuously changing and depends on many factors such as time of day, weather conditions, traffic situation, etc. In models with stochastic travel time [ 4,5,6 ], the time is represented by a random variable with a time-dependent distribution function. In either case, the optimality condition for routing can be determined in different ways depending on the used objective function. The following types of objective functions can be used: 1) minimization of the least expected travel time [ 4 - 7 ]; 2) maximization of the probability of arriving at the destination at a predetermined time interval [ 8, 9 ]; 3) maximization of the probability that travel time is less than a given threshold [ 10, 11 ]; 4) minimization of the worst possible travel time [ 12 ]; 5) minimization of the travel time to guarantee a given likelihood of arriving on-time in a stochastic network [ 13 ].

These types of objective functions can be divided into two groups: the least expected time (LET) (1) and the reliable shortest path (RSP) problem (2-5). The LET problem has been well studied, there are many effective algorithms for different types of the problem [ 6,7 ]. Nevertheless, in a number of practical tasks, the path with the least expected time may not be suitable, since it does not take into account the dispersion of the travel time and does not give any guarantees of reliability. In many cases, road users decided to increase travel time and to choose a more reliable route [ 8 ]. The problem of finding a reliable shortest path was investigated in [ 10, 11 ]. In [ 14, 15 ], a shortest path algorithm was proposed, taking into account current and predictive information about the transport flows in the network, which is a modification of the algorithm from [ 8 ]. However, the algorithms described in the works are computationally complex and cannot be used to determine the shortest path in large-scale networks in real time.

In this paper, we investigate the method for reliable routing in a time-dependent stochastic transport network. We consider the following optimality criterion: maximizing the probability of arrival at a destination within a predetermined time interval. The aim of this work is to decrease the computation time of the existing algorithm. Acceleration of the algorithm is achieved by choosing a subset of the graph nodes used to find the shortest path. The algorithm proposed by the group of authors in [ 8 ] is used as a basic algorithm.

The paper is organized as follows. The second section introduces the basic notation, the problem statement, and describes the base algorithm. In the third section, we propose modifications of the reliable routing algorithm. In the fourth section, experimental studies of the proposed algorithms are presented. Finally, we provide our conclusions.

2. Stochastic on-time arrival problem

Step 0. Initialization.

k  0, uik (x)  0, i  N, i  s, x  N, x [0,T / t],  k  k , usk (t)  1, x  N, x [0,T / t], j  arg max ui (t)

iN uik (x)  uik1 (x), i  N , i  s, (i, j)  A, x  N, x [0, ( k   ) / t],

x uik (x)  max j  pij (h)u kj 1 (x  h), i  N , i  s, (i, j)  A, x  N, x [(( k   ) / t  1), ( k / t)] h0 (1) (2) where N is a nonempty set of nodes that correspond to road intersections, N is the number of nodes, A is a set of links that correspond to road segments, A is the number of links, P is the probabilistic description of the links travel time. We assume that the graph has a spatial reference, i.e. each node of the graph i  N has coordinates x, yi that are determined by the physical location of the corresponding intersection in the real road network.

Let Tij ( ) be the travel time of the link (i, j)  A . Travel time Tij ( ) is represented as a random variable with a probability density function pij (t) that depends on the time at which the vehicle enters this link.

Let r  N be the origin node, s  N be the destination node, T be the maximum amount of time allowed to reach the destination, i.e. the time budget.

The optimal routing policy is defined as the policy of maximizing the probability of arrival at the destination s in a time less than T . This problem is abbreviated as SOTA (Stochastic On Time Arrival) [ 8, 14, 16 ].

In papers [ 8, 19 ] for the definition of the optimal routing policy, an additional notation is introduced. Let ui (t) be the probability of reaching the destination node s from the node i at the time  with a time budget t . ui (t) is called reliability of the path.

Definition 1 [ 8 ]. The optimal routing policy for the SOTA problem can be formulated as follows

t

The discrete algorithm for solving the problem (1) was described in [ 8 ]. We will consider it as the base algorithm. The algorithm can be formulated as follows: where t is a sampling interval,  is the minimum travel time across the transport network.

The decision rule for selecting the next node j in the transport network graph for a given time budget t and calculated probabilities ui (x) is as follows:

In the described algorithm, all graph nodes are used to construct the shortest route that makes this algorithm computationally complex and not applicable for finding the shortest path in large-scale networks in real time. In the next section we propose modifications of the algorithm, consisting in selecting a certain subset of the graph nodes that will be used to find the shortest route.

3. Modified algorithm

The main idea of the modification is to achieve the acceleration of the base algorithm by reducing the number of nodes that are considered as candidates in the shortest path. We propose two methods for selecting a subset of nodes and links of the graph used to construct a reliable shortest path: on the basis of the bounding box and on the basis of the k-shortest path algorithm.

3.1. Subset based on a bounding box

The obvious way to reduce the number of nodes used to find the shortest route is to select only those nodes whose coordinates is inside the bounding box between the origin and destination nodes The bounding box coordinates can be written as follows:

xmin  min xr , xs   , ymin  min yr , y s   , xmax  max xr , xs   , ymax  max yr , y s   , where  is the buffer distance chosen experimentally.

Then the subsets of nodes and links of the graph can be defined as follows:

A  i, j A : i  N  j  N.

N  i  N : xmin  xi  xmax  ymin  yi  ymax ,

This method of selecting subsets is computationally simple, but the resulting subsets may be redundant or, conversely, insufficient, depending on the network structure and the location of the origin and destination nodes..

3.2. Subset based on the k-shortest path algorithm

The k-shortest path algorithm is an extension algorithm of the shortest path routing algorithm in a given network [ 17 ]. Depending on the problem statement, the shortest paths may or may not contain the same nodes and links. We suggest that the nodes and links that are included in the shortest path are marked as passed and cannot be used to construct the next shortest paths. To find different shortest paths, various algorithms can be used; in this paper we use the Dijkstra algorithm [ 1 ].

For a formal description of the method, we introduce additional notations.

Let drks  {v1k ,v2k ,...,vMk } be the kth shortest path between nodes r and s, where vmk  N, m  0, M k  1 is the graph node included in the kth shortest path:

M k is the number of nodes in the shortest path; k  1, K is the shortest path index; K is the number of shortest path chosen experimentally.

Then the subsets of nodes and links of the graph can be defined as follows:

N  i  d rks k 1,K ,



A  i, j  A : i  N  j  N .

The method of selecting a subset of nodes based on the k-shortest path algorithm has a greater computational complexity than the method based on the bounding box, but it does not depend on the network structure and allows to adjust the size of the subset by selecting the appropriate parameter K .

3.3. Modified reliable routing algorithm

The modified reliable routing algorithm uses subsets of nodes N and links A of the graph. In the form of a pseudo code, the algorithm can be written as follows: uik (x)  0, i  N, i  s, x  N, x [0,T / t], usk (t)  1, x  N, x [0,T / t].

Step 1. Update.

FOR k  1,2,..., L  T / t  k  k , usk (t)  1, x  N, x [0, T / t], uik (x)  uik1 (x), i  N , i  s, (i, j)  A, x  N, x [0, ( k  ) / t],

x uik (x)  max j  pij (h)u kj 1 (x  h), i  N , i  s, (i, j)  A, x  N, x [(( k  ) / t 1), ( k / t)]

h0

The subsets N and A are selected by one of the methods described above.

Image Processing, Geoinformation Technology and Information Security / I. Abdulganiev, A. Agafonov

4. Results and Discussion

The purposes of the conducted experiments were to compare the base and modified algorithms according to the criteria of the computation time of the algorithm and the reliability ui (t) of the calculated route.

The experiments were carried out on the transport network of Samara, Russia. The transport network consists of 9721 nodes and 26088 links. As the weight of the road link, we used travel time data averaged over a ten-minute interval. As the probability density function on the link i, j  we used the lognormal distribution.

To conduct experiments, 10 initial and 10 final vertices of the transport network have been chosen, located at a considerable distance from each other. For each pair of vertices, the shortest paths have been found using the base and modified algorithms. To study the algorithm based on the bounding box, the following values of the buffer distance were chosen:   200; 300; 400; 500; 600 . The study of the algorithm based on k-shortest paths was conducted depending on the number of shortest paths K  3;4;5;6;7 .

First of all, we compare the algorithms by the reliability criterion (the probability of reaching a destination node with a given time budget). The results of the comparison are presented in Table 1. 0 4 0 3 0 2 0 1 0 0 0 2 = Δ 0 0 3 = Δ 0 0 4 = Δ

500=Δ 600=Δ k3= Parameters of the algorithm 4 = k Fig 1. Acceleration of the modified algorithm.

5 = k 6 = k 7 = k

The best results on this criterion have been shown by the algorithm based on k-shortest paths. The computation time in comparison with the base algorithm decreased by 10-35 times depending on the number of shortest paths K. Modification of the base algorithm based on the bounding box allows to decrease the computation time by 8-10 times. Note that the value of the buffer distance does not have a strong effect on the speed of the algorithm, but too much value can significantly increase the computation time.

The results show, that the proposed modifications allow to significantly decrease the computation time of the base algorithm (in 8-35 times) with a slightly decrease in the reliability of the shortest path. The modified algorithm can be used to find the reliable shortest route in large-scale networks in real time.

5. Conclusion

In this paper we have proposed modifications of the reliable routing algorithm in a time-dependent stochastic transport network. Reliability means maximizing the probability of arrival at a destination within a time budget. Two modifications are proposed for the purpose of decreasing the computation time of the algorithm: based on the bounding box and based on the kshortest path algorithm. The proposed modified algorithms are compared with the base algorithm on the Samara transport network.

Acknowledgements References

This work was supported by the Russian Foundation for Basic Research (RFBR) grant 16-37-00055-mol-a.

Image Processing, Geoinformation Technology and Information Security / I. Abdulganiev, A. Agafonov

The results of experimental studies have shown that the proposed modifications allow to significantly decrease the computation time (by 8-35 times) with practically identical reliability of the routes. The modified algorithms allow to find the shortest route in large-scale networks in real time.

Further research includes: • studies related to the route choice depending on the traffic flows; • studies related to the choice of a travel time budget.

References

[1] Dijkstra EW . A Note on Two Problems on Connexion with Graphs . Numerische Mathematik 1959 ; 1 : 269 - 271 .

[2] Bellman RE . On a routing problem . Quarterly of Applied Mathematics 1958 ; 16 : 87 - 90 .

[3] Dreyfus SE. An appraisal of some shortest-path algorithm . Operations Research 1969 ; 17 : 395 - 412 .

[4] Gao S , Chabini I. Optimal routing policy problems in stochastic timedependent networks . Transportation Research Part B 2006 ; 40 : 93 - 122 .

[5] Gao S , Huang H . Real-time traveler information for optimal adaptive routing in stochastic time-dependent networks . Transportation Research Part C 2012 ; 21 : 196 - 213 .

[6] Hall RW. The fastest path through a network with random time-dependent travel times . Transportation Science 1986 ; 20 ( 3 ): 182 - 188 .

[7] Fu L , Rilett LR . Expected shortest paths in dynamic and stochastic traffic networks . Transportation Research Part B 1998 ; 32 ( 7 ): 499 - 516 .

[8] Samaranayake S , Blandin S , Bayen A . A tractable class of algorithms for reliable routing in stochastic networks . Transportation Research Part C 2012 ; 20 : 199 - 217 .

[9] Fan Y , Nie Y. Optimal routing for maximizing the travel time reliability . Networks and Spatial Economics 2006 ; 6 ( 3 -4): 333 - 344 .

[10] Frank H. Shortest paths in probabilistic graphs . Operations Research . 1969 ; 17 ( 4 ): 583 - 589 .

[11] Mirchandani PB . Shortest distance and reliability of probabilistic networks . Computers and Operations Research 1976 ; 3 ( 4 ): 347 - 355 .

[12] Montemanni R , Gambardella L . An exact algorithm for the robust shortest path problem with interval data . Computers and Operations Research 2004 ; 31 ( 10 ): 1667 - 1680 .

[13] Nie Y , Wu X . Shortest path problem considering on-time arrival probability . Transportation Research Part B 2009 ; 43 ( 6 ): 597 - 613 .

[14] Agafonov A , Myasnikov V . Reliable routing in stochastic timedependent network with the use of actual and forecast information of the traffic flows . IEEE Intelligent Vehicles Symposium , Proceedings 2016 ; 1168 - 1172 .

[15] Agafonov A . Method for the reliable shortest path search in time-dependent stochastic networks and its application to GIS-based traffic control . Computer Optics 2016 ; 40 ( 2 ): 275 - 283 . DOI: 10 .18287/ 2412 -6179-2016-40-2- 275 -283.

[16] Nie Y , Fan Y . Arriving-on-time problem: Discrete algorithm that ensures convergence . Transportation Research Record 2006 ; 1964 : 193 - 200 .

[17] Yen JY . Finding the K shortest loopless paths in a network . Management Science 1971 ; 17 ( 11 ): 712 - 716 .