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

Published Version
Terms of Use: Creative Commons Attribution Non-commercial No Derivatives .
Download (1MB)
Cite this document: 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). doi:10.1016/j.ejtl.2020.100020
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

Open Access document in PolyPublie
Subjects: 1600 Génie industriel > 1600 Génie industriel
1600 Génie industriel > 1605 Génie des facteurs humains
Department: Département de mathématiques et de génie industriel
Research Center: GERAD - Groupe d'études et de recherche en analyse des décisions
Funders: CRSNG/NSERC - Collaborative Research and Development Grant, IVADO, IBS Software - AD OPT
Date Deposited: 05 Apr 2022 11:35
Last Modified: 06 Apr 2022 01:20
PolyPublie URL: https://publications.polymtl.ca/9271/
Document issued by the official publisher
Journal Title: EURO Journal on Transportation and Logistics (vol. 9, no. 4)
Publisher: Elsevier
Official URL: https://doi.org/10.1016/j.ejtl.2020.100020


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only