MS, 2005, Civil and Environmental Engineering, UMD
Contact info: Unknown
The Quick TDQFP: A Lesson in ZeroSum Cycles
In this thesis, a quick solution technique for the integral timedependent 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 timedependent 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 zerosum cycles when employed in this context. Zerosum cycles pose a problem for the reoptimization technique. A heuristic that can be embedded in the reoptimization algorithm to prevent the inclusion of a zerosum 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 pathfinding function to address the problem with no waiting. Further, a modified implementation of an existing onetoall pathfinding algorithm is proposed. Using this modified pathfinding algorithm in the existing successive shortest path based technique provides an exact solution for the timedependent 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 onetoall pathfinding 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 onetoall path finding algorithm based on an existing work in which a reoptimization algorithm for the reverse implementation of the said pathfinding algorithm. Such a procedure would further improve its computational performance when used in the successive shortest path approach.

Elise MillerHooks, Ph.D.
Professor
Bill & Eleanor Hazel Chair in Infrastructure Engineering
Phone: 703.993.1685
Email: miller@gmu.edu
Office: 4614 Nguyen Engineering Building
Address:
Sid and Reva Dewberry Department of Civil, Environmental and Infrastructure Engineering
George Mason University
4400 University Drive, MS 6C1
Fairfax, VA 22030
USA
Students
Home
