MS, 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
On Finding Paths and Flows in Multicriteria, Stochastic and TimeVarying Networks
This dissertation addresses two classes of network flow problems in networks with multiple, stochastic and timevarying 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 Paretooptimal 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 timedependent 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, timevarying capacities, arc travel times, while timevarying, are deterministic quantities. Explicit consideration of stochastic and timevarying travel times makes the SEscape problem and other related problems significantly more difficult. A metaheuristic 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, timevarying 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.
Least Expected Time Hyperpaths in Stochastic and TimeVarying MultiModal Networks
The primary focus of this thesis is the development of the Adaptive Multimodal Least Expected Time (AMLET) algorithm for determining the timeadaptive least expected time hyperpaths from all origins to a specified destination for all departure times in a period of interest in stochastic, timevarying 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 TimeDependent Intermodal Least Time Path (TDILTP) algorithm of Ziliaskopoulos and Wardell (1998), and the Adaptive Least Expected Time (ALET) algorithm of MillerHooks (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 timevarying. 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 nonFIFO 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 timeadaptive least expected time hyperpaths, but also the travel mode to be chosen along each path segment for completing a trip. The timeadaptive least expected time hyperpaths are the least expected time paths in stochastic, timevarying 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 realworld 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 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
