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)
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49+30-314-78654
email: skutella [at] math.tu-berlin.de.de
Researcher: Dr. Ines Spenke (Oct 2002 - Dec 2007)
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
Björn Stenzel (since Jan 2008)
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30 - 314 23598 
email: stenzel [at] 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.

Without doubt, the present regained interest and international recognition of the theoretical and practical importance of time-dependent flows was initiated by the research carried out in this project.

As suggested by the project's title, there are two essential project goals: In theory and applications. Time-dependent flows are much more difficult to analyze than static flows. On the theoretical side, the aim of this project is to investigate the structure and algorithmic complexity of time-dependent (multi-commodity) flow problems. Models, exact algorithms or approximations, and complexity results are of special interest. Particular questions ask for the influence of waiting, a better use of time-expanded graphs, and simpler models for flow-dependent transit times.

On the practical side, time-dependent (multi-commodity) flows turned out to be an efficient tool to adequately model applications, in particular in traffic and transport. It is the goal of this project, to build on the theoretical base, and make it actually usable in practice. To this end, in cooperation with industrial partners, practical time-dependent flow problems are to be modeled, and solution algorithms be implemented. Obviously, this second stage requires a further development of modeling and solution techniques since practitioner's needs clearly exceed the modeling cleanness of theory.

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 and results.

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.

Based on an applicational background, the routing of AGVs at HHLA Container terminal Altenwerder (CTA), 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.

Moreover, applications often require that the flow does not split into tiny f low 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.

During the first phase some industrial partners have been attracted by the projects topic. In particular, we continue the cooperation with the Hamburger Hafen und Logistik AG (HHLA) on the routing of Automated Guided V ehicles (AGVs) in the second phase. Interestingly, from an abstract point of view, conflict-free routing of vehicles (over time) is pursued by on-site switching railroads as well, e.g., at steel plants. We developed a first exact integer programming model which we propose to solve via branch-and-cut-and-price.

The versatile tool of mixed integer programming again proved helpful for time-dependent multicommodity flows. We considered the overnight rail freight transportation in Switzerland. The flow of goods has to be assigned to trains, trains must be scheduled, and most importantly, trains are split and re-arranged in two central hubs. In a sense, this is a system with two interdependent multicommodity flows on an common network: shipments and trains. Of crucial importance for the model quality (in terms of the linear programming relaxation) was to establish flow conservation over time at the hubs. We developed a model with meaningful fractional flow conservation over time, which helped finding integer solutions a lot.

Finally, in cooperation with B13 and B16, we studied transports and stacking operations in steel-slab logistics; we provided a lower bound obtained from a combinatorial relaxation solved via mixed integer programming. In particular, the stacking operations must be considered over time, a fact which considerably adds to the complexity of the problem.

Industrial Partners.

Publications.

A. Ceselli, M. Gatto, M. Lübbecke, M. Nunkesser, and H. Schilling. Optimizing the cargo express service of Swiss Federal Railways. Transportation Sci., 2008, To appear.
F. König, M. Lübbecke, R. Möhring, G. Schäfer, and I. Spenke. Solutions to real-world instances of PSPACE-complete stacking. In Proceedings of ESA 2007, volume 4698 of LNCS, pages 729-740. Springer, 2007.
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.