License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2014.79
URN: urn:nbn:de:0030-drops-47549
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4754/
Go to the corresponding OASIcs Volume Portal

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

A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem

pdf-format:
p079-07-borndoerfer.pdf (0.7 MB)

Abstract

We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.

BibTeX - Entry

@InProceedings{borndrfer_et_al:OASIcs:2014:4754,
  author =	{Ralf Bornd{\"o}rfer and Markus Reuther and Thomas Schlechte},
  title =	{{A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation  Problem}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{79--91},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Stefan Funke and Mat{\'u}{\v{s}} Mihal{\'a}k},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4754},
  URN =		{urn:nbn:de:0030-drops-47549},
  doi =		{10.4230/OASIcs.ATMOS.2014.79},
  annote =	{Keywords: Coarse-To-Fine Linear Programming, Rolling Stock Rotation Problem}
}

Keywords: Coarse-To-Fine Linear Programming, Rolling Stock Rotation Problem
Collection: 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Issue Date: 2014
Date of publication: 19.09.2014

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