A Suitable Model for a Bi-criteria Optimization Approach to Railway Track Allocation

Technical restrictions and challenging details let railway traffic become one of the most complex transportation systems. Routing trains in a conflict-free way through a track network is one of the basic scheduling problems for any railway company. This article focuses on a robust extension of this problem, also known as train timetabling problem (TTP), which consists in finding a schedule, a conflict free set of train routes, of maximum value for a given railway network. However, timetables are not only required to be profitable. Railway companies are also interested in reliable and robust solutions. Intuitively, we expect a more robust track allocation to be one where disruptions arising from delays are less likely to be propagated causing delays of subsequent trains. This trade-off between an efficient use of railway infrastructure and the prospects of recovery leads us to a bicriteria optimization approach. On the one hand we want to maximize the profit of a schedule, that is more or less to maximize the number of feasible routed trains. On the other hand if two trains are scheduled as tight as possible after each other it is clear that a delay of the first one always affects the subsequent train. We present extensions of the integer programming formulation in Borndofer & Schlechte [2007] for solving (TTP). These models can incorporate both aspects, because of the additional track configuration variables. We discuss how these variables can directly be used to measure a certain type of robustness of a timetable. For these models which can be solved by column generation techniques, we propose so-called scalarization techniques, see Ehrgott [2005], to determine efficient solutions. Here, an efficient solution is one which does not allow any improvement in profit and robustness at the same time. We prove that the LP-relaxation of the (TTP) including an additional ǫ-constraint This work was funded by the Federal Ministry of Economics and Technology (BMWi), project Trassenborse, grant 19M4031A. Konrad-Zuse-Zentrum fur Informationstechnik Berlin (ZIB), Takustr. 7, 14195 BerlinDahlem, Germany, Email {borndoerfer, schlechte}@zib.de