contents
|
|
Dynamic Flows
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 traffic
networks. We investigate various theoretic questions in the context
of dynamic flows.
Our work
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:
|
top