Railway Track Allocation by Rapid Branching

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

doi:10.4230/OASIcs.ATMOS.2010.13

Document

Railway Track Allocation by Rapid Branching

Authors Ralf Borndörfer, Thomas Schlechte, Steffen Weider

Part of: Volume: 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (ATMOS 2010)
Part of: Series: Open Access Series in Informatics (OASIcs)
Part of: Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2010-09-01

PDF

File

PDF

OASIcs.ATMOS.2010.13.pdf

Filesize: 0.6 MB
11 pages

Document Identifiers

DOI: 10.4230/OASIcs.ATMOS.2010.13
URN: urn:nbn:de:0030-drops-27465

Subject Classification

Keywords

track allocation problem
integer programming
rapid branching heuristic
proximal bundle method

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get BibTex

Ralf Borndörfer, Thomas Schlechte, and Steffen Weider. Railway Track Allocation by Rapid Branching. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 13-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010) https://doi.org/10.4230/OASIcs.ATMOS.2010.13

Author Details

Ralf Borndörfer

Thomas Schlechte

Steffen Weider

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail