<  Back to the Polytechnique Montréal portal

Machine learning in airline crew pairing to construct initial clusters for dynamic constraint aggregation

Yassine Yaakoubi, François Soumis and Simon Lacoste-Julien

Article (2020)

Open Acess document in PolyPublie and at official publisher
Open Access to the full text of this document
Published Version
Terms of Use: Creative Commons Attribution Non-commercial No Derivatives
Download (516kB)
Show abstract
Hide abstract


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)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%.

Uncontrolled Keywords

Machine learning, Column generation, Constraint aggregation, Airline crew scheduling, Crew pairing

Subjects: 1600 Industrial engineering > 1600 Industrial engineering
1600 Industrial engineering > 1605 Human factors engineering
Department: Department of Mathematics and Industrial Engineering
Research Center: GERAD - Research Group in Decision Analysis
Funders: CRSNG/NSERC - Collaborative Research and Development Grant, IVADO, IBS Software - AD OPT
PolyPublie URL: https://publications.polymtl.ca/9271/
Journal Title: EURO Journal on Transportation and Logistics (vol. 9, no. 4)
Publisher: Elsevier
DOI: 10.1016/j.ejtl.2020.100020
Official URL: https://doi.org/10.1016/j.ejtl.2020.100020
Date Deposited: 05 Apr 2022 11:35
Last Modified: 15 May 2023 18:30
Cite in APA 7: Yaakoubi, Y., Soumis, F., & Lacoste-Julien, S. (2020). Machine learning in airline crew pairing to construct initial clusters for dynamic constraint aggregation. EURO Journal on Transportation and Logistics, 9(4), 14 pages. https://doi.org/10.1016/j.ejtl.2020.100020


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only

View Item View Item