Flows over Time
Time plays an important role in transport:
- People use cars to move, often a vast number of cars at the same time on the same route. Still they want to reach their destinations fast.
- Huge amounts of data run through communication networks. Network capacities limit the throughput and data sent along a connection block this way for other data. Nevertheless, nobody wants to wait to get data.
- Goods traverse complex production processes. Production costs are often influenced by the pass-through time.
All these time-oriented processes benefit from good structure and control. Planning them requires an appropriate model.
There is a variety of very different mathematical approaches to model dynamic behaviour. In combinatorial optimization it can be modelled as flows in networks. The underlying structure, for example streets and junctions in traffic systems, is described as a network. Moving objects like cars are interpreted as flow in this network.
Research in flow theory from the last forty years has been focussed on static flows. Such flows do not reflect time. Flows over time or dynamic flows as a generalization of static flows provide an appropriate way to include time aspects. For both static and dynamic flows, underlying networks consists of nodes and arcs with arc capacities. In static flows, to every arc a flow value is assigned limited by the given arc capacity. Flows over time, however, are described by a flow rate which enters an arc at a specified time. Arc capacities limit the amount of flow entering an arc at the same time and transit times describe how long it takes to travel over an arc.
Our work is strongly related to applications in road networks. We investigate various theoretic questions in the context of dynamic flows.
2006
- Ines Spenke, Complexity and Approximation of Static k-Splittable Flows and Dynamic Grid Flows, PhD thesis
2005
- Alexander Hall and Heiko Schilling, Flows over Time: Towards a more Realistic and Computationally Tractable Model, ALENEX 2005
2003
- Alexander Hall, Katharina Langkau, and Martin Skutella, An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times, APPROX 2003
- Alexander Hall, Steffen Hippler, and Martin Skutella, Multicommodity Flows over Time: Efficient Algorithms and Complexity, ICALP 2003
- Katharina Langkau, Flows Over Time with Flow-Dependent Transit Times, PhD thesis
- Nadine Baumann, Netzwerkflüsse mit flussabhängigen Fahrzeiten: Modelle und Anwendungen für das Evakuierungsproblem, Diploma thesis
- Lydia Franck, Dynamische Flüsse in Netzwerken: Verkehrslenkung bei lastabhängigen Fahrzeiten, Diploma thesis
2002
- Lisa Fleischer and Martin Skutella, The Quickest Multicommodity Flow Problem, IPCO 2002
- Ekkehard Köhler, Rolf H. Möhring, and Martin Skutella, Traffic Networks and Flows Over Time
- Lisa Fleischer and Martin Skutella, Minimum Cost Flows Over Time without Intermediate Storage, SODA 2003
- Ekkehard Köhler, Katharina Langkau, and Martin Skutella, Time-Expanded Graphs for Flow-Dependent Transit Times, ESA 2002
- Steffen Hippler, Simple Flows Over Time, Diploma thesis
2001
- Ekkehard Köhler and Martin Skutella, Flows over time with load-dependent transit times, SODA 2002
- Kerstin Kuhligk, Lenkung von Verkehrsströmen mittels dynamischer Flüsse - ein semidynamisches Optimierungsverfahren, Diploma thesis