2026-07-23T08:30:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2746 2024-03-06T10:28:42Z ddc:004 open_access

Railway Track Allocation by Rapid Branching Borndörfer, Ralf Schlechte, Thomas Weider, Steffen track allocation problem integer programming rapid branching heuristic proximal bundle method 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ralf Borndörfer and Thomas Schlechte and Steffen Weider 2010 Is Part Of OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2010.13 urn:nbn:de:0030-drops-27465 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.13 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode