Abstract:
A prominent problem in airline crew scheduling is the pairings or Tour-of-Duty planning
problem. The objective is to determine a set of pairings (or Tours-of-Duty) for a crew group
to minimize the planned cost of operating a schedule of flights. However, due to unforeseen
events the performance in operation can differ considerably from planning, sometimes causing
significant additional recovery costs.
In recent years there has been a growing interest in robust crew scheduling. Here, the
aim is to find solutions that are “cheap” in terms of planned cost as well as being robust,
meaning that they are less likely to be disrupted in case of delays. Taking the stochastic
nature of delays into account, Yen and Birge (2006) formulate the problem as a two-stage
stochastic integer programme and develop an algorithm to solve this problem. Based on
the contradictory nature of the goals, Ehrgott and Ryan (2002) formulate a bi-objective set
partitioning model and employ elastic constraint scalarization to enable the solution by set
partitioning algorithms commercially used in crew scheduling software.
In this paper we compare the two solution approaches. We improve the algorithm of Yen
and Birge (2006) and implement both methods with a commercial crew scheduling software.
The results of both methods are compared with respect to characteristics of robust solutions,
such as the number of aircraft changes for crew. We also conduct experiments to simulate the
performance of the obtained solutions. All experiments are performed using actual schedule
data for a New Zealand domestic airline.
