Solving the Real-Time Train Dispatching Problem by Column Generation

Disruptions in the operational flow of rail traffic can lead to conflicts between train movements, making it impossible to adhere to the scheduled timetable. This is when dispatching comes into play: resolving existing conflicts and providing a revised timetable. In this process, train paths are adjusted in their spatial and temporal dimensions. This adjustment is known as the train dispatching problem (TDP), which involves selecting conflict-free train paths with minimal delay. Starting from a path-oriented formulation of the TDP, a binary linear decision model is introduced. For each possible train path, a binary decision variable indicates whether the path is utilized by a train. Each train path is constructed from a set of predefined path segments within a time–space network. Instead of modeling pairwise conflicts, stronger linear programming formulations are achieved by defining cliques over the complete train paths. The combinatorial nature of the path segments results in a large number of possible paths, necessitating the use of the column-generation method. Within the subproblem, the shadow prices of conflict cliques must be considered. When constructing a new train path, it must be determined whether it belongs to a clique. This issue is addressed using a mixed integer program. The methodology is tested on instances from a dispatching area in Germany. Numerical results show that the presented method achieves acceptable computation times and good solution quality, meeting the requirements for real-time dispatching.