Thumbnail Image

An Introduction to Network Flows Over Time

Skutella, Martin

Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin

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.