Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

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

    Thumbnail
    View/Open
    umi-umd-2160.pdf (394.5Kb)
    No. of downloads: 1649

    Date
    2005-01-03
    Author
    Dhundia, Harsh
    Advisor
    Miller-Hooks, Elise D
    Metadata
    Show full item record
    Abstract
    A 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.
    URI
    http://hdl.handle.net/1903/2173
    Collections
    • Civil & Environmental Engineering Theses and Dissertations
    • UMD Theses and Dissertations

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility