Abstract: The crew pairing problem is one of the fundamental elements in strategic planning of airline companies. So far, crew pairing is mostly modeled as a deterministic problem, not concerning about flight delays. However, the airline industry is currently under great pressure to improve its on-time performance, so researches on robust models and solutions are in great need. Based on the literature review, a robust crew pairing model with consideration of stochastic disruptions is proposed in this paper. A deeper analysis of interdependencies of flight delays is given first in order to model the problem more accurately. For the purpose of better evaluating the costs caused by flight delays, delay costs are distinguished into normal delay cost and cancel cost according to whether those delays would result in partial flights cancellation. Due to the complexity of the crew paring problem itself, as well as the stochastic and interdependent features of flight delays, it is highly difficult to find feasible or optimal solutions of the model. Therefore, a heuristic column generation algorithm is introduced in this paper, which is proved to be highly efficient. The computational test shows that problems of real-world size can be solved efficiently within reasonable time. Furthermore, simulations are given to compare performances of our model with traditional deterministic model under same disruptions, and the results show that our model could highly increase robustness of crew pairing process.

Key words: crew pairing, stochastic disruptions, robustness, optimization model, column generation