Abstract
In this paper, a pseudopolynomial time algorithm is presented for solving the integral time-dependent quickest flow problem (TDQFP) and its multiple source and sink counterparts: the time-dependent 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 time-dependent quickest flow (TDQFP) algorithm which solves the TDQFP, i.e. it solves the integral QFP, as defined above, on a time-dependent dynamic network, where the arc travel times, arc and node capacities, and supply at the source vary with time. Furthermore, this algorithm solves the time-dependent 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 time-dependent evacuation and the time-dependent quickest transshipment problems.
Similar content being viewed by others
References
Ahuja, R. K., Magnanti, T. L. and Orlin, J. B.: Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Inc., New Jersey, 1993.
Anderson, E. J. and Nash, P.: Linear Programming in Infinite-Dimensional Spaces, Wiley, New York, 1987.
Anderson, E. J., Nash, P. and Philpott, A. B.: A class of continuous network flow problems, Math. Oper. Res. 7 (1982), 501–514.
Anderson, E. J. and Philpott, A. B.: A continuous-time network simplex algorithm, Networks 19 (1989), 395–425.
Aronson, J. E.: A survey of dynamic network flows, Ann. Oper. Res. 20 (1989), 1–66.
Bellman, R.: On a routing problem, Quart. Appl. Math. 16 (1958), 87–90.
Bertsimas, D. and Stock Patterson, S.: The air traffic flow management problem with enroute capacities, Oper. Res. 46 (1998), 406–422.
Burkard, R., Dlaska, K. and Klinz, B.: The quickest flow problem, Meth. Models Oper. Res. 37 (1993), 31–58.
Cai, X., Sha, D. and Wong, C. K.: Time-varying minimum cost flow problems, European J. Oper. Res. 131 (2001), 352–374.
Chabini, L.: Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time, Transport. Res. Record 1645 (1998), 170–175.
Chalmet, L., Francis, R. and Saunders, P.: Network models for building evacuation, Management Sci. 28 (1982), 86–105.
Fleischer, L. and Tardos, E.: Efficient continuous-time dynamic network flow algorithms, Oper. Res. Lett. 23 (1998), 71–80.
Ford, L. and Fulkerson, D.: Flows in Networks, Princeton University Press, New Jersey, 1962.
Hajek, B. and Ogier, R. G.: Optimal dynamic routing in communication networks with continuous traffic, Networks 14 (1984), 457–487.
Halpern, J.: A generalized dynamic flows problem, Networks 9 (1979), 133–167.
Hamacher, H. and Tufekci, S.: On the use of lexicographic min cost flows in evacuation modeling, Naval Res. Logistics 34 (1987), 487–503.
Hoppe, B.: Efficient dynamic network flow algorithms, Technical Report TR95-1524, Department of Computer Science, Cornell University, Ithaca, NY, 1995.
Hoppe, B. and Tardos, E.: The quickest transshipment problem, Math. Oper. Res. 25 (2000), 36–62.
Jarvis, J. and Ratliff, H.: Some equivalent objectives for dynamic network flow problems, Management Sci. 28 (1982), 106–109.
Klinz, B. and Woeginger, G.: Minimum cost dynamic flows: The series-parallel case, in Proceedings of the 4th Conference on Integer Programming and Combinatorial Optimization, 1995, pp. 329–343.
Lindsay, K., Boyd, E. and Burlingame, R.: Traffic flow management modeling with the time assignment model, Air Traffic Contr. Quart. 1 (1993), 3.
Miller-Hooks, E.: Optimal routing in time-varying, stochastic networks: Algorithms and implementation, Ph.D. Thesis, Department of Civil Engineering, The University of Texas at Austin, Austin, TX, 1997.
Ogier, R. G.: Minimum-delay routing in continuous-time dynamic networks with piecewiseconstant capacities, Networks 18 (1988), 303–318.
Orda, A. and Rom, R.: On continuous network flows, Oper. Res. Lett. 17 (1995), 27–36.
Philpott, A. B.: Continuous-time flows in networks, Math. Oper. Res. 15 (1990), 640–661.
Philpott, A. B. and Craddock, M.: An adaptive discretization algorithm for a class of continuous network programs, Networks 26 (1995), 1–11.
Powell, W. B., Jaillet, P. and Odoni, A.: Stochastic and dynamic networks and routing, in M. Ball, T. Magnanti, C. Monma and G. Nemhauser (eds), Handbooks in OR and MS: Network Routing, Elsevier Science, 1995.
Pullan, M. C.: An algorithm for a class of continuous linear problems, SIAM J. Control Optim. 31 (1993), 1558–1577.
Pullan, M. C.: A study of general dynamic network programs with arc time-delays, SIAM J. Control Optim. 7 (1997), 889–912.
Ziliaskopoulos, A.: Optimum path algorithms on multidimensional networks: Analysis and design, implementation and computational experience, Ph.D. Thesis, Department of Civil Engineering, The University of Texas at Austin, Austin, TX, 1994.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Miller-Hooks, E., Stock Patterson, S. On Solving Quickest Time Problems in Time-Dependent, Dynamic Networks. Journal of Mathematical Modelling and Algorithms 3, 39–71 (2004). https://doi.org/10.1023/B:JMMA.0000026708.57419.6d
Issue Date:
DOI: https://doi.org/10.1023/B:JMMA.0000026708.57419.6d