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

Borndörfer, Ralf ; Reuther, Markus ; Schlechte, Thomas ; Weider, Steffen

A Hypergraph Model for Railway Vehicle Rotation Planning

pdf-format:
14.pdf (0.5 MB)

Abstract

We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the "regularity" of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved.

BibTeX - Entry

@InProceedings{borndrfer_et_al:OASIcs:2011:3274,
  author =	{Ralf Bornd{\"o}rfer and Markus Reuther and Thomas Schlechte and Steffen Weider},
  title =	{{A Hypergraph Model for Railway Vehicle Rotation Planning}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{146--155},
  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/3274},
  URN =		{urn:nbn:de:0030-drops-32746},
  doi =		{10.4230/OASIcs.ATMOS.2011.146},
  annote =	{Keywords: Rolling Stock Planning, Hypergraph Modeling, Integer Programming,   Column Generation, Rapid Branching}
}

Keywords: Rolling Stock Planning, Hypergraph Modeling, Integer Programming, Column Generation, Rapid Branching
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