License
when quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2008.1586
URN: urn:nbn:de:0030-drops-15862
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1586/

Schachtebeck, Michael ; Schöbel, Anita

IP-based Techniques for Delay Management with Priority Decisions

pdf-format:
Dokument 1.pdf (326 KB)


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.

BibTeX - Entry

@InProceedings{schachtebeck_et_al:OASIcs:2008:1586,
  author =	{Michael Schachtebeck and Anita Sch{\"o}bel},
  title =	{{IP-based Techniques for Delay Management with Priority Decisions}},
  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/1586},
  URN =		{urn:nbn:de:0030-drops-15862},
  doi =		{http://dx.doi.org/10.4230/OASIcs.ATMOS.2008.1586},
  annote =	{Keywords: Public transportation, delay, integer programming, never-meet property, heuristics, preprocessing}
}

Keywords: Public transportation, delay, integer programming, never-meet property, heuristics, preprocessing
Seminar: 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 Published by LZI