Paper Info
Title
An Improved Integral Column Generation Algorithm Using Machine Learning for Aircrew Pairing
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)CG(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)CG(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)CG(p).
Year
DOI
Venue
2021
10.1287/trsc.2021.1084
TRANSPORTATION SCIENCE
Keywords
DocType
Volume
crew pairing, machine learning, integral column generation, deep neural network
Journal
55
Issue
ISSN
Citations 
6
0041-1655
0
PageRank 
References 
Authors
0.34
0
5
Name
Order
Citations
PageRank
Adil Tahir100.34
Frédéric Quesnel200.34
Guy Desaulniers387462.90
Issmail El Hallaoui400.34
Yassine Yaakoubi500.68