Railway track allocation by rapid branching. (English) Zbl 1247.90170

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

Erlebach, Thomas (ed.) et al., 10th workshop on algorithmic approaches for transportation modelling, optimization, and systems (ATMOS’10). Selected papers based on the presentations at the workshop, September 9, 2010, Liverpool, United Kingdom. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-20-0). OASIcs – OpenAccess Series in Informatics 14, 13-23, electronic only (2010).

Summary: 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.
For the entire collection see [Zbl 1247.90009].

MSC:

90B80	Discrete location and assignment
90B06	Transportation, logistics and supply chain management
90C10	Integer programming
90C59	Approximation methods and heuristics in mathematical programming

Keywords:

track allocation problem; integer programming; rapid branching heuristic; proximal bundle method

Software:

TTPLib