TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)RobuNet

COGA 5-Wheel

Page Content

to Navigation

Robust Network Design for Large Scale Logistics Networks

4flow AG

August 2012 - May 2015
Project heads:
Yann Disser
Britta Peis
Sebastian Stiller
Rolf H. Möhring

Martin Skutella
Wiebke Höhn, Alexander Richter 
Cooperation partner:
4flow AG
Official website:
Europäischer Fonds für Regionale Entwicklung (EFRE)
Investitionsbank Berlin (IBB)


Background and motivation

Facility location decisions belong to the most important cost drivers in the design of modern logistics networks. Moreover these longterm investments determine the framework for finding cost efficient solutions in tactical and operational planning. This close interrelation between operational cost and longterm investments makes an integrated planning of both aspects desirable.

This integrated approach is even more complex due to the disparate time horizons of both planning aspects. From mathematical point of view, this belongs to the realm of optimizing over scenarios, since the scenario of demands is unknown at the time of investments and the investments have to be convenient for many scenarios. E.g., fluctuations of fuel prices or differing developments of labor costs in different regions constitute relevant uncertainties in designing logistic networks.

In practice it is common to firstly ignore uncertainties in input data and to react a-postiori to changes. It has been shown that with this practice already small fluctuations can lead to much worse results as opposed to a robust optimization, a modelling technique that considers the possible range of fluctuations in input data a priori. A large gap between the actual state of research and the logistic practice has to be closed here. On the other hand, it is essential to the research of robust optimization to understand which kinds of uncertainties appear in practice.

The goal of RobuNet is to develop solutions techniques that are tailored for the use in large scale logistics networks, which requires to link actual mathematical research with practical expertise.

Research program

The main research focus is on facility location decisions in logistics networks which lie at the intersection of the classical research fields of network flow, covering and packing problems. Moreover they are affected by planning uncertainties and have to be considered in very large networks which requires efficient algorithms in the mathematical sense. To address the whole range of the problem we chose a stepwise approach, that is in each step we disregard a single aspect of the problem. Especially when dealing with uncertainties a profound understanding of the deterministic version is required as a starting point. A more detailed outline of the research program is listed below.


  • Analysis of uncertainties, network structures, and the decision and information model
  • Identification of relevant optimization potential
  • Development of mathematical models

Deterministic facility location in logistics networks

  • Mathematical problem structure
  • Development and analysis of efficient algorithms for facility location decisions with consolidated routing
  • Development of methods for problem specific network separation

Optimizing over scenarios

  • Mathematical foundation for logistics networks with uncertainties
  • Stochastic optimization models
  • Robust optimization models

Non-standard decision-and-information models

  • Increase of network robustness against strong singular fluctuations
  • Development and analysis of reoptimization techniques
  • Development and analysis of methods for incremental location decisions

Evaluation on real-world instances and implementation of a demonstrator

  • Case studies for the evaluation of the different approaches for robust optimization
  • Implementation of functionalities for analysis and visualization
  • Evaluation of practicability
  • Compilation of a toolbox for robust planning in logistics


Maximum Multicommodity Flows over Time without Intermediate Storage
Citation key GrossSkutella2012a
Author Groß, Martin and Skutella, Martin
Title of Book Algorithms – ESA 2012
Pages 539-550
Year 2012
ISBN 978-3-642-33089-6
DOI 10.1007/978-3-642-33090-2_47
Volume 7501
Editor Epstein, Leah and Ferragina, Paolo
Publisher Springer Berlin / Heidelberg
Series Lecture Notes in Computer Science
Institution TU Berlin
Abstract Flows over time generalize classical “static” network flows by introducing a temporal dimension. They can thus be used to model non-instantaneous travel times for flow and variation of flow values over time, both of which are crucial characteristics in many real-world routing problems. There exist two different models of flows over time with respect to flow conservation: one where flow might be stored temporarily at intermediate nodes and a stricter model where flow entering an intermediate node must instantaneously progress to the next arc. While the first model is in general easier to handle, the second model is often more realistic since in applications like, e.g., road traffic, storage of flow at intermediate nodes is undesired or even prohibited. The main contribution of this paper is a fully polynomial time approximation scheme (FPTAS) for (min-cost) multi-commodity flows over time without intermediate storage. This improves upon the best previously known (2 + ε )-approximation algorithm presented 10 years ago by Fleischer and Skutella (IPCO 2002).
Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe