@article{ref1,
title="Critical time windowed train driver relief opportunities",
journal="Public transport",
year="2009",
author="Kwan, Ann S. K. and Kwan, Raymond S. K. and Laplagne, Ignacio",
volume="1",
number="1",
pages="73-85",
abstract="Train driver scheduling is the problem of constructing an efficient schedule of driver shifts, each of which contains a sequence of work on one or more trains separated by breaks. Relief opportunities (ROs) occur when trains stop at a station. While relieving on arrival at a train station is the preferred practice in the UK rail industry, considering relieving at other times within the full window of relief opportunities (WRO) at a stop might allow for a schedule optimization algorithm to build better schedules. However, simply expanding each WRO into ROs at individual minutes within the WRO would exponentially increase the complexity of the combinatorial optimization problem. A rational approach would be to be selective in considering the WROs when applying Generate-and-Select (GaS); this could either take the form of a pre-processing stage to GaS, or that of augmenting (or even replacing) the generation phase of GaS.In this paper we first show a simple example where approximating WROs by a single relief point results in inefficient schedules, and hints at the complexity of exploiting WROs. We then study the potential of WROs in terms of the new spells and/or shifts they may allow to be created. We propose a heuristic extension to the GaS generation phase, where WROs are analysed in relation to individual scheduling constraints; ROs within WROs that are deemed useful are added to the set of arrival-time ROs. Results show an improvement over the traditional approach in a number of real-life instances from UK operations.We also present a constructive method to analyse a combination of scheduling constraints. Results show that the method is effective in exploiting constraints that may be skipped or difficult to consider by non-constructive approaches.<p />",
language="",
issn="1866-749X",
doi="10.1007/s12469-008-0001-6",
url="http://dx.doi.org/10.1007/s12469-008-0001-6"
}