An Improved Integral Column Generation Algorithm Using Machine Learning for Aircrew Pairing

Adil Tahir (), Frédéric Quesnel (), Guy Desaulniers (), Issmail El Hallaoui () and Yassine Yaakoubi ()
Additional contact information
Adil Tahir: Department of Mathematics and Industrial Engineering and Groupe d'études et de recherche en analyse des décisions (GERAD), Ecole Polytechnique de Montréal, Montréal, Quebec H3T 1J4, Canada
Frédéric Quesnel: Department of Mathematics and Industrial Engineering and Groupe d'études et de recherche en analyse des décisions (GERAD), Ecole Polytechnique de Montréal, Montréal, Quebec H3T 1J4, Canada
Guy Desaulniers: Department of Mathematics and Industrial Engineering and Groupe d'études et de recherche en analyse des décisions (GERAD), Ecole Polytechnique de Montréal, Montréal, Quebec H3T 1J4, Canada
Issmail El Hallaoui: Department of Mathematics and Industrial Engineering and Groupe d'études et de recherche en analyse des décisions (GERAD), Ecole Polytechnique de Montréal, Montréal, Quebec H3T 1J4, Canada
Yassine Yaakoubi: Department of Mathematics and Industrial Engineering and Groupe d'études et de recherche en analyse des décisions (GERAD), Ecole Polytechnique de Montréal, Montréal, Quebec H3T 1J4, Canada

Transportation Science, 2021, vol. 55, issue 6, 1411-1429

Abstract: The crew-pairing problem (CPP) is solved in the first step of the crew-scheduling process. It consists of creating a set of pairings (sequence of flights, connections, and rests forming one or multiple days of work for an anonymous crew member) that covers a given set of flights at minimum cost. Those pairings are assigned to crew members in a subsequent crew-rostering step. In this paper, we propose a new integral column-generation algorithm for the CPP, called improved integral column generation with prediction ( I 2 C G p ), which leaps from one integer solution to another until a near-optimal solution is found. Our algorithm improves on previous integral column-generation algorithms by introducing a set of reduced subproblems. Those subproblems only contain flight connections that have a high probability of being selected in a near-optimal solution and are, therefore, solved faster. We predict flight-connection probabilities using a deep neural network trained in a supervised framework. We test I 2 C G p on several real-life instances and show that it outperforms a state-of-the-art integral column-generation algorithm as well as a branch-and-price heuristic commonly used in commercial airline planning software, in terms of both solution costs and computing times. We highlight the contributions of the neural network to I 2 C G p .

Keywords: crew pairing; machine learning; integral column generation; deep neural network (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2021.1084 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:55:y:2021:i:6:p:1411-1429

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().