Alternating Lagrangian decomposition for integrated airline crew scheduling problem

The airline crew scheduling problem is usually solved sequentially in two main steps because of its complexity: the crew pairing followed by the crew assignment. However, finding a globally optimal solution via the sequential approach may be impossible because the decision domain of the crew assignment problem is reduced by decisions made in the pairing problem. This study considers the crew scheduling problem in a personalized context where each pilot and copilot requests a set of preferred flights and vacations each month. We propose a model that completely integrates the crew pairing and personalized assignment problems to generate personalized monthly schedules for a given set of pilots and copilots simultaneously in a single optimization step. The model keeps the pairings in the two problems as similar as possible so that the propagation of perturbations arising during the operation is reduced. We develop an integrated algorithm that combines alternating Lagrangian decomposition, column generation, and dynamic constraint aggregation. We conduct computational experiments on a set of real instances from a major US carrier. Our integrated approach produces significant cost savings and better satisfaction of crew preferences compared with the traditional sequential approach.