Access Restriction

Author Laplagne, Ignacio ♦ Kwan, Raymond S. K. ♦ Kwan, Ann S. K.
Source SpringerLink
Content type Text
Publisher Springer-Verlag
File Format PDF
Copyright Year ©2008
Language English
Subject Domain (in DDC) Social sciences ♦ Economics ♦ Technology ♦ Management & auxiliary services ♦ General management
Subject Keyword Crew scheduling ♦ Time windows ♦ Computer-Aided Engineering (CAD, CAE) and Design ♦ Automotive Engineering ♦ Operations Research/Decision Theory
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.
ISSN 1866749X
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2008-11-01
Publisher Place Berlin, Heidelberg
e-ISSN 16137159
Journal Public Transport
Volume Number 1
Issue Number 1
Page Count 13
Starting Page 73
Ending Page 85

Open content in new tab

   Open content in new tab
Source: SpringerLink