Machine Learning-Enhanced Column Generation for the Crew Pairing Problem: Leveraging Gated Recurrent Units to Generate the Initial Restricted Master Problem
| dc.contributor.author | Eriksson, Wilmer | |
| dc.contributor.department | Chalmers tekniska högskola / Institutionen för matematiska vetenskaper | sv |
| dc.contributor.examiner | Jonasson, Johan | |
| dc.contributor.supervisor | Grover, Divya | |
| dc.contributor.supervisor | Jonasson, Johan | |
| dc.date.accessioned | 2025-01-14T08:48:34Z | |
| dc.date.available | 2025-01-14T08:48:34Z | |
| dc.date.issued | 2024 | |
| dc.date.submitted | ||
| dc.description.abstract | 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. | |
| dc.identifier.coursecode | MVEX03 | |
| dc.identifier.uri | http://hdl.handle.net/20.500.12380/309081 | |
| dc.language.iso | eng | |
| dc.setspec.uppsok | PhysicsChemistryMaths | |
| dc.subject | Column Generation, Crew Pairing Problem, Gated Recurrent Units, Machine Learning | |
| dc.title | Machine Learning-Enhanced Column Generation for the Crew Pairing Problem: Leveraging Gated Recurrent Units to Generate the Initial Restricted Master Problem | |
| dc.type.degree | Examensarbete för masterexamen | sv |
| dc.type.degree | Master's Thesis | en |
| dc.type.uppsok | H | |
| local.programme | Engineering mathematics and computational science (MPENM), MSc |