Machine Learning in Airline Crew Pairing to Construct Initial Clusters for Dynamic Constraint Aggregation

By François Soumis, Simon Lacoste-Julien. 2020

26 citations recorded by the source corpus.

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

Subfields: Automotive Engineering, Economics and Econometrics, Industrial and Manufacturing Engineering, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Automotive Engineering

1. Simon Lacoste-Julien
2. François Soumis
3. Yassine Yaakoubi

In Economics and Econometrics

1. Simon Lacoste-Julien
2. François Soumis
3. Yassine Yaakoubi

In Industrial and Manufacturing Engineering

1. Simon Lacoste-Julien
2. Yassine Yaakoubi
3. François Soumis

In Mathematical Optimization

1. Simon Lacoste-Julien
2. Yassine Yaakoubi
3. François Soumis

Citations in the corpus

• Structured Convolutional Kernel Networks for Airline Crew Scheduling (2021, methodology): “Then, using the same heuristics as in Yaakoubi et al. (2020) (see Appendix D.3), we build a monthly crew pairing called “CNN - initial” .”
• Flight-connection Prediction for Airline Crew Scheduling to Construct Initial Clusters for OR Optimizer (2019, methodology): “Note that the importance of the methodology in this paper is illustrated in a follow-up paper of ours where we propose contributions to the OR solver, in order to use the proposed ML approach on a monthly CPP [46].”