Project B8: Time-dependent Multicommodity Flows: Theory and Applications

DFG Research Center Matheon Technische Universitšt Berlin

Duration: First Period: October 2002 - May 2006
Second Period: June 2006 - May 2008
Project director: Prof. Dr. Rolf H. Möhring
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30 - 2 45 94
email: moehring@math.tu-berlin.de
Dr. Marco Lübbecke (since Aug 2007)
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30 - 2 57 35
email: m.luebbecke [at] math.tu-berlin.de
Prof. Dr. Ekkehard Köhler (June 2006 - May 2007)
Brandenburgische Technische Universität Cottbus, Fachbereich Mathematik, Postfach 10 13 44, D-03013 Cottbus, Germany
Tel: +49-355/69-2933
email: ekoehler@math.tu-cottbus.de
Prof. Dr. Martin Skutella (Oct 2002 - May 2006)
Universität Dortmund, Fachbereich Mathematik, Vogelpothsweg 87, 44227 Dortmund, Germany
Tel: +49+231-755-7213
email: martin.skutella@uni-dortmund.de
Researcher: Dr. Ines Spenke
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30 - / 314 25739 
email: spenke@math.tu-berlin.de
Support: MATHEON - DFG Research Center "Mathematics for Key Technologies"

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.

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.

I. Spenke, Complexity and Approximation of Static k-Splittable Flows and Dynamic Grid Flows, PhD thesis, Cuvillier Verlag, 2007.
R. Koch, I. Spenke, Complexity and Approximability of k-Splittable Flows, accepted for Theory of Computing Systems, 2007.
R. Koch, M. Skutella, I. Spenke, Maximum k-Splittable Flows, Theoretical Computer Science, 2006.
R. Koch, M. Skutella, I. Spenke, Approximation and Complexity of k-Splittable Flows, Proceedings of the third Workshop on Approximation and Online Algorithms, 2005

Posters.

Diploma students.

References (at project start).

[1] M. Carey and E. Subrahmanian.An approach for modeling time-varying flows on congested networks. Transp. Res. B, 34:157--183, 2000. 
[2] W. B. Powell, P. Jaillet, and A. Odoni. Stochastic and dynamic networks and routing. In M.O. Ball et al., editors, Network Routing, volume~8 of Handbooks in Operations Research and Management Science, pages 141--295. Elsevier Science B. V., Amsterdam, 1995. 
[3] M. Skutella. Approximating the single source unsplittable min-cost flow problem. Mathematical Programming B, to appear.