License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2008.1587
URN: urn:nbn:de:0030-drops-15876
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1587/
Go to the corresponding OASIcs Volume Portal

Cicerone, Serafino ; Di Stefano, Gabriele ; Schachtebeck, Michael ; Schöbel, Anita

Dynamic Algorithms for Recoverable Robustness Problems

pdf-format:
08002.Cicerone.1587.pdf (0.2 MB)

Abstract

Recently, the recoverable robustness model has been introduced in the optimization area. This model allows to consider disruptions (input data changes) in a unified way, that is, during both the strategic planning phase and the operational phase. Although the model represents a significant improvement, it has the following drawback: we are typically not facing only one disruption, but many of them might appear one after another. In this case, the solutions provided in the context of the recoverable robustness are not satisfying.
In this paper we extend the concept of recoverable robustness to deal not only with one single recovery step, but with arbitrarily many recovery steps. To this aim, we introduce the notion of dynamic recoverable robustness problems. We apply the new model in the context of timetabling and delay management problems. We are interested in finding efficient dynamic robust algorithms for solving the timetabling problem and in evaluating the price of robustness of the proposed solutions.

BibTeX - Entry

@InProceedings{cicerone_et_al:OASIcs:2008:1587,
  author =	{Serafino Cicerone and Gabriele Di Stefano and Michael Schachtebeck and Anita Sch{\"o}bel},
  title =	{{Dynamic Algorithms for Recoverable Robustness Problems}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) },
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Matteo Fischetti and Peter Widmayer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1587},
  URN =		{urn:nbn:de:0030-drops-15876},
  doi =		{10.4230/OASIcs.ATMOS.2008.1587},
  annote =	{Keywords: Robustness, optimization problems, dynamic algorithms, timetabling, delay management}
}

Keywords: Robustness, optimization problems, dynamic algorithms, timetabling, delay management
Collection: 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)
Issue Date: 2008
Date of publication: 24.09.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI