Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-05T02:01:26.870Z Has data issue: false hasContentIssue false

An Introduction to Transshipments Over Time

Published online by Cambridge University Press:  23 May 2024

By
Martin Skutella
Edited by
Felix Fischer  and
Robert Johnson
Felix Fischer
Affiliation:
Queen Mary University of London
Robert Johnson
Affiliation:
Queen Mary University of London
Get access

Summary

Network flows over time are a fascinating generalization of classical (static) network flows, introducing an element of time. They naturally model problems where travel and transmission are not instantaneous and flow may vary over time. Not surprisingly, flow over time problems turn out to be more challenging to solve than their static counterparts. In this survey, we mainly focus on the efficient computation of transshipments over time in networks with several source and sink nodes with given supplies and demands, which is arguably the most difficult flow over time problem that can still be solved in polynomial time.

Type
Chapter
Information
Surveys in Combinatorics 2024 , pp. 239 - 270
Publisher: Cambridge University Press
Print publication year: 2024

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Anderson, E. J. and Nash, P., Linear programming in infinite-dimensional spaces, Wiley, New York, 1987.Google Scholar
Anderson, E. J., Nash, P., and A. B. Philpott, A class of continuous network flow problems, Mathematics of Operations Research 7 (1982), 501–514.CrossRefGoogle Scholar
Anderson, E. J. and Philpott, A. B., Optimisation of flows in networks over time, Probability, Statistics and Optimisation (F. P. Kelly, ed.), Wiley, New York, 1994, pp. 369–382.Google Scholar
Aronson, J. E., A survey of dynamic network flows, Annals of Operations Research 20 (1989), 1–66.CrossRefGoogle Scholar
Baumann, N. and Skutella, M., Solving evacuation problems efficiently: Earliest arrival flows with multiple sources, Mathematics of Operations Research 34 (2009), 499–512.CrossRefGoogle Scholar
Berlin, G. N., The use of directed routes for assessing escape potential, National Fire Protection Association, Boston, MA, 1979.Google Scholar
Bixby, R. E., Cunningham, W. H., and Topkis, D. M., The partial order of a polymatroid extreme point, Mathematics of Operations Research 10 (1985), 367–378.CrossRefGoogle Scholar
Burkard, R. E., Dlaska, K., and Klinz, B., The quickest flow problem, ZOR — Methods and Models of Operations Research 37 (1993), 31–58.CrossRefGoogle Scholar
Cunningham, W. H., Testing membership in matroid polyhedra, Journal of Combinatorial Theory, Series B 36 (1984), 161–188.CrossRefGoogle Scholar
Cunningham, W. H., On submodular function minimization, Combinatorica 3 (1985), 185–192.CrossRefGoogle Scholar
Dinkelbach, W., On nonlinear fractional programming, Management Science 13 (1967), 492–498.CrossRefGoogle Scholar
Disser, Y. and Skutella, M., The simplex algorithm is NP-mighty, ACM Transactions on Algorithms 15 (2019), 5:1–5:19.CrossRefGoogle Scholar
Dressler, D., FlötteRöd, G., Lämmel, G., Nagel, K., and Skutella, M., Optimal evacuation solutions for large-scale scenarios, Operations Research Proceedings 2010 (Hu, B., Morasch, K., Pickl, S., and Siegle, M., eds.), Springer, 2011, pp. 239–244.CrossRefGoogle Scholar
Dressler, D., Groß, M., Kappmeier, J.-P., Kelter, T., Kulbatzki, J., Plümpe, D., Schlechter, G., Schmidt, M., Skutella, M., and Temme, S., On the use of network flow techniques for assigning evacuees to exits, Proceedings of the International Conference on Evacuation Modeling and Management, Procedia Engineering, vol. 3, Elsevier Ltd, 2010, pp. 205–215.Google Scholar
Edmonds, J., Submodular functions, matroids and certain polyhedra, Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications (Guy, R., Hanai, H., Sauer, N., and Schönheim, J., eds.), 1970, pp. 69–87.Google Scholar
Fleischer, L. and Skutella, M., Quickest flows over time, SIAM Journal on Computing 36 (2007), 1600–1630.CrossRefGoogle Scholar
Fleischer, L. K., Faster algorithms for the quickest transshipment problem, SIAM Journal on Optimization 12 (2001), 18–35.CrossRefGoogle Scholar
Fleischer, L. K. and É. Tardos, Efficient continuous-time dynamic network flow algorithms, Operations Research Letters 23 (1998), 71–80.CrossRefGoogle Scholar
Ford, L. R. and Fulkerson, D. R., Constructing maximal dynamic flows from static flows, Operations Research 6 (1958), 419–433.CrossRefGoogle Scholar
Ford, L. R. and Fulkerson, D. R., Flows in networks, Princeton University Press, 1962.CrossRefGoogle Scholar
Gale, D., Transient flows in networks, Michigan Mathematical Journal 6 (1959), 59–63.CrossRefGoogle Scholar
Goldberg, A. V. and Tarjan, R. E., Finding minimum-cost circulations by successive approximation, Mathematics of Operations Research 15 (1990), 430–466.CrossRefGoogle Scholar
Groß, M., Kappmeier, J.-P. W., Schmidt, D. R., and Schmidt, M., Approximating earliest arrival flows in arbitrary networks, Algorithms – ESA 2012 – 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings (Epstein, L. and Ferragina, P., eds.), Lecture Notes in Computer Science, vol. 7501, Springer, 2012, pp. 551–562.Google Scholar
Groß, M. and Skutella, M., A tight bound on the speed-up through storage for quickest multi-commodity flows, Operations Research Letters 43 (2015), 93–95.CrossRefGoogle Scholar
Grötschel, M., Lovász, L., and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2, Springer, 1988.Google Scholar
Hajek, B. and Ogier, R. G., Optimal dynamic routing in communication networks with continuous traffic, Networks 14 (1984), 457–487.CrossRefGoogle Scholar
Hall, A., Hippler, S., and Skutella, M., Multicommodity flows over time: Efficient algorithms and complexity, Theoretical Computer Science 379 (2007), 387–404.CrossRefGoogle Scholar
Hamacher, H. W. and Tufecki, S., On the use of lexicographic min cost flows in evacuation modeling, Naval Research Logistics 34 (1987), 487–503.3.0.CO;2-9>CrossRefGoogle Scholar
Hoppe, B., Efficient dynamic network flow algorithms, Ph.D. thesis, Cornell University, 1995.Google Scholar
Hoppe, B. and É. Tardos, Polynomial time algorithms for some evacuation problems, Proceedings of the 5th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA 1994), 1994, pp. 433–441.Google Scholar
Hoppe, B. and É. Tardos, The quickest transshipment problem, Mathematics of Operations Research 25 (2000), no. 1, 36–62.CrossRefGoogle Scholar
Iwata, S., Fleischer, L., and Fujishige, S., A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM 48 (2001), 761–777.CrossRefGoogle Scholar
Jarvis, J. J. and Ratliff, H. D., Some equivalent objectives for dynamic network flow problems, Management Science 28 (1982), 106–108.CrossRefGoogle Scholar
Kamiyama, N., Discrete Newton methods for the evacuation problem, Theoretical Computer Science 795 (2019), 510–519.CrossRefGoogle Scholar
Klinz, B., Personal communication cited in [31], 1994.Google Scholar
Klinz, B. and Woeginger, G. J., Minimum-cost dynamic flows: The series-parallel case, Networks 43 (2004), 153–162.CrossRefGoogle Scholar
Köhler, E., H. Möhring, R., and M. Skutella, Traffic networks and flows over time, Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation (Lerner, J., Wagner, D., and Zweig, K. A., eds.), Lecture Notes in Computer Science, vol. 5515, Springer, 2009, pp. 166–196.CrossRefGoogle Scholar
Korte, B. and Vygen, J., Combinatorial optimization: Theory and algorithms, 6th ed., Springer, 2018.CrossRefGoogle Scholar
Kotnyek, B., An annotated overview of dynamic network flows, Rapport de recherche 4936, INRIA Sophia Antipolis, 2003.Google Scholar
Lin, M. and Jaillet, P., On the quickest flow problem in dynamic networks – a parametric min-cost flow approach, Proceedings of the 26th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2015) (Indyk, P., ed.), 2015, pp. 1343–1356.CrossRefGoogle Scholar
Lovetskii, S. E. and Melamed, I. I., Dynamic network flows, Automation and Remote Control 48 (1987), 1417–1434, Translated from Avtomatika i Telemekhanika, 11 (1987), pp. 7–29.Google Scholar
Manzhulina, L., Personal communication, August 2023.Google Scholar
McCormick, S. T., Submodular function minimization, Discrete Optimization (Aardal, K., Nemhauser, G.L., and Weismantel, R., eds.), Handbooks in Operations Research and Management Science, vol. 12, Elsevier, 2005, pp. 321–391.CrossRefGoogle Scholar
Megiddo, N., Optimal flows in networks with multiple sources and sinks, Mathematical Programming 7 (1974), 97–107.CrossRefGoogle Scholar
Megiddo, N., Combinatorial optimization with rational objective functions, Mathematics of Operations Research 4 (1979), 414–424.CrossRefGoogle Scholar
Minieka, E., Maximal, lexicographic, and dynamic network flows, Operations Research 21 (1973), 517–527.CrossRefGoogle Scholar
Philpott, A. B., Continuous-time flows in networks, Mathematics of Operations Research 15 (1990), 640–661.CrossRefGoogle Scholar
Powell, W. B., Jaillet, P., and Odoni, A., Stochastic and dynamic networks and routing, Network Routing (Ball, M. O., Magnanti, T. L., Monma, C. L., and Nemhauser, G. L., eds.), Handbooks in Operations Research and Management Science, vol. 8, North–Holland, Amsterdam, The Netherlands, 1995, pp. 141–295.CrossRefGoogle Scholar
Saho, M. and Shigeno, M., Cancel-and-tighten algorithm for quickest flow problems, Networks 69 (2017), no. 2, 179–188.CrossRefGoogle Scholar
Schlöter, M., Flows over time and submodular function minimization, Ph.D. thesis, TU Berlin, Institut für Mathematik, 2018.Google Scholar
Schlöter, M., Earliest arrival transshipments in networks with multiple sinks, Proceedings of the 20th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2019) (Lodi, A. and Nagarajan, V., eds.), Lecture Notes in Computer Science, vol. 11480, Springer, 2019, pp. 370–384.CrossRefGoogle Scholar
Schlöter, M. and Skutella, M., Fast and memory-efficient algorithms for evacuation problems, Proceedings of the 28th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA 2017) (Klein, P. N., ed.), 2017, pp. 821–840.CrossRefGoogle Scholar
Schlöter, M., Skutella, M., and Tran, K. V., A faster algorithm for quickest transshipments via an extended discrete Newton method, Proceedings of the 33rd Annual ACM–SIAM Symposium on Discrete Algorithms (SODA 2022) (Naor, S. and Buchbinder, N., eds.), 2022, pp. 90–102.CrossRefGoogle Scholar
Schmidt, M. and Skutella, M., Earliest arrival flows in networks with multiple sinks, Discrete Applied Mathematics 164 (2014), 320–327.CrossRefGoogle Scholar
Schrijver, A., A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory, Series B 80 (2000), 346–355.CrossRefGoogle Scholar
Shapley, L. S., Cores of convex games, International Journal of Game Theory 1 (1971), 11–26.CrossRefGoogle Scholar
Skutella, M., An introduction to network flows over time, Research Trends in Combinatorial Optimization (Cook, W., Lovász, L., and Vygen, J., eds.), Springer, 2009, pp. 451–482.CrossRefGoogle Scholar
Skutella, M., A note on the quickest minimum cost transshipment problem, Operations Research Letters 51 (2023), no. 3, 255–258.CrossRefGoogle Scholar
Tjandra, S., Dynamic network optimization with application to the evacuation problem, Ph.D. thesis, Universität Kaiserslautern, 2003.Google Scholar
Wilkinson, W. L., An algorithm for universal maximal dynamic flows in a network, Operations Research 19 (1971), 1602–1612.CrossRefGoogle Scholar
Zadeh, N., A bad network problem for the simplex method and other minimum cost flow algorithms, Mathematical Programming 5 (1973), 255–266.CrossRefGoogle Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×