EXPECTED SHORTEST PATHS IN DYNAMIC AND STOCHASTIC TRAFFIC NETWORKS

The dynamic and stochastic shortest path problem (DSSPP) is defined as finding the expected shortest path in a traffic network where the lin k travel times are modeled as a continuous-time stochastic process. Th e 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 Transp ortation System (ITS) capabilities. The paper first identifies a set o f relationships between the mean and variance of the travel time of a given path and the mean and variance of the dynamic and stochastic lin k travel times on these networks. Based on these relationships it is s hown that the DSSPP is computationally intractable and traditional sho rtest path algorithms cannot guarantee an optimal solution. A heuristi c algorithm based on the k-shortest path algorithm is subsequently pro posed to solve the problem. Lastly, the trade-off between solution qua lity and computational efficiency of the proposed algorithm is demonst rated on a realistic network from Edmonton, Alberta. (C) 1998 Elsevier Science Ltd. All rights reserved.