.png){kind=icon}
.png){kind=icon}
Return
An Improved Integral Column Generation Algorithm Using Machine Learning for Aircrew Pairing
.png){kind=icon}
PRE
AI
DOI：10.1287/trsc.2021.1084.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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).
Keywords:
crew pairing
machine learning
integral column generation
deep neural network