The Train Driver Recovery Problem - a Set Partitioning Based Model and Solution Method

Natalia Jurjevna Rezanova, David Ryan

    Research output: Book/ReportReportResearchpeer-review

    385 Downloads (Pure)

    Abstract

    The need to recover a train driver schedule occurs during major disruptions in the daily railway operations. Using data from the train driver schedule of the Danish passenger railway operator DSB S-tog A/S, a solution method to the Train Driver Recovery Problem (TDRP) is developed. The TDRP is formulated as a set partitioning problem. The LP relaxation of the set partitioning formulation of the TDRP possesses strong integer properties. The proposed model is therefore solved via the LP relaxation and Branch & Price. Starting with a small set of drivers and train tasks assigned to the drivers within a certain time period, the LP relaxation of the set partitioning model is solved with column generation. If a feasible solution is not found, further drivers are gradually added to the problem or the optimization time period is increased. Fractions are resolved with a constraint branching strategy using the depth-first search of the Branch & Bound tree. Preliminarily results are encouraging, showing that nearly all tested real-life instances produce integer solutions to the LP relaxation and solutions are found within a few seconds.
    Original languageEnglish
    PublisherInformatics and Mathematical Modelling, Technical University of Denmark, DTU
    Publication statusPublished - 2006

    Cite this

    Rezanova, N. J., & Ryan, D. (2006). The Train Driver Recovery Problem - a Set Partitioning Based Model and Solution Method. Informatics and Mathematical Modelling, Technical University of Denmark, DTU.