Group for Research in Decision Analysis

G-2020-71

An improved integral column generation algorithm using machine learning for aircrew pairing

, , , , and

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^2CG_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^2CG_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, both in term of solution cost and computing times. We highlight the contributions of the neural network to \(I^2CG_p\).

, 23 pages