1 results for Report, A comparison of stochastic programming and bi-objective optimization approaches to robust airline crew scheduling, 2007

  • A comparison of stochastic programming and bi-objective optimization approaches to robust airline crew scheduling

    Tam, Bassy; Ehrgott, Matthias; Ryan, David; Zakeri, Golbon (2007)

    Report
    The University of Auckland Library

    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.

    View record details