Impact of Travel Time Models on Quality of Real-Time Routing Instructions

Abstract

Mobile communication systems coupled with intelligent transportation systems technologies can permit information service providers to supply real-time routing instructions to suitably equipped vehicles as real-time travel times are received. Simply considering current conditions in updating routing decisions, however, may lead to suboptimal path choices, because future travel conditions likely will differ from that currently observed. Even with perfect and continuously updated information about current conditions, future travel times can be known a priori with uncertainty at best. Further, in congested transportation systems, conditions vary over time as recurrent congestion may change with a foreseeable pattern during peak driving hours. It is postulated that better, more robust routing instructions can be provided by explicitly accounting for this inherent stochastic and dynamic nature of future travel conditions in generating the routing instructions. It is further hypothesized that nearly equally good routing instructions can be provided by collecting real-time information from only a small neighborhood within the transportation system as from the entire system. Extensive numerical experiments were conducted to assess the validity of these two hypotheses.

Get full access to this article

View all access options for this article.

References

Hall

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

Psaraftis

, and Tsitsiklis

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

Miller-Hooks

, and Mahmassani

H. S.

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

Miller-Hooks

, and Mahmassani

H. S.

. Optimal Routing of Hazardous Materials in Stochastic, Time-Varying Transportation Networks. In Transportation Research Record 1645, TRB, National Research Council, Washington, D.C., 1998, pp. 143–151.

Miller-Hooks

, and Mahmassani

H. S.

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

, and Rilett

. Expected Shortest Paths in Dynamic and Stochastic Traffic Networks. Transportation Research B, Vol. 32, 1998, pp. 499–516.

Pretolani

A Directed Hyperpath Model for Random Time Dependent Shortest Paths. European Journal of Operational Research, Vol. 123, 2000, pp. 315–324.

An Adaptive Routing Algorithm for In-Vehicle Route Guidance Systems with Real-Time Information. Transportation Research B, Vol. 35, 2001, pp. 749–765.

Miller-Hooks

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

10.

Yang

Robust On-Line Routing in Intelligent Transportation Systems. Ph.D. dissertation. Department of Civil and Environmental Engineering, The Pennsylvania State University, University Park, 2001.

11.

Koutsopoulos

, and Xu

. An Information Discounting Routing Strategy for Advanced Traveler Information Systems. Transportation Research C, Vol. 1, 1993, pp. 249–264.

12.

Ahuja

, Magnanti

, and Orlin

. Network Flows. Prentice Hall, Englewood Cliffs, N.J., 1993, ch. 4, 5.

13.

Bellman

On a Routing Problem. Quarterly of Applied Mathematics, Vol. 16, 1958, pp. 87–90.

14.

Ziliaskopoulos

A. K.

, and Mahmassani

H. S.

. Time-Dependent, Shortest-Path Algorithm for Real-Time Intelligent Vehicle Highway System Applications. In Transportation Research Record 1408, TRB, National Research Council, Washington, D.C., 1993, pp. 94–100.

15.

Chabini

Discrete Dynamic Shortest Path Problems in Transportation Applications: Complexity and Algorithms with Optimal Run Time. In Transportation Research Record 1645, TRB, National Research Council, Washington, D.C., 1998, pp. 170–175.

16.

Miller-Hooks

, and Yang

. Updating Paths in General Transportation Networks. Transportation Science, 2002, in review.