Machine Learning-Enhanced Column Generation for the Crew Pairing Problem: Leveraging Gated Recurrent Units to Generate the Initial Restricted Master Problem

Sammanfattning

The crew scheduling problem is a critical challenge for airlines as crew costs representthe second largest operating cost. It consists of determining the optimal assignmentof crew members to each flight leg in an airline’s schedule. The problem is brokeninto two separate problems that are solved sequentially. This research focuses onthe initial problem, referred to as the crew pairing problem, where sequences offlight legs, known as pairings, are created. Traditionally, the crew pairing problemis solved by Integer Column Generation frameworks such as the branch-and-pricealgorithm.This work proposes the integration of Gated Recurrent Units (GRU) into the stateof-the-art industry algorithms used to solve the crew pairing problem. This method,named the GRU-Enhanced Pairing Initializer (GEPI), generates an initial potentialpartial solution using supervised learning before starting the traditional columngeneration process. For large-scale optimization problems, a fundamental trade-offbetween optimality and computational time exists. Sometimes, problems are notsolved to complete optimality; instead, satisfactory or near-optimal solutions arefound. Therefore, by improving the starting point of the algorithm, it should bepossible to find better solutions.The results shows that GEPI can generate high-quality pairings that are used in thefinal solution for 59 out of the 192 test cases. These GEPI-generated pairings reducedthe flight schedule cost in 34 test cases, while two cases saw a cost increase. Theintroduction of GEPI in the optimization process led to an increase of execution timefor 37 test cases. These outcomes suggest that there is some potential of improvingthe starting point of the column generation process using a neural network. However,the decrease in scheduling cost appears to be associated with longer execution times.To gain a more comprehensive understanding of GEPI’s potential and limitations,further tests and analysis are needed.