EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

960. A Strong Formulation for the Train Dispatching Problem and its Solution

Invited abstract in session TC-54: Disruption management and recovery, stream Public Transport Optimization.

Tuesday, 12:30-14:00
Room: S01 (building: 101)

Authors (first author is the speaker)

1. Maik Schälicke
TU Dresden
2. Karl Nachtigall
Faculty of Transport and Traffic Sciences, Institut for Logistics and Aviation, Technical University of Dresden

Abstract

Disruptions in the operational flow of rail traffic can lead to conflicts between train movements, such that a scheduled timetable can no longer be realised. This is where dispatching is applied, existing conflicts are resolved and a dispatching timetable is provided. In the process, train paths are varied in their spatio-temporal course. This is called the train dispatching problem (TDP), which consists of selecting conflict-free train paths with minimum delay. Starting from a path-oriented formulation of the TDP, an IP is introduced. The IP selects the best of all potentially possible train paths via binary decision variables, which results in a big number of variables, so column generation is used to solve the problem. Instead of modelling pairwise conflicts, a stronger formulation is achieved by cliques formulated over the complete train path. The resulting pricing problem is a hard problem, because the shadow prices of the conflict cliques must be taken into account. When constructing a new train path, it must be determined whether this train path belongs to a conflict clique or not. This problem is tackled by a MIP. The methodology is tested on instances from a dispatching area in Germany. Numerical results show that the presented method achieves acceptable computation times with good solution quality while meeting the requirements for real-time train dispatching.

Keywords

Status: accepted

Back to the list of papers