Airline cabin crew pairing with accurate characterization of cross-class substitution: A branch-and-price approach

Given the increasing heterogeneity of the types of aircraft operated, many airlines have switched from the traditional team scheduling approach to the individual scheduling approach for cabin crew planning. The individual approach not only allows for greater scheduling flexibility, but also helps achieve better utilization of available manpower through cross-class substitution (i.e., assigning a high-class crew member to substitute a low-class crew member), which is especially important in view of the recent industry-wide manpower shortage led by the post-pandemic traffic recovery. In this study, we present a new crew pairing approach with accurate characterization of cross-class substitution. This approach is novel as it can distinguish the substitutions among different pairs of crew classes with precise characterization of work time and costs. We develop a branch-and-price solution approach. A new specialized flight network that characterizes each crew class for each flight is constructed to realize the recognition of substitution heterogeneity. Although the size of the new flight network increases dramatically, it can be simplified to consider only one crew class for each flight in each column generation iteration without affecting optimality. We also propose a new column-fixing branching strategy to identify integer solutions for the newly developed model with non-negative integer variables. Computational experiments based on real-world collected flight schedules are conducted to validate the performance of the proposed approach in obtaining high-quality solutions (e.g., achieving a 0.01% optimality gap). The cost saving of the new crew pairing approach is examined, which is shown to vary greatly across different manpower availability levels and part-time cost settings. Besides, rich managerial insights are derived. Among others, we find that if it is expensive for a high crew class to directly substitute a low class (e.g., one that is experiencing a shortage), indirect assistance can be provided through an intermediate class.