Elise Miller-Hooks

PhD in Civil Engineering and Operations Research, 2001
Penn State

Manager, Customer Research, American Airlines
4333 Amon Carter Blvd, MD 5390, American Airlines, Fort Worth, Texas 76155

Email: baiyu.yang@aa.com



Dissertation Title:

Robust On-Line Routing in Intelligent Transportation Systems


This work provides an efficient real-time route planning (RTRP) framework with embedded components which produces robust dynamic path strategies based on both historical and real-time travel conditions. Such a framework is especially useful in the context of Intelligent Transportation Systems (ITS), where Information Service Providers (ISPs) collect and process real-time traffic data from transportation systems and broadcast general travel information (e.g. travel speed, congestion and incidents) to a population of motorists or provide personal routing instruction (e.g. optimal route) to individual travelers. The RTRP framework is intended for use by the ISPs to generate such personal routing instruction based on (historical and real-time) traffic data. In this work, both the conceptual RTRP framework and its specific algorithmic components are provided.

The path strategies resulting from the RTRP framework with appropriately embedded components are robust (i.e. likely to remain optimal or near-optimal despite perturbations in travel conditions) because the stochastic and dynamic nature of future travel times are explicitly considered. Specifically, in this work, a transportation system is represented as a stochastic, time-varying (or STV) network (Miller-Hooks and Mahmassani, 2000), where nodes represent intersections, arcs represent streets, and arc travel times are represented as random variables with probability distribution functions (PDFs) that vary with time. The STV network provides a more realistic representation of actual travel conditions than traditional deterministic representations. Therefore, the RTRP framework proposed in this work, designed for use in STV networks, produces path strategies that are more likely to be optimal or near-optimal than those generated by other approaches which do not consider the stochastic and dynamic nature of future travel times. Experiments conducted on a real-world highway network indicate that the solutions resulting from the RTRP framework with appropriate components embedded are more robust than those from the approaches that do not consider the stochasticity of future travel times.

Two algorithms are presented for producing routing suggestions in signalized STV networks where signal timings are either known with certainty or only probabilistically. Experiments conducted on a real-world signalized street network show that explicitly considering signal control in solving for the best path strategies leads to significantly better solutions than when signal control is not considered.

The routing suggestions resulting from the RTRP framework are produced based on both historical and real-time travel information. In particular, as a motorist travels through the network, the arc travel time PDFs representing historical travel information are updated by the current travel times at specified points in time. While any updating mechanism can be used in this framework, an updating mechanism based on the concept of information discounting proposed by Koutsopoulos and Xu (1993) (for deterministic, time-invariant networks) is presented, where the value of real-time information is both temporally and spatially discounted.

In addition to the flexibility in the choice of a travel time PDF updating mechanism, this framework permits the use of real-time information on only a subset of network arcs. That is, when the RTRP framework is implemented, only a set of information critical arcs (ICAs) may be instrumented for collecting the real-time information. Thus, one can choose a fixed number of locations to be instrumented for real-time data collection. This will reduce the cost in terms of hardware and data collection, transmission, and processing. In this work, a mathematical formulation is given for the problem of determining the ICAs and a heuristic approach is proposed for solving this problem. This approach is general to other applications in instrumented transportation systems as well as other disciplines. Additionally, a neighborhood around the traveler's location can be specified for which real-time information is collected and travel time PDF updating is carried out. This will lead to further reduction in time for collecting, transmitting, and processing data. Experiments were conducted to assess the effect of collecting and employing the real-time information given a varying number of ICAs from varying size neighborhoods. The experimental results show that network-wide real-time information may not be necessary and instrumenting as little as 30% of the network arcs may lead to optimal or near-optimal routing decisions. The results also indicate that small neighborhoods may be adequate for producing good path strategies.

One can solve the real-time route planning problem by embedding existing algorithms (e.g. the ELB algorithm in Miller-Hooks and Mahmassani (2000) or the SDOT algorithm in Miller-Hooks (2001)) in the RTRP framework and resolving for the solution paths upon arrival at each intermediate location and after future travel time PDFs are updated. In this work, a faster reoptimization-based approach is presented, where routing suggestions are updated (instead of resolved for in their entirety) at each intermediate location based on previous solution paths and current travel time PDF predictions. The RTRP framework, employing such a reoptimization technique, is faster in average computational performance, and thus, more suitable for on-line application. Experiments were conducted to assess the computational benefits of using the reoptimization approach in the RTRP framework over the approach of resolving from scratch at each intermediate location. The experimental results show that the average run time is significantly smaller when the reoptimization approach is used than when solutions are found by resolving from scratch.

The contributions of this work include: (1) a flexible framework (the RTRP framework) where real-time travel information collected from user-specified network arcs is employed for updating future travel time estimates and the resulting predictions can be used by appropriate embedded routing algorithms to generate robust dynamic en route path strategies, (2) a mathematical formulation and heuristic approach to choose the arcs for which the collection of real-time information has the greatest impact on routing decisions, (3) a mechanism based on the information discounting strategy for employing real-time information to update future travel time distribution estimates, (4) specific computational steps for producing routing suggestions in signalized STV networks where signal timings are known with certainty or only probabilistically, and (5) algorithmic steps for reoptimizing (i.e. deriving solution paths from previous solutions and current travel time predictions), instead of resolving from scratch, which can be applied to a variety of least time path solution approaches that can be embedded in the RTRP framework and which makes the RTRP framework faster in average computational performance and more suitable for on-line application.

Top of Page

Elise Miller-Hooks, Ph.D.
Bill & Eleanor Hazel Chair in Infrastructure Engineering

Phone: 703.993.1685
Email: miller@gmu.edu

Office: 4614 Nguyen Engineering Building

Sid and Reva Dewberry Department of Civil, Environmental and Infrastructure Engineering
George Mason University
4400 University Drive, MS 6C1
Fairfax, VA 22030


Additional Resources




Volgenau School of Engineering
George Mason University