2026-07-25T14:19:33Z https://drops.dagstuhl.de/oai

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

05. Models for Railway Track Allocation Borndörfer, Ralf Schlechte, Thomas Track allocation train timetabling,integer programming column generation The optimal track allocation problem (OPTRA) is to find, in a given railway network, a conflict free set of train routes of maximum value. We study two types of integer programming formulations for this problem: a standard formulation that models block conflicts in terms of packing constraints, and a novel formulation of the `extended' type that is based on additional `configuration' variables. The packing constraints in the standard formulation stem from an interval graph and can therefore be separated in polynomial time. It follows that the LP-relaxation of a strong version of this model, including all clique inequalities from block conflicts, can be solved in polynomial time. We prove that the LP-relaxation of the extended formulation can also be solved in polynomial time, and that it produces the same LP-bound. Albeit the two formulations are in this sense equivalent, the extended formulation has advantages from a computational point of view. It features a constant number of rows and is amenable to standard column generation techniques. Results of an empirical model comparison on mesoscopic data for the Hanover-Fulda-Kassel region of the German long distance railway network are reported. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ralf Borndörfer and Thomas Schlechte 2007 Is Part Of OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2007.1170 urn:nbn:de:0030-drops-11701 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1170 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode