Solving the Real-Time Train Dispatching Problem by Column Generation

Maik Schälicke () and Karl Nachtigall ()
Additional contact information
Maik Schälicke: Dresden University of Technology, 01069 Dresden, Germany
Karl Nachtigall: Dresden University of Technology, 01069 Dresden, Germany

Transportation Science, 2025, vol. 59, issue 3, 587-602

Abstract: 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.

Keywords: train dispatching; column generation; speed profiles; train path segments (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2023.0215 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:59:y:2025:i:3:p:587-602

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().