Railway Track Allocation

in press
  • This chapter addresses the classical task to decide which train runs on which track in a railway network. In this context a track allocation defines the precise routing of trains through a railway network, which usually has only a limited capacity. Moreover, the departure and arrival times at the visited stations of each train must simultaneously meet several operational and safety requirements. The problem to find the 'best possible' allocation for all trains is called the track allocation problem (TTP). Railway systems can be modeled on a very detailed scale covering the behavior of individual trains and the safety system to a large extent. However, those microscopic models are too big and not scalable to large networks, which make them inappropriate for mathematical optimization on a network wide level. Hence, most network optimization approaches consider simplified, so called macroscopic, models. In the first part we take a look at the challenge to construct a reliable and condensed macroscopic model for the associated microscopic model and to facilitate the transition between both models of different scale. In the main part we focus on the optimization problem for macroscopic models of the railway system. Based on classical graph-theoretical tools the track allocation problem is formulated to determine conflict-free paths in corresponding time-expanded graphs. We present standard integer programming model formulations for the track allocation problem that model resource or block conflicts in terms of packing constraints. In addition, we discuss the role of maximal clique inequalities and the concept of configuration networks. We will also present classical decomposition approaches like Lagrangian relaxation and bundle methods. Furthermore, we will discuss recently developed techniques, e.g., dynamic graph generation. Finally, we will discuss the status quo and show a vision of mathematical optimization to support real world track allocation, i.e. integrated train routing and scheduling, in a data-dominated and digitized railway future.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Gabrio Caimi, Frank Fischer, Thomas Schlechte
Document Type:Book chapter
Parent Title (English):Handbook of Optimization in the Railway Industry
First Page:141
Last Page:160
Series:International Series in Operations Research & Management Science
Publisher:Springer International Publishing
Year of first publication:2018