Elise Miller-Hooks

PhD Student:
Sathaporn Opasanon

Sathaporn OpasanonMS, Civil and Environmental Engineering, 2000, Penn State
PhD, Civil and Environmental Engineering, 2004, UMD

Faculty of International Business, Logistics and Transport
Thammasat University
2 Prachan Rd.
Bangkok 10200, Thailand

Email: opasanon@tu.ac.th


Dissertation Title:

On Finding Paths and Flows in Multicriteria, Stochastic and Time-Varying Networks

Dissertation Abstract:

This dissertation addresses two classes of network flow problems in networks with multiple, stochastic and time-varying attributes. The first problem class is concerned with providing routing instructions with the ability to make updated decisions as information about travel conditions is revealed for individual travelers in a transportation network. Three exact algorithms are presented for identifying all or a subset of the adaptive Pareto-optimal solutions with respect to the expected value of each criterion from each node to a desired destination for each departure time in the period of interest.

The second problem class is concerned with problems of determining the optimal set of a priori path flows for evacuation in capacitated networks are addressed, where the time-dependent and stochastic nature of arc attributes and capacities inherent in these problems is explicitly considered. The concept of Safest Escape is formulated for developing egress instructions. An exact algorithm is proposed to determine the pattern of flow that maximizes the minimum path probability of successful arrival of supply at the sink.

While the Safest Escape problem considers stochastic, time-varying capacities, arc travel times, while time-varying, are deterministic quantities. Explicit consideration of stochastic and time-varying travel times makes the SEscape problem and other related problems significantly more difficult. A meta-heuristic based on the principles of genetic algorithms is developed for determining optimal path flows with respect to several problems in dynamic networks, where arc traversal times and capacities are random variables with probability mass functions that vary with time. The proposed genetic algorithm is extended for use in more difficult, stochastic, time-varying and multicriteria, capacitated networks, for which no exact, efficient algorithms exist. Several objectives may be simultaneously considered in determining the optimal flow pattern: minimize total time, maximize expected flow and maximize the minimum path probability of successful arrival at the sink (the objective of the SEscape problem). Numerical experiments are conducted to assess the performance of all proposed approaches.

MS thesis Title:

Least Expected Time Hyperpaths in Stochastic and Time-Varying Multi-Modal Networks

MS Thesis Abstract:

The primary focus of this thesis is the development of the Adaptive Multimodal Least Expected Time (AMLET) algorithm for determining the time-adaptive least expected time hyperpaths from all origins to a specified destination for all departure times in a period of interest in stochastic, time-varying multimodal networks, where the path can be appropriately changed depending on the arrival time at each node en route. In multimodal networks, travelers are allowed to select any mode or sequence of modes that is available for getting to a desired destination. The AMLET algorithm is an extension of the Time-Dependent Intermodal Least Time Path (TDILTP) algorithm of Ziliaskopoulos and Wardell (1998), and the Adaptive Least Expected Time (ALET) algorithm of Miller-Hooks (2000). Mode transfer delays are incorporated in the algorithm to account for waiting times required in transferring modes, such as between driving and boarding a transit vehicle. Both mode transfer delays and arc travel times are permitted to be stochastic and time-varying. By considering stochastic travel times, as well as the resulting stochastic transit transfer times, we can more realistically represent conditions in transportation networks than can existing deterministic approaches. Arc travel times via driving are allowed to be non-FIFO where it is possible that a vehicle departing from a particular node later than another vehicle can reach the next node before this other vehicle. The result is anticipated to provide, not only the time-adaptive least expected time hyperpaths, but also the travel mode to be chosen along each path segment for completing a trip. The time-adaptive least expected time hyperpaths are the least expected time paths in stochastic, time-varying networks, where the path selected can be adjusted at the nodes in accordance with knowledge of the arrival time at the current node and trip information experienced from previously visited nodes. The travelers are not restricted to traveling on only one path and one mode found best before departing from the origin. Rather, they can change the path and travel modes en route depending on the arrival time at each node.

The AMLET algorithm is implemented in C++ and is tested on a portion of the State College, Pennsylvania multimodal transportation network consisting of 264 nodes and 848 arcs. The period of interest is chosen from the evening peak period. This real-world example application involves 6 transportation modes including walking, driving and 4 public transit lines. Three traffic scenarios are tested to evaluate the accuracy of the algorithm and to illustrate the nature of the solution paths. In the first scenario, all six modes are available and ordinary evening peak conditions prevail. In the second scenario, traffic conditions as might be found during a football game weekend (the cause of major traffic congestion in the study region) prevail and all six modes are available. In the third scenario, it is assumed that the traveler does not have access to a car, and therefore, the driving mode is unavailable.

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