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
Robust OnLine Routing in Intelligent Transportation Systems
This work provides an efficient realtime route planning (RTRP) framework with embedded components which produces robust dynamic path strategies based on both historical and realtime travel conditions. Such a framework is especially useful in the context of Intelligent Transportation Systems (ITS), where Information Service Providers (ISPs) collect and process realtime 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 realtime) 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 nearoptimal 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, timevarying (or STV) network (MillerHooks 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 nearoptimal than those generated by other approaches which do not consider the stochastic and dynamic nature of future travel times. Experiments conducted on a realworld 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 realworld 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 realtime 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, timeinvariant networks) is presented, where the value of realtime 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 realtime 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 realtime information. Thus, one can choose a fixed number of locations to be instrumented for realtime 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 realtime 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 realtime information given a varying number of ICAs from varying size neighborhoods. The experimental results show that networkwide realtime information may not be necessary and instrumenting as little as 30% of the network arcs may lead to optimal or nearoptimal routing decisions. The results also indicate that small neighborhoods may be adequate for producing good path strategies.
One can solve the realtime route planning problem by embedding existing algorithms (e.g. the ELB algorithm in MillerHooks and Mahmassani (2000) or the SDOT algorithm in MillerHooks (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 reoptimizationbased 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 online 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 realtime travel information collected from userspecified 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 realtime information has the greatest impact on routing decisions, (3) a mechanism based on the information discounting strategy for employing realtime 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 online application.
Top of Page

Elise MillerHooks, Ph.D.
Professor
Bill & Eleanor Hazel Chair in Infrastructure Engineering
Phone: 703.993.1685
Email: miller@gmu.edu
Office: 4614 Nguyen Engineering Building
Address:
Sid and Reva Dewberry Department of Civil, Environmental and Infrastructure Engineering
George Mason University
4400 University Drive, MS 6C1
Fairfax, VA 22030
USA
Students
Home
