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.