Machine Learning-Enhanced Column Generation for the Crew Pairing Problem: Leveraging Gated Recurrent Units to Generate the Initial Restricted Master Problem
Typ
Examensarbete för masterexamen
Master's Thesis
Master's Thesis
Program
Engineering mathematics and computational science (MPENM), MSc
Publicerad
2024
Författare
Eriksson, Wilmer
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
The crew scheduling problem is a critical challenge for airlines as crew costs represent
the second largest operating cost. It consists of determining the optimal assignment
of crew members to each flight leg in an airline’s schedule. The problem is broken
into two separate problems that are solved sequentially. This research focuses on
the initial problem, referred to as the crew pairing problem, where sequences of
flight legs, known as pairings, are created. Traditionally, the crew pairing problem
is solved by Integer Column Generation frameworks such as the branch-and-price
algorithm.
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 potential
partial solution using supervised learning before starting the traditional column
generation process. For large-scale optimization problems, a fundamental trade-off
between optimality and computational time exists. Sometimes, problems are not
solved to complete optimality; instead, satisfactory or near-optimal solutions are
found. Therefore, by improving the starting point of the algorithm, it should be
possible to find better solutions.
The results shows that GEPI can generate high-quality pairings that are used in the
final solution for 59 out of the 192 test cases. These GEPI-generated pairings reduced
the flight schedule cost in 34 test cases, while two cases saw a cost increase. The
introduction of GEPI in the optimization process led to an increase of execution time
for 37 test cases. These outcomes suggest that there is some potential of improving
the 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.
Beskrivning
Ämne/nyckelord
Column Generation, Crew Pairing Problem, Gated Recurrent Units, Machine Learning