The airline crew scheduling problem involves assigning a group of crew members to scheduled flights over a planning horizon (usually a month) while respecting safety rules and regulations. Because of its size and complexity, this problem is frequently solved in two steps, first crew pairing and then crew assignment. Therefore, the global optimization of the crew scheduling is not guaranteed, because the crew pairing problem does not take into account the scheduling constraints. The problem of integrated bidline scheduling (anonymous schedules) for pilots has been investigated by Saddoune et al. In this paper, we deal with the integrated personalized crew scheduling problem. In this case, personal preferences and constraints result in different monthly schedules for the pilots and copilots. However, to maintain the robustness of the crew schedules under perturbation at the operational level, the pilots and copilots must have similar pairings when possible. This paper presents a heuristic algorithm that alternates between the pilot and copilot scheduling problems to obtain similar pairings even when the monthly schedules are different. Each problem is formulated as a set partitioning problem, and the solution approach is based on column generation and constraint aggregation. We conduct computational experiments on a set of real instances from a major US carrier.
Published December 2014 , 18 pages