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.2011.88
URN: urn:nbn:de:0030-drops-32699
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3269/
Go to the corresponding OASIcs Volume Portal

Dollevoet, Twan ; Schmidt, Marie ; Schöbel, Anita

Delay Management including Capacities of Stations

pdf-format:
9.pdf (0.5 MB)

Abstract

The question of delay management (DM) is whether trains should wait for delayed feeder trains or should depart on time. Solutions to this problem strongly depend on the capacity constraints of the tracks making sure that no two trains can use the same piece of track at the same time. While these capacity constraints have been included in integer programming formulations for DM, the capacity constraints of the stations (only offering a limited number of platforms) have been neglected so far. This can lead to highly infeasible solutions. In order to overcome this problem we suggest two new formulations for DM both including the stations' capacities. We present numerical results showing that the assignment-based formulation is clearly superior to the packing formulation. We furthermore propose an iterative algorithm in which we improve the platform assignment with respect to the current delays of the trains at each station in each step. We will show that this subproblem asks for coloring the nodes of a graph with a given number of colors while minimizing the weight of the conflicts. We show that the graph to be colored is an interval graph and that the problem can be solved in polynomial time by presenting a totally unimodular IP formulation.

BibTeX - Entry

@InProceedings{dollevoet_et_al:OASIcs:2011:3269,
  author =	{Twan Dollevoet and Marie Schmidt and Anita Sch{\"o}bel},
  title =	{{Delay Management including Capacities of Stations}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{88--99},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Alberto Caprara and Spyros Kontogiannis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3269},
  URN =		{urn:nbn:de:0030-drops-32699},
  doi =		{10.4230/OASIcs.ATMOS.2011.88},
  annote =	{Keywords: Delay management, station capacities}
}

Keywords: Delay management, station capacities
Collection: 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Issue Date: 2011
Date of publication: 19.09.2011

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