An Introduction to Network Flows Over Time

To appear in W. Cook, L. Lovász, and J. Vygen (eds.): Research Trends in Combinatorial Optimization. Springer, Berlin 2009, 451-482.

not available

dynamic network flows; flows over time

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.

Created on June 12 2008

Download as [PDF]