Elise Miller-Hooks

Publications: Conference 03

“On the Generation of Non-dominated Paths in Stochastic, Time-Varying Networks”

Proceedings of TRISTAN III (Triennial Symposium on Transportation Analysis), San Juan.
Miller-Hooks, E. and H. Mahmassani (1998)

Travel time between an origin and destination is often the primary criterion in optimally routing vehicles such as ambulances, police cars, vehicles carrying hazardous substances, vehicles on their way to accidents involving such substances, or individuals on their way to some activity. Efficient algorithms are widely available for finding the least time paths in networks where the arc weights are time-invariant, deterministic quantities. However, future travel times in congested transportation networks are inherently time-varying and stochastic in nature. In order to optimally route vehicles in such networks, both the random and dynamic nature of the travel times must be considered.

In this paper, a general framework is presented for determining all a priori nondominated least time paths and their associated probability distribution functions, ranges, or expected times in networks where the arc weights are random variables whose probability distribution functions vary with time (i.e. stochastic, time-varying networks). Specific details for four implementations involving three different notions of dominance are given.

An overview of the results of these implementations are given for computational tests performed on numerous randomly generated networks and on a real-world transportation network. A less computationally burdensome procedure based on this general framework is briefly described for determining a subset of non-dominated paths.



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



Volgenau School of Engineering
George Mason University