Delay Management including Capacities of Stations

Twan Dollevoet, Marie Schmidt, A Schöbel

Research output: Chapter/Conference proceedingConference proceedingAcademicpeer-review

14 Citations (Scopus)
5 Downloads (Pure)


The question of delay management (DM) is whether trains should wait for delayed feeder trains or should depart on time. Solutions to this problem strongly depend on the capacity constraints of the tracks making sure that no two trains can use the same piece of track at the same time. While these capacity constraints have been included in integer programming formulations for DM, the capacity constraints of the stations (only offering a limited number of platforms) have been neglected so far. This can lead to highly infeasible solutions. In order to overcome this problem we suggest two new formulations for DM both including the stations' capacities. We present numerical results showing that the assignment-based formulation is clearly superior to the packing formulation. We furthermore propose an iterative algorithm in which we improve the platform assignment with respect to the current delays of the trains at each station in each step. We will show that this subproblem asks for coloring the nodes of a graph with a given number of colors while minimizing the weight of the conflicts. We show that the graph to be colored is an interval graph and that the problem can be solved in polynomial time by presenting a totally unimodular IP formulation.
Original languageEnglish
Title of host publication11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Editors Alberto Caprara, Spyros Kontogiannis
Place of PublicationDagstuhl, Germany
Number of pages12
Publication statusPublished - 2011


Dive into the research topics of 'Delay Management including Capacities of Stations'. Together they form a unique fingerprint.

Cite this