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

Fischer, Frank ; Helmberg, Christoph ; Janßen, Jürgen ; Krostitz, Boris

Towards Solving Very Large Scale Train Timetabling Problems by Lagrangian Relaxation

pdf-format:
08002.Fischer.1585.pdf (0.2 MB)

Abstract

The train timetabling problem considered is to find conflict free routes for a set of trains in a given railway network so that cer- tain time window conditions are satisfied. We deal with the very large scale problem of constructing such timetables for the German railway network. A number of restrictions on different train types like freight trains or passenger trains have to be observed, e.g., sequence dependent headway times, station capacities, and stopping times. In order to handle the enormous number of variables and constraints we employ Lagrangian relaxation of the conflict constraints combined with a cutting plane approach. The model is solved by a bundle method; its primal aggregate is used for separation and as starting point for rounding heuristics. We present some promising results towards handling a test instance com- prising ten percent of the entire network.

BibTeX - Entry

@InProceedings{fischer_et_al:OASIcs:2008:1585,
  author =	{Frank Fischer and Christoph Helmberg and J{\"u}rgen Jan{\ss}en and Boris Krostitz},
  title =	{{Towards Solving Very Large Scale Train Timetabling Problems by Lagrangian Relaxation}},
  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/1585},
  URN =		{urn:nbn:de:0030-drops-15850},
  doi =		{10.4230/OASIcs.ATMOS.2008.1585},
  annote =	{Keywords: }
}

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