direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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.


Graph Orientation and Flows Over Time
Citation key ArulselvanGrossSkutella2014
Author Arulselvan, Ashwin and Groß, Martin and Skutella, Martin
Title of Book Algorithms and Computation
Pages 741–752
Year 2014
DOI 10.1007/978-3-319-13075-0_58
Volume 8889
Editor Ahn, Hee-Kap and Shin, Chan-Su
Publisher Springer International Publishing
Series Lecture Notes in Computer Science
Link to original publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions