### Page Content

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

Project directors: | Prof. Dr. Martin Skutella |
---|---|

Researcher: | Miriam Schlöter |

Support: | DFG Schwerpunktprogramm 1736 "Algorithms for BIG DATA" |

Since: | 2014 |

## 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.

## Publications

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.