963
eng
reportzib
0
2007-08-02
2007-08-02
--
Solving Railway Track Allocation Problems
The \emph{optimal track allocation problem} (\textsc{OPTRA}), also known as the train routing problem or the train timetabling problem, is to find, in a given railway network, a conflict-free set of train routes of maximum value. We propose a novel integer programming formulation for this problem that is based on additional configuration' variables. Its LP-relaxation can be solved in polynomial time. These results are the theoretical basis for a column generation algorithm to solve large-scale track allocation problems. Computational results for the Hanover-Kassel-Fulda area of the German long distance railway network involving up to 570 trains are reported.
07-20
1438-0064
974
urn:nbn:de:0297-zib-9631
Appeared in: Operations Research Proceedings 2007. J. Kalcsics, S. Nickel (eds.)Springer 2008, pp. 117-122
Ralf BorndÃ¶rfer
unknown unknown
Thomas Schlechte
ZIB-Report
07-20
eng
uncontrolled
railway track allocation
eng
uncontrolled
timetabling
eng
uncontrolled
column generation
Informatik, Informationswissenschaft, allgemeine Werke
Transportation, logistics
Combinatorial optimization
Mathematical Optimization
BorndÃ¶rfer, Ralf
Schlechte, Thomas
https://opus4.kobv.de/opus4-zib/files/963/ZR_07_20.pdf
https://opus4.kobv.de/opus4-zib/files/963/ZR_07_20.ps