Elise Miller-Hooks

MS Student:
Harsh Dhundia

Harsh DhundiaMS, 2005, Civil and Environmental Engineering, UMD

Contact info: Unknown

Thesis Title:

The Quick TDQFP: A Lesson in Zero-Sum Cycles


In this thesis, 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. It modifies an existing algorithm to improve its average performance in solving the time-dependent quickest flow problem when no waiting is allowed at any node. At each iteration of a typical algorithm based on the successive shortest path approach, a new augmenting path is sought in a residual graph. The problem of determining a new path at each iteration can be viewed as a problem of updating the path given changes to the arc travel times. Thus, a reoptimization procedure is employed to determine the augmenting path at each iteration. The residual graph, by construction, almost always contains zero-sum cycles when employed in this context. Zero-sum cycles pose a problem for the reoptimization technique. A heuristic that can be embedded in the reoptimization algorithm to prevent the inclusion of a zero-sum cycle is developed for this purpose. Numerous computational experiments were conducted. Results from the application of the heuristic were found to be optimal nearly 100% of the time. The results also indicate that the proposed heuristic provides significant improvement in computation time over the existing technique when it was used with an appropriate path-finding function to address the problem with no waiting. Further, a modified implementation of an existing one-to-all path-finding algorithm is proposed. Using this modified path-finding algorithm in the existing successive shortest path based technique provides an exact solution for the time-dependent quickest flow problem when waiting at the source is allowed. For smaller problem sizes, the run times of the heuristic were comparable with those obtained with the use of the modified implementation of the one-to-all path-finding algorithm. However, as the problem size grew, the heuristic proved to be significantly faster. It may be possible to develop a reoptimization procedure for this one-to-all path finding algorithm based on an existing work in which a reoptimization algorithm for the reverse implementation of the said path-finding algorithm. Such a procedure would further improve its computational performance when used in the successive shortest path approach.

Elise Miller-Hooks, Ph.D.
Bill & Eleanor Hazel Chair in Infrastructure Engineering

Phone: 703.993.1685
Email: miller@gmu.edu

Office: 4614 Nguyen Engineering Building

Sid and Reva Dewberry Department of Civil, Environmental and Infrastructure Engineering
George Mason University
4400 University Drive, MS 6C1
Fairfax, VA 22030


Additional Resources




Volgenau School of Engineering
George Mason University