TY - JOUR
T1 - Expected shortest paths in dynamic and stochastic traffic networks
AU - Fu, Liping
AU - Rilett, L. R.
N1 - Funding Information:
This research was funded through a Natural Science and Engineering Research Council of Canada Operating Grant (OGP 138670) and their assistance is gratefully acknowledged. The authors would like to thank the three anonymous referees for their helpful comments.
PY - 1998/9
Y1 - 1998/9
N2 - The dynamic and stochastic shortest path problem (DSSPP) is defined as finding the expected shortest path in a traffic network where the link travel times are modeled as a continuous-time stochastic process. The objective of this paper is to examine the properties of the problem and to identify a technique that can be used to solve the DSSPP given information that will be available in networks with Intelligent Transportation System (ITS) capabilities. The paper first identifies a set of relationships between the mean and variance of the travel time of a given path and the mean and variance of the dynamic and stochastic link travel times on these networks. Based on these relationships it is shown that the DSSPP is computationally intractable and traditional shortest path algorithms cannot guarantee an optimal solution. A heuristic algorithm based on the k-shortest path algorithm is subsequently proposed to solve the problem. Lastly, the trade-off between solution quality and computational efficiency of the proposed algorithm is demonstrated on a realistic network from Edmonton, Alberta.
AB - The dynamic and stochastic shortest path problem (DSSPP) is defined as finding the expected shortest path in a traffic network where the link travel times are modeled as a continuous-time stochastic process. The objective of this paper is to examine the properties of the problem and to identify a technique that can be used to solve the DSSPP given information that will be available in networks with Intelligent Transportation System (ITS) capabilities. The paper first identifies a set of relationships between the mean and variance of the travel time of a given path and the mean and variance of the dynamic and stochastic link travel times on these networks. Based on these relationships it is shown that the DSSPP is computationally intractable and traditional shortest path algorithms cannot guarantee an optimal solution. A heuristic algorithm based on the k-shortest path algorithm is subsequently proposed to solve the problem. Lastly, the trade-off between solution quality and computational efficiency of the proposed algorithm is demonstrated on a realistic network from Edmonton, Alberta.
KW - Dynamic and stochastic network
KW - Intelligent Transportation Systems
KW - Route Guidance Systems
KW - Shortest path problem
KW - Traffic network
KW - k-shortest path problem
UR - http://www.scopus.com/inward/record.url?scp=0032157717&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032157717&partnerID=8YFLogxK
U2 - 10.1016/S0191-2615(98)00016-2
DO - 10.1016/S0191-2615(98)00016-2
M3 - Article
AN - SCOPUS:0032157717
SN - 0191-2615
VL - 32
SP - 499
EP - 516
JO - Transportation Research, Series B: Methodological
JF - Transportation Research, Series B: Methodological
IS - 7
ER -