TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)Algorithms for Solving Time-Dependent Routing Problems with Exponential Output Size

COGA 5-Wheel

Page Content

to Navigation

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.

Publications

A tight bound on the speed-up through storage for quickest multi-commodity flows
Citation key GrossSkutella2015
Author Groß, Martin and Skutella, Martin
Pages 93–95
Year 2015
DOI 10.1016/j.orl.2014.12.008
Journal Operation Research Letters
Volume 43
Number 1
Link to original publication Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe