Online Stochastic Routing Incorporating Real-Time Traffic Information

Abstract

In this paper, online stochastic routing policies are developed to identify the optimal next action (path choice) at the current decision node (intersection) for travelers on the basis of their preference for future paths with the shortest travel time, the lowest travel time variability, or a combination, given the network conditions. A modified label-correcting algorithm is provided to solve for the shortest path that results from the proposed routing policies. Its running time is bounded by O(mn²), where m and n are the number of arcs and nodes, respectively, in the network. Since real-time traffic information is usually available with a certain level of accuracy, the proposed online routing policy integrates an existing information fusion model, which provides real-time short-term arc travel time distributions by considering information accuracy. Numerical experiments are used to demonstrate the performance of the proposed routing policies and algorithms, as well as the impacts of real-time information accuracy on the online stochastic routing.

Get full access to this article

View all access options for this article.

References

, Peeta

, and Kim

Y. H.

An Adaptive Information Fusion Model to Predict the Short-Term Arc Travel Time Distribution in Dynamic Traffic Networks. Transportation Research Part B: Methodological, Vol. 46, No. 1, 2011, pp. 235–252.

Waller

, and Ziliaskopoulos

On the On-Line Shortest Path Problem with Limited Arc Cost Dependencies. Networks, Vol. 40, No. 4, 2002, pp. 216–227.

Croucher

A Note on the Stochastic Shortest-Route Problem. Naval Research Logistics, Vol. 25, 1978, pp. 729–732.

Eiger

, Mirchandani

P. B.

, and Soroush

Path Preferences and Optimal Paths in Probabilistic Networks. Transportation Science, Vol. 19, No. 1, 1985, pp. 75–84.

Kaufman

, and Smith

Fastest Paths in Time-Dependent Networks for Intelligent Vehicle Highway System Application. Intelligent Vehicle–Highway Systems Journal, Vol. 1, No. 1, 1993, pp. 1–11.

Hall

The Fastest Path Through a Network with Random Time-Dependent Travel Time. Transportation Science, Vol. 20, No. 3, 1986, pp. 182–188.

Wellman

, Ford

, and Larson

Path Planning Under Time-Dependent Uncertainty. Proc., 11th Conference on Uncertainty in Artificial Intelligence, Montreal, Canada, Aug. 18–20, 1995, pp. 532–539.

Hooks

, and Mahmassani

Least Possible Time Paths in Stochastic Time-Varying Networks. Computers and Operations Research, Vol. 25, No. 12, 1998, pp. 1107–1125.

Hooks

, and Mahmassani

Least Expected Time Paths in Stochastic Time-Varying Transportation Networks. Transportation Science, Vol. 34, No. 2, 2000, pp. 198–215.

10.

Hooks

Adaptive Least-Expected Time Paths in Stochastic, Time-Varying Transportation and Data Networks. Networks, Vol. 37, No. 1, 2001, pp. 35–52.

11.

Fan

, Kalaba

, and Moore

Arriving on Time. Journal of Optimization Theory and Applications, Vol. 127, No. 3, 2005, pp. 497–513.

12.

An Adaptive Routing Algorithm for In-Vehicle Route Guidance Systems with Real-Time Information. Transportation Research Part B: Methodological, Vol. 32, No. 7, 2001, pp. 749–765.

13.

R. R.

, Liu

H. X.

, Kornhauser

A. L.

, and Ran

Temporal and Spatial Variability of Travel Time. Technical Report UCI-ITS-TS-WP-02-13. Institute of Transportation Studies, University of California, Irvine, 2002.

14.

Provan

A Polynomial-Time Algorithm to Find Shortest Paths with Recourse. Networks, Vol. 41, No. 2, 2003, pp. 115–125.

15.

Andreatta

, and Romeo

Stochastic Shortest Paths with Recourse. Networks, Vol. 18, 1988, pp. 193–204.

16.

Psaraftis

, and Tsitsiklis

Dynamic Shortest Paths in Acyclic Networks with Markovian Arc Costs. Operations Research, Vol. 41, No. 1, 1993, pp. 91–101.

17.

Gao

, and Chabini

Optimal Routing Policy Problems in Stochastic Time-Dependent Networks. Transportation Research Part B: Methodological, Vol. 40, No. 2, 2006, pp. 93–122.

18.

Kim

, Lewis

, and White

C. I.

Optimal Vehicle Routing with Real-Time Traffic Information. IEEE Transactions on Intelligent Transportation Systems, Vol. 6, No. 2, 2005, pp. 178–188.

19.

Kim

, Lewis

, and White

C. I.

State Space Reduction for Non-Stationary Stochastic Shortest Path Problems with Real-Time Traffic Information. IEEE Transactions on Intelligent Transportation Systems, Vol. 6, No. 3, 2005, pp. 273–284.

20.

Bellman

Dynamic Programming. Princeton University Press, Princeton, N.J., 1965.

21.

Ahuja

R. K.

, Magnanti

T. L.

, and Orlin

J. B.

Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.