Optimal construction of airline individual crew pairings

In this paper we develop eight scheduling models to minimize crew costs and to plan the proper individual pairings using real constraints for a Taiwan airline. These models are formulated as integer linear programs, where column-generation-based algorithms are developed to solve them. A case study regarding the operation of a major Taiwan Airline is presented. The construction of airline cabin crew schedules is generally separated into two problems, crew scheduling and crew rostering. Traditionally, the planned pairings from crew scheduling are not allocated to individual crew members. In reality, crew members from different home basis are considered for service on the same flight. Crew members with higher ranks may be assigned to serve lower classes of cabin seats. As well, flights having different aircraft types are sometimes combined to form a pairing. When these factors are handled in downstream crew rostering, it increase not only the complexity of the crew rostering problem but also the crew cost. The purpose of this paper is to incorporate such factors as multiple home basis, mixed aircraft types and multiple cabin classes into the crew scheduling problems, to improve the construction of cabin crew schedules, and to better link crew scheduling and crew rostering.