Group for Research in Decision Analysis

G-2018-37

Combining alternating Lagrangian decomposition, column generation, and dynamic constraint aggregation for integrated crew pairing and personalized assignment problems simultaneous for pilots and copilots

and

The airline crew scheduling problem consists of determining crew schedules for airline crew members such that all the scheduled flights over a planning horizon (usually a month) are covered and the constraints are satisfied. Because of its size and complexity, this problem is usually solved sequentially in two main steps: the crew pairing followed by the crew assignment. However, finding a global optimal solution via sequential approach may become impossible because the decision domain of the crew assignment problem is reduced by previously made decisions in the crew pairing problem. In this paper, we consider the pilot and copilot crew scheduling problems in a personalized context where each pilot and copilot requests a set of preferences flights and vacations per 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 where we keep the pairings in the two problems as similar as possible so the propagation of the perturbations during the operation is reduced. To solve this model, we develop an integrated approach based on combining alternating Lagrangian decomposition, column generation, and dynamic constraint aggregation. We conduct computational experiments on a set of real instances from a major US carrier. The integrated approach produced significant cost savings and satisfaction of crew preferences in comparison with the traditional sequential approach commonly used in~practice.

, 18 pages