Back

# 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

BibTeX reference

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