Project description.

Background.

Flow variation over time is an important aspect 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 [2]. The common feature are networks with capacities and transit times on the arcs. Flow portions travel along the arcs according to these transit times and capacities. Commonly, such tasks are modeled as static multi-commodity flow problems, handling time-dependent aspects via time expanded networks [1], via simulation models or via very small dynamic models that are based on differential equations. Efficient algorithmic techniques tailored to the dynamic nature of these flows over time are of high interest.

Expertise.

Expert knowledge has been gained during a project within the bmb+f-program Neue Mathematische Verfahren in Industrie und Dienstleistungen (in cooperation with DaimlerChrysler) and in a project within the DFG Schwerpunktprogramm Algorithms for large and complex networks. The work is also related to an earlier project in cooperation with German Telekom.

Research program.

The goal of this project is to develop optimization methods and algorithms for flow over time problems. The test case for this research are applications in traffic management and route guidance systems.

Special emphasis in the first phase is put on: i) examining the theoretical structure of 'good' time-dependent flows for multi-commodity flow problems such as the one discussed in [3]; ii) developing and investigating simplified time-dependent flow models with flow-dependent transit times; iii) studying the integration of differential equations into discrete network models; and iv) implementing simulation tools for analyzing and testing the applicability of different models and approaches.

During the first phase some industrial partners have been attracted by the projects topic. We will continue to develop algorithms for practical applications in the second period.

Industrial Partners.

• Hamburger Hafen und Logistik AG (HHLA)
• Computer Sciences Corporation (CSC)
• Planung, Transport, Verkehr AG (PTV)
• Products and Systems of Information Technology AG (PSI)

Results.

Based on an applicational background flow over time problems in grid graphs have been investigated. The focus was set on analyzing the complexity and the approximability of the problem of finding a quickest flow for given demands. Several specific requirements coming from the applications have been considered as for example time windows on edges, waiting policies and node capacities. Such additional demands yield that standard flow over time approaches cannot be used. For a variety of combinations of practical requirements their influence on the problems complexity was shown. In some cases approximation algorithms exploiting the grid structure could be derived.

Applications often require that the flow does not split into tiny flow portions along a high number of paths. Such a requirement has been introduced by Baier, K;hler and Skutella in 2002 by so called k-splittable flows. In several publications, a variety of complexity results for k-splittable flow problems in directed and undirected graphs for constant values of k and for k that depends on graph parameters is studied. Polynomially solvable and NP-hard k-splittable flow problems are identified. New bounds for the approximability of such problems are shown. On a special class of graphs, graphs of bounded treewidth, problems that are in general NP-hard are solved to optimality or near-optimality.

Publications.

Posters.

• Poster 2006
• Poster 2003

Diploma students.

• Ronald Koch, Komplexität und Approximierbarkeit von k-spaltbaren Flüssen,2004.

References (at project start).