A branch-and-price heuristic for the crew pairing problem with language constraints

In large commercial airlines, the monthly schedule (roster) of the crew members is usually determined by solving two problems sequentially, namely, the crew pairing problem (CPP) and the crew rostering problem (CRP). While the CPP finds a set of low-cost feasible anonymous pairings, the CRP assigns these pairings to the crew members to create a valid roster. The CRP often involves language constraints, which request language qualifications among the crew members operating some flights. In this case, the pairings returned by the CPP are not necessarily compatible with the qualifications of the available crew members, resulting in a large number of violated language constraints in the CRP. In this paper, we propose a new CPP variant, called the CPP with language constraints (CPPLC), that takes into account two types of soft language constraints that help producing more suitable pairings for satisfying the CRP language constraints. To solve the CPPLC, we develop a branch-and-price heuristic that includes an efficient partial pricing strategy for handling the large number of subproblems needed to model the language constraints. We also propose an acceleration technique to compute a high-quality (usually fractional) solution at the root node of the search tree. The proposed algorithm is tested on seven real-world datasets. We show that pairings produced by the CPPLC are better-suited for the CRP, resulting in a reduction of the number of violated CRP language constraints that varies between 61% and 96%, when compared to the pairings obtained from the traditional CPP.