Models for Railway Track Allocation
Please always quote using this URN: urn:nbn:de:0297-zib-9451
- This article is about the optimal track allocation problem (OPTRA) 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: a standard formulation that models block conflicts in terms of packing constraints, and a new extended formulation that is based on additional configuration' variables. We show that the packing constraints in the standard formulation stem from an interval graph, and that they can 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 extended formulation produces the same LP bound, and that it can also be computed with this model in polynomial time. Albeit the two formulations are in this sense equivalent, the extended formulation has advantages from a computational point of view, because it features a constant number of rows and is therefore amenable to standard column generation techniques. Results of an empirical model comparison on mesoscopic data for the Hannover-Fulda-Kassel region of the German long distance railway network are reported.
Author: | Ralf BorndörferORCiD, Thomas Schlechte |
---|---|
Document Type: | ZIB-Report |
Tag: | Combinatorial Optimization; Linear and Integer Programming; Railway Slot Allocation; Train Timetabling |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization |
Contributing Corporation: | This work was funded by the Federal Ministry of Economics and Technology (BMWi), project Trassenbörse, grant 19M4031A |
Date of first Publication: | 2007/01/08 |
Series (Serial Number): | ZIB-Report (07-02) |
ZIB-Reportnumber: | 07-02 |
Published in: | Appeared in: Proceeding of the 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2007) (C. Liebchen, R. K. Ahuja und J. A. Mesa, Hg.), Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, 2007 |