On finding paths and flows in multicriteria, stochastic and time-varying networks

dc.contributor.advisorMiller-Hooks, Eliseen_US
dc.contributor.authorOpasanon, Sathaporn -en_US
dc.contributor.departmentCivil Engineeringen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2005-02-02T06:39:11Z
dc.date.available2005-02-02T06:39:11Z
dc.date.issued2004-11-24en_US
dc.description.abstractThis 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.en_US
dc.format.extent1756444 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/2067
dc.language.isoen_US
dc.subject.pqcontrolledEngineering, Civilen_US
dc.subject.pquncontrolledMulticriteriaen_US
dc.subject.pquncontrolledOptimal Pathen_US
dc.subject.pquncontrolledFlowen_US
dc.subject.pquncontrolledNetworken_US
dc.subject.pquncontrolledTransportationen_US
dc.subject.pquncontrolledEvacuationen_US
dc.titleOn finding paths and flows in multicriteria, stochastic and time-varying networksen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
umi-umd-2030.pdf
Size:
1.68 MB
Format:
Adobe Portable Document Format