A mean-variance model for stochastic time-dependent networks.

Abstract

Traditional models of route generation are based on choosing routes that minimize expected travel-time between origin and destination. The variance of the least-time path is not included in the path selection. In addition, due to congestion in transportation networks, travel times are time-dependent and stochastic in nature. This research focuses on the time dependency as well as the stochastic nature of traffic flow.

The computational performance of the algorithms was evaluated through numerical experiments using randomly generated networks. A regression curve relating the running time to number of nodes, arc density, number of time intervals, and the number of discrete arc travel times has been generated for each algorithm. The results show that number of nodes and arc density influence the running time worse than linearly. The proposed algorithms were illustrated using a real-life network and near-real time travel information between Beverly Hills and Garden Grove in Los Angeles, California. The data was generated using the Freeway Performance Measurement System (PaMS) run by California Department of Transportation and the University of California at Berkeley. The illustration showed that more research is needed in extracting travel time information from real-life data which is vast and influenced by several factors such as the day of the week, holidays, time of the day, accidents. However, through the illustration we were able to demonstrate how the proposed algorithms can be used with near real-time information.

Two algorithms are developed for determining a minimum travel time variance path and minimum mean-variance path assuming a priori best path routing policy. Under this policy, drivers use the path that corresponds to the minimum travel time variance to their destination node determined prior to the actual departure time at an origin node. We prove that both algorithms reach the optimal solution in finite number of steps but have non-polynomial running times. In addition, two algorithms, specialized modified label correcting and label setting algorithms, are developed for determining minimum mean-variance travel time path for time-adaptive routing problem. These algorithms allow the travel to define the route as he/she travels from the origin to the destination. Both algorithms reach optimal solution in finite number of steps and have polynomial computational complexity.