Efficient Algorithms for Path-Based and Dynamic Flow Problems in Large Networks

Project Head: Prof. Dr. Rolf H. Möhring
Prof. Dr. Martin Skutella
Researcher: Nadine Baumann
Heiko Schilling
Support: Deutsche Forschungsgemeinschaft (DFG)
within SPP 1126 "Algorithms on large and complex networks"
Cooperation partner: Daimler Chrysler AG


During the first funding period (between August 1, 2001 and July 31, 2003), the project was residing solely in the group Combinatorial Optimization & Graph Algorithms of Rolf Möhring at the TU Berlin. After Martin Skutella had moved from there to the MPI Saarbrücken and later to the University of Dortmund, the initial project has been considerably extended. It is being performed jointly by the groups of Rolf Möhring and Martin Skutella (for this part of the project see here) since September 1, 2003. August 1, 2005 the third and last funding period started. The whole project will be finished in August 2007.


Efficient algorithms are of crucial importance for a variety of network-based applications like traffic management and planning, telecommunications, and data traffic in the Internet. A typical example of such applications is the minimization of network load by simultaniously satisfying various user constraints. This naturally leads to optimization problems in networks, which are usually treated with standard techniques from network optimization, such as algorithms for shortest paths, maximum flows, min-cost multi-commodity flows. To cope with the various user constraints that often relate to the quality of the flow-carrying paths in the given solution, path-based formulations for different flow problems are of interest.

While the classical techniques for solving flow problems are efficient for common networks of smaller size and complexity, they often ignore substantial aspects that are characteristic of larger, more complex networks. Due to their input size, large and complex networks can generally not be supplied explicitly but instead have to be given in some implicit manner. For example, a traffic network can be modelled via a hierarchical structure where different street classes (local streets, highways, etc.) define different levels of hierarchy. Unfortunately, standard algorithms for network optimization are generally not capable of using this condensed representation of the networks but require the full expanded network.

In this project we want to develop and test algorithms for solving "path-based" flow and multi-commodity flow problems on large and complex networks. The theoretical challenges here are two-fold. First, the algorithms must be able to solve problems using only partial information about the network structure, since it is given implicitly. Second, the constraints of our problems call for new path-based algorithmic approaches in order to solve flow problems that are tailored for our large networks.

The practical test bed for these algorithms are traffic routing problems, on which we cooperate with DaimlerChrysler. For these applications, practical data is available for testing the developed algorithms.






See also: