Citation

Laplagne I, Kwan RSK, Kwan ASK. Public Transp. 2009; 1(1): 73-85.

Copyright

(Copyright © 2009, Holtzbrinck Springer Nature Publishing Group)

DOI

10.1007/s12469-008-0001-6

PMID

unavailable

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.