direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Preprints 2009

An Introduction to Network Flows Over Time
Citation key Report-022-2008
Author Martin Skutella
Year 2008
Number 022
Note To appear in W. Cook, L. Lovász, and J. Vygen (eds.): Research Trends in Combinatorial Optimization. Springer-Verlag, Berlin 2009, 451-482.
Institution Technische Universität Berlin, Institut für Mathematik
Abstract Flow variation over time is an important feature in network flow problems arising in various applications such as road or air traffic control, production systems, communication networks (e.g., the Internet), and financial flows. In such applications, flow values on arcs are not constant but may change over time. Moreover, there is a second temporal dimension in these applications. Usually, flow does not travel instantaneously through a network but requires a certain amount of time to travel through each arc. In particular, when routing decisions are being made in one part of a network, the effects can be seen in other parts of the network only after a certain time delay. Not only the amount of flow to be transmitted but also the time needed for the transmission plays an essential role. The above mentioned aspects of network flows are not captured by the classic static network flow models. This is where network flows over time come into play. They include a temporal dimension and therefore provide a more realistic modeling tool for numerous real-world applications. Only few textbooks on combinatorial optimization and network flows, however, mention this topic at all. This manuscript has been developed for the purpose of teaching in an advanced course on combinatorial optimization. We concentrate on flows over time (also called `dynamic flows' in the literature) with finite time horizon and constant capacities and constant transit times in a continuous time model.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry