Airline crew pairing with fatigue: Modeling and analysis

•A comprehensive crew pairing optimization model with a realistic account for fatigue.•A solution methodology based on column generation.•Pairings are generated based on a shortest path problem with fatigue.•A detailed numerical analysis based on real data for benchmarking.•Outperforms models that account for fatigue through hard constraints.

Crew fatigue is one of the main causes of airline accidents. Regulatory authorities such as the Federal Aviation Agency constantly introduce new fatigue regulations, often in the form of hard constraints on the length of duty and rest periods. The complex nature of travel-related fatigue, however, makes it difficult to account for it indirectly through such constraints. Recent studies show that fatigue depends on human factors such as the homeostatic process and the circadian body clock as well as time-zone differences. In this work, we explicitly account for fatigue in crew pairing optimization through the Three Process Model of Alertness, one of the most comprehensive fatigue models available in the literature. We provide a mathematical model for the crew pairing problem that incorporates fatigue and solve it using a column generation approach. Numerical analysis on two real data sets reveals that the proposed approach is able to reduce the crew fatigue levels substantially with minimal impact on cost. In particular, it is shown that hard constraints on fatigue may still lead to high fatigue levels and that jet-lag and time-zone differences have a major impact. The results of the tests also show that some of the rules and regulations in practice may be omitted if the fatigue is accounted for directly.