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

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

Railway Track Allocation by Rapid Branching

pdf-format:
2.pdf (0.6 MB)

Abstract

The track allocation problem, also known as train
routing problem or train timetabling problem, is to find a
conflict-free set of train routes of maximum value in a railway
network. Although it can be modeled as a standard path packing
problem, instances of sizes relevant for real-world railway
applications could not be solved up to now. We propose a rapid
branching column generation approach that integrates the solution of
the LP relaxation of a path coupling formulation of the problem with
a special rounding heuristic. The approach is based on and exploits
special properties of the bundle method for the approximate solution
of convex piecewise linear functions. Computational results for
difficult instances of the benchmark library TTPLIB are reported.

BibTeX - Entry

@InProceedings{borndrfer_et_al:OASIcs:2010:2746,
  author =	{Ralf Bornd{\"o}rfer and Thomas Schlechte and Steffen Weider},
  title =	{{Railway Track Allocation by Rapid Branching}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{13--23},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Thomas Erlebach and Marco L{\"u}bbecke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2746},
  URN =		{urn:nbn:de:0030-drops-27465},
  doi =		{10.4230/OASIcs.ATMOS.2010.13},
  annote =	{Keywords: track allocation problem, integer programming, rapid branching heuristic, proximal bundle method}
}

Keywords: track allocation problem, integer programming, rapid branching heuristic, proximal bundle method
Collection: 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)
Issue Date: 2010
Date of publication: 01.09.2010

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