Expected shortest paths in dynamic and stochastic traffic networks

Expected shortest paths in dynamic and stochastic traffic networks

0.00 Avg rating0 Votes
Article ID: iaor19991339
Country: United Kingdom
Volume: 32B
Issue: 7
Start Page Number: 499
End Page Number: 516
Publication Date: Sep 1998
Journal: Transportation Research. Part B: Methodological
Authors: ,
Keywords: networks: path
Abstract:

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 traditonal shortest path algorithms cannot guarantee an optimal soluton. 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.

Reviews

Required fields are marked *. Your email address will not be published.