  The crew pairing problem (CPP) is generally modelled as a set partitioning
problem where the flights have to be partitioned in pairings. A pairing is a
sequence of flight legs separated by connection time and rest periods that
starts and ends at the same base. Because of the extensive list of complex
rules and regulations, determining whether a sequence of flights constitutes a
feasible pairing can be quite difficult by itself, making CPP one of the
hardest of the airline planning problems. In this paper, we first propose to
improve the prototype Baseline solver of Desaulniers et al. (2020) by adding
dynamic control strategies to obtain an efficient solver for large-scale CPPs:
Commercial-GENCOL-DCA. These solvers are designed to aggregate the flights
covering constraints to reduce the size of the problem. Then, we use machine
learning (ML) to produce clusters of flights having a high probability of being
performed consecutively by the same crew. The solver combines several advanced
Operations Research techniques to assemble and modify these clusters, when
necessary, to produce a good solution. We show, on monthly CPPs with up to 50
000 flights, that Commercial-GENCOL-DCA with clusters produced by ML-based
heuristics outperforms Baseline fed by initial clusters that are pairings of a
solution obtained by rolling horizon with GENCOL. The reduction of solution
cost averages between 6.8% and 8.52%, which is mainly due to the reduction in
the cost of global constraints between 69.79% and 78.11%.
