Show simple item record

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

dc.contributor.advisorMiller-Hooks, Elise Den_US
dc.contributor.authorDhundia, Harshen_US
dc.date.accessioned2005-02-02T06:59:50Z
dc.date.available2005-02-02T06:59:50Z
dc.date.issued2005-01-03en_US
dc.identifier.urihttp://hdl.handle.net/1903/2173
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.language.isoen_US
dc.titleThe Quick Time Dependent Quickest Flow Problem: A Lesson in Zero-Sum Cyclesen_US
dc.typeThesisen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.contributor.departmentCivil Engineeringen_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


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record