DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2008.1587

Dynamic Algorithms for Recoverable Robustness Problems

Authors: Serafino Cicerone, Gabriele Di Stefano, Michael Schachtebeck, and Anita Schöbel

Published in: OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)

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.

Cite as

Serafino Cicerone, Gabriele Di Stefano, Michael Schachtebeck, and Anita Schöbel. Dynamic Algorithms for Recoverable Robustness Problems. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{cicerone_et_al:OASIcs.ATMOS.2008.1587,
  author =	{Cicerone, Serafino and Di Stefano, Gabriele and Schachtebeck, Michael and Sch\"{o}bel, Anita},
  title =	{{Dynamic Algorithms for Recoverable Robustness Problems}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Fischetti, Matteo and Widmayer, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.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}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2008.1586

IP-based Techniques for Delay Management with Priority Decisions

Authors: Michael Schachtebeck and Anita Schöbel

Published in: OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)

Abstract

Delay management is an important issue in the daily operations of any railway company. The task is to update the planned timetable to a disposition timetable in such a way that the inconvenience for the passengers is as small as possible. The two main decisions that have to be made in this respect are the wait-depart decisions to decide which connections should be maintained in case of delays and the priority decisions that determine the order in which trains are allowed to pass a specific piece of track. They later are necessary in the capacitated case due to the limited capacity of the track system and are crucial to ensure that the headways between different trains are respected and that single-track traffic is routed correctly. While the wait-depart decisions have been intensively studied in literature (e.g. [Sch06,Gat07]), the priority decisions in the capacitated case have been neglected so far in delay management optimization models. In the current paper, we add the priority decisions to the integer programming formulation of the delay management problem and are hence able to deal with the capacitated case. Unfortunately, these constraints are disjunctive constraints that make the resulting event activity network more dense and destroy the property that it does not contain any directed cycle. Nevertheless, we are able to derive reduction techniques for the network which enable us to extend the formulation of the never-meet property from the uncapacitated delay management problem to the capacitated case. We then use our results to derive exact and heuristic solution procedures for solving the delay management problem. The results of the algorithms are evaluated both from a theoretical and a numerical point of view. The latter has been done within a case study using the railway network in the region of Harz, Germany.

Cite as

Michael Schachtebeck and Anita Schöbel. IP-based Techniques for Delay Management with Priority Decisions. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{schachtebeck_et_al:OASIcs.ATMOS.2008.1586,
  author =	{Schachtebeck, Michael and Sch\"{o}bel, Anita},
  title =	{{IP-based Techniques for Delay Management with Priority Decisions}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Fischetti, Matteo and Widmayer, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1586},
  URN =		{urn:nbn:de:0030-drops-15862},
  doi =		{10.4230/OASIcs.ATMOS.2008.1586},
  annote =	{Keywords: Public transportation, delay, integer programming, never-meet property, heuristics, preprocessing}
}

Search Results

Documents authored by Schachtebeck, Michael

Dynamic Algorithms for Recoverable Robustness Problems

Abstract

Cite as

IP-based Techniques for Delay Management with Priority Decisions

Abstract

Cite as

Thanks for your feedback!

Could not send message