Journal of Mathematical Modelling and Algorithms 3(1), 3971
MillerHooks, E. and S. Stock Patterson (2004)
In this paper, a pseudopolynomial time algorithm is presented for solving the integral timedependent quickest flow problem (TDQFP) and its multiple source and sink counterparts: the timedependent
evacuation and quickest transshipment problems. A more widely known, though less general version, is the quickest flow problem (QFP). The QFP has historically been defined on a dynamic network,
where time is divided into discrete units, flow moves through the network over time, travel times determine how long each unit of flow spends traversing an arc, and capacities restrict the rate of
flow on an arc.
The goal of the QFP is to determine the paths along which to send a given supply from a single source to a single sink such that the last unit of flow arrives at the sink in the minimum
time. The main contribution of this paper is the timedependent quickest flow (TDQFP) algorithm which solves the TDQFP, i.e. it solves the integral QFP, as defined above, on a timedependent
dynamic network, where the arc travel times, arc and node capacities, and supply at the source vary with time. Furthermore, this algorithm solves the timedependent minimum time dynamic flow
problem, whose objective is to determine the paths that lead to the minimum total time spent completing all shipments from source to sink.
An optimal solution to the latter problem is
guaranteed to be optimal for the TDQFP. By adding a small number of nodes and arcs to the existing network, we show how the algorithm can be used to solve both the timedependent evacuation
and the timedependent quickest transshipment problems.

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
More Publications
