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

Publication: Research - peer-reviewJournal article – Annual report year: 2010

View graph of relations

The need to recover a train driver schedule occurs during major disruptions in the daily railway operations. Based on data from 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. We define a disruption neighbourhood by identifying a small set of drivers and train tasks directly affected by the disruption. Based on the disruption neighbourhood, the TDRP model is formed and solved. If the TDRP solution provides a feasible recovery for the drivers within the disruption neighbourhood, we consider that the problem is solved. However, if a feasible solution is not found, the disruption neighbourhood is expanded by adding further drivers or increasing the recovery time period. Fractional solutions to the LP relaxation of the TDRP are resolved with a constraint branching strategy using the depth-first search of the Branch & Bound tree. The LP relaxation of the TDRP possesses strong integer properties. We present test scenarios generated from the historical real-life operations data of DSB S-tog A/S. The numerical results show that all but one tested instances produce integer solutions to the LP relaxation of the TDRP and solutions are found within a few seconds.
Original languageEnglish
JournalComputers & Operations Research
Issue number5
Pages (from-to)845-856
StatePublished - 2010
CitationsWeb of Science® Times Cited: 24


  • Constraint branching, Real-time disruption recovery, Set partitioning, Rail crew scheduling
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

ID: 4858518