The Quick Time Dependent Quickest Flow Problem: A Lesson in Zero-Sum Cycles

Simple item page
dc.contributor.advisorMiller-Hooks, Elise Den_US
dc.contributor.authorDhundia, Harshen_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:59:50Z
dc.date.available2005-02-02T06:59:50Z
dc.date.issued2005-01-03en_US
dc.description.abstractA quick solution technique for the integral time-dependent quickest flow problem with no waiting is presented. The proposed technique is based on the successive shortest path approach and modifies an existing algorithm to improve its average performance. At each iteration, a reoptimization procedure is employed to determine the augmenting path given updates to the residual graph. The residual graph, by construction, almost always contains zero-sum cycles when employed in this context. These zero-sum cycles pose a unique problem for the reoptimization technique. A heuristic that can be embedded in the reoptimization algorithm to provide path solutions in the presence of zero-sum cycles has been proposed. In the computational experiments, the heuristic provided an optimal solution nearly 100% of the times. Further, a modified implementation of an existing path-finding algorithm has been used to solve the time-dependent quickest flow problem with source waiting.en_US
dc.format.extent403978 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/2173
dc.language.isoen_US
dc.subject.pqcontrolledEngineering, Civilen_US
dc.subject.pqcontrolledOperations Researchen_US
dc.subject.pqcontrolledEngineering, Industrialen_US
dc.subject.pquncontrolledsuccessive shortest pathen_US
dc.subject.pquncontrolledreoptimizationen_US
dc.subject.pquncontrolledresidual graphen_US
dc.subject.pquncontrolledzero-sum cycleen_US
dc.titleThe Quick Time Dependent Quickest Flow Problem: A Lesson in Zero-Sum Cyclesen_US
dc.typeThesisen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
umi-umd-2160.pdf
Size:
394.51 KB
Format:
Adobe Portable Document Format
Download

Collections

UMD Theses and Dissertations
Civil & Environmental Engineering Theses and Dissertations