direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Algorithms for Solving Time-Dependent Routing Problems with Exponential Output Size

Project Overview

Within the past decade, routing problems in various transportation networks have experienced a dramatic explosion of the size of data involved. This phenomenon has various causes, one of them being the demand for models and solutions that also take the dynamic (i. e., time-dependent) development of flow in transportation networks into account. Prominent examples are route guidance systems for traffic networks, evacuation planning for major districts or entire cities, and planning problems in huge logistics networks.

In the efficient algorithms and mathematical programming communities, fast methods for the solution of static (i.e., not time-dependent) routing problems have been developed over the past 50-60 years. In contrast, much less attention has been paid to the study of dynamic routing problems. This project addresses fundamental questions in the area of dynamic network flows and time-expanded networks which constitute an appropriate tool for modeling and solving time-dependent routing problems. Special emphasis is put on earliest arrival flows which capture the essence of evacuation planning.

An interesting artifact of dynamic flow problems is that static (i.e., small) input data leads to dynamic (i.e., big) output data. For such problems, whose solution size might be exponential in the input size, traditional complexity theory hardly explains their true difficulty. Other prominent examples can be found in parametric optimization, multi-criteria optimization, and enumeration problems. Beyond the main focus of this project, time-dependent routing, and on a more fundamental level, we aim at a better understanding of the curse of exponential output size, that is, the complexity of such problems and algorithms for their solution.


Disser, Yann and Skutella, Martin
The Simplex Algorithm is NP-mighty.
In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 858-872, 2015.  [pdf]

Arulselvan, Ashwin and Groß, Martin and Skutella, Martin
Graph Orientation and Flows Over Time.
In Ahn, Hee-Kap and Shin, Chan-Su (ed.)Algorithms and Computation, Lecture Notes in Computer Science, Vol. 8889, pp. 741–752, Springer International Publishing, 2014.

Groß, Martin and Skutella, Martin
A tight bound on the speed-up through storage for quickest multi-commodity flows.
Operation Research Letters, Vol. 43, pp. 93–95, 2015.

Schlöter, Miriam and Skutella, Martin
Fast and Memory-Efficient Algorithms for Evacuation Problems.
In Klein, Philip N. (ed.)Proceedings of the 28th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 821-840, SIAM, 2017.

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions