Solving the Large-Scale Crew Pairing Problem in the Airline Industry Using the Column Generation Method - MOL, GÖKÇE; ERMİŞ, MURAT (Springer Science and Business Media Deutschland GmbH, 2025)
The commercial airline industry is highly competitive, and resources must be carefully managed to be sustainable. Of the many factors that affect operating costs, the two most important are fuel costs and crew pairing. Crew pairing is the strategic assignment of flight crews, including pilots, co-pilots, and flight attendants, to designated sequences of connected flights. This pairing should be done carefully to ensure a balance between cost-effectiveness and operational efficiency. This study focuses on developing an efficient model and solution approach for large-scale real-world problems by addressing the airline crew pairing problem. The primary goal of crew pairing is to minimize the total number of crews required to cover all scheduled flights achieved by grouping flights into pairings that maximize overall crew utilization. Crew pairing also aims to minimize unproductive crew time. In other words, efforts are made to reduce waiting times and deadheads, which is the time spent at the destination to rest between flights. Since flight safety is crucial in air transportation, all pairings must comply with regulations set by national/international civil aviation authorities and international agreements. These regulations set restrictions for pilots and flight attendants, such as duty hours, rest periods, and flight duration. Several approaches have been proposed in the literature to find an exact solution to the crew pairing problem. These approaches are generally suitable for smaller datasets where the number of aircraft and destinations is limited due to issues such as scalability and impracticality. This paper addresses this challenge using the column generation method, an effective technique for solving problems characterized by a large number of variables. In our study, real flight data from the narrow-body fleet of a large global airline is used. The proposed method outperformed in terms of computational efficiency and feasibility for larger datasets.
International Symposium for Production Research, ISPR 2024
Keywords: Airline Crew Pairing; Column Generation; Integer Programming; Set Covering