Abstract
Consider a network\(\mathcal{N}\)=(G, c, τ) whereG=(N, A) is a directed graph andc ij andτ ij , respectively, denote the capacity and the transmission time of arc (i, j) ∈A. The quickest flow problem is then to determine for a given valueυ the minimum numberT(υ) of time units that are necessary to transmit (send)υ units of flow in\(\mathcal{N}\) from a given sources to a given sinks′.
In this paper we show that the quickest flow problem is closely related to the maximum dynamic flow problem and to linear fractional programming problems. Based on these relationships we develop several polynomial algorithms and a strongly polynomial algorithm for the quickest flow problem.
Finally we report computational results on the practical behaviour of our metholds. It turns out that some of them are practically very efficient and well-suited for solving large problem instances.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ahrens JH, Finke G (1980) Primal transportation and transshipment algorithms.Zeitschrift für Operations Research 24:1–32
Ahuja RK, Magnanti T, Orlin JB (1989) Network Flows. In: GL Nemhauser et al. (eds.),Handbooks in OR & MS, Vol. 1, North Holland, Amsterdam, 211–369
Ahuja RK, Orlin JB (1991) Scaling algorithms for the constrained maximum flow problem, talk presented at the 14-th International Symposium on Mathematical Programming, Amsterdam
Ali AI, Padman R, Thiagaran H (1989) Dual algorithms for pure network problems.Operations Research 37:159–171
Aronson JE (1989) A survey on dynamic network flows.Annals of Operations Research 20:1–66
Bertsekas DP, Tseng P (1988) The relax codes for linear minimum cost network flow problems.Annals of Operations Research 13:125–190
Bertsekas DP, Tseng P (1990) RELAXT-III: A new and improved version of the RELAX code, LIDS Report P-1990, Laboratory for Information and Decision Systems, MIT, Cambridge, MA
Burkard RE, Dlaska K, Kellerer H (1991) The quickest disjoint flow problem. Technical Report 189-91, Institute of Mathematics, University of Technology, Graz, Austria
Burkard RE, Dlaska K, Klinz B (1991) The quickest flow problem. Technical Report 188-91, Institute of Mathematics, University of Technology, Graz, Austria (also available as Rutcor Research Report RRR # 57-91, Rutgers University, New Brunswick, NJ, 1991)
Carstensen PJ (1983) Complexity of some parametric integer and network programming problems.Mathematical Programming 5:64–75
Chalmet LG, Francis RL, Saunders PB (1982) Network models for building evacuation.Management Science 28:86–105
Chen YL, Chin YH (1990) The quickest path problem.Computers and Operations Research 17:153–161
Derigs U, Meier W (1989) Implementing Goldberg's max-flow algorithm, a computational investigation.Zeitschrift für Operations Research 33:383–403
Derigs U, Meier W (1990) Goldrmf/Goldnet-max-flow program.European Journal of Operational Research 46:260
Ford LR, Fulkerson DR (1962)Flows in Networks, Princeton University Press, New Jersey
Gallo G, Pallottino S (1988) Shortest path algorithms.Annals of Operations Research 13:3–79
Gibbons A, Rytter W (1988)Efficient Parallel Algorithms, Cambridge University Press, Cambridge
Grigoriadis MD (1986) An efficient implementation of the network simplex method.Mathematical Programming Study 26:83–111
Hamacher HW (1983) Min cost and time minimizing dynamic flows, Research Report No. 83-16, Industrial & Systems Engineering Department, University of Florida, Gainesville
Hamacher HW (1989) Temporally repeated flow algorithms for dynamic min cost flows,Proceedings of the 28-th IEEE Conference on Decision and Control
Ibaraki T (1983) Parametric approaches to fractional programs.Mathematical Programming 26:345–362
Iwano K, Misono S, Tezuka S, Fujishige S (1990) A new scaling algorithm for the maximum mean cut problem. IBM Research Report RT 0049, Tokyo, Japan
Jarvis JR, Ratliff DH (1982) Some equivalent objectives for dynamic network flow problems.Management Science 28:106–109
Karp RM, Orlin JB (1981) Parametric shortest path algorithms with an application to cyclic staffing.Discrete Applied Mathematics 3:37–45
Klingman D, Napier A, Stutz S (1974) Netgen: A program for generating large scale capacitated assignment, transportation and minimum cost flow problems.Management Science 20: 814–821
Klinz B, Tuy H (1991) Minimum concave-cost network flow problems with a single nonlinear arc cost, Technical Report 191-91, Institute of Mathematics, University of Technology, Graz, Austria
McCormick TS, Ervolina TR (1990) Computing maximum mean cuts, UBC Faculty of Commerce Working Paper 90-MSC-011, Vancouver, BC
Megiddo N (1979) Combinatorial optimization with rational objective functions.Mathematics of Operations Research 4:414–424
Megiddo N (1983) Applying parallel computation algorithms in the design of serial algorithms.Journal of the A. C. M. 30:852–865
Minieka E (1973) Maximal, lexicographic, and dynamic network flows.Operations Research 21:517–527
Murty KG (1983)Linear Programming, John Wiley & Sons, New York
Orlin JB (1988) A faster strongly polynomial minimum cost flow algorithm,Proc. 20-th Annual Symp. Theory of Computing 377–387
Orlin JB (1992) Private communication
Orlin JB, Ahuja RK (1992) New scaling algorithms for the assignment and minimum mean cycle problems.Mathematical Programming 54:41–56
Radzik T (1991) Minimizing capacity violations in a transshipment network, Technical Report, Computer Science Department, Stanford University, CA
Rosen JB, Sun S-Z, Xue G-L (1991) Algorithms for the quickest path problem and the enumeration of quickest paths.Computers and Operations Research 18:579–584
Rote G (1991) Private communication
Ruhe G (1991)Algorithmic Aspects of Flows in Networks, Mathematics and Its Applications, Volume 69, Kluwer Academic Publishers, Doortrecht
Schaible S (1978)Analyse und Anwendungen von Quotientenprogrammen — Ein Beitrag zur Planung mit Hilfe der nichtlinearen Programmierung, (in German), Mathematical Systems in Economics 42, Verlag Anton Hain, Meisenheim am Glan
Schaible S, Ibaraki T (1983) Fractional programming.European Journal of Operational Research 12:325–338
Young NE, Tarjan RE, Orlin JB (1991) Faster parametric shortest path minimum-balance algorithms.Networks 21:205–221
Zadeh N (1973) A bad network problem for the simplex method and other minimum cost flow algorithms.Mathematical Programming 5:255–266
Author information
Authors and Affiliations
Additional information
Partial financial support by the Air Force Office of Scientific Research under grants AFOSR-89-0512 and AFOSR-90-0008 is gratefully acknowledged by the first author.
Rights and permissions
About this article
Cite this article
Burkard, R.E., Dlaska, K. & Klinz, B. The quickest flow problem. ZOR - Methods and Models of Operations Research 37, 31–58 (1993). https://doi.org/10.1007/BF01415527
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01415527