Robust airline crew scheduling with flight flying time variability

Abstract

The crew pairing problem is one of the most important but challenging tasks for commercial airlines. However, the operation environment of the aviation industry is highly volatile with diverse uncertainties. Flight flying time variability is an important disruption that usually causes deviations of flight departure/arrival times from the schedule. Traditional crew pairing frameworks without considering flight flying time variability can generate pairings that are fragile to flight delays. However, the impact of flight flying time variability on crew pairings is under-explored. In this paper, we propose two robustness enhancement strategies based on the consideration of flight flying time variability (i.e., encouraging deviation-affected-free flights and discouraging deviation-affected flights). Besides, two robustness measurements are developed to construct two novel robust crew pairing models. One is time based while the other is number based. A customized column generation based solution algorithm is proposed. Computational experiments based on real flight schedules show that our new models can greatly enhance solution robustness (e.g., 49.1% more deviation-buffer time) at a price of an acceptable increase in operating costs (e.g., 9.7%) compared with the traditional model. Besides, extreme-delay flights can be completely avoided in the proposed models. Moreover, the solutions obtained from the time-based model show higher resistance against the disruption of flight flying time variability with a lower operating cost than the number-based model.