Using machine learning to improve a column generation framework for a tail assignment optimizer
Publicerad
Författare
Typ
Examensarbete för masterexamen
Program
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
While the research effort spent on algorithms for solving optimization problems
appearing in an airline industry is vast, the use of machine learning for improving
these algorithms is a new and under-explored topic. A popular and widely
researched problem in the airline industry is the tail assignment problem. This
problem aims to assign a set of aircrafts to a set of flights such that constraints
like pre-planned maintenance activities, destination restrictions, curfews and turn
time rules are respected and some objective function like fuel costs or robustness is
optimized to get a schedule for an airline. At Jeppesen Systems, the tail assignment
problem is solved using a column generation framework which uses a subgradient
optimizer to solve the Lagrangean dual problem. In this thesis, machine learning is
being used to determine whether to start each iteration of the column generation
framework from the previous iteration solution (warm start) or from scratch/origin
(cold start). The choice of starting procedure has a significant effect on the solution
time and overall quality of the solution. The problem is investigated by proposing
predefined strategies with different types of starts which can be used to solve a tail
assignment problem. After studying the performance of the strategies, it turned out
that some of them perform better than the current heuristic employed at Jeppesen
Systems for certain problem instances, implying that the machine learning model
could improve the column generation framework. Five supervised learning models
were then implemented to learn the patterns for selecting the right strategy for a
given tail assignment problem instance. The implemented models were then evaluated
against a baseline model using accuracy and F1-score as evaluation metrics.
The results from the analysis of the models suggest that all the selected features of a
problem instance allow four of the five models to perform better than just randomly
guessing the strategy. In the future, the models can be improved by developing
models on a larger data set with more problem instances, having more diverse, dynamic
strategies and by analyzing the effect of the choice of input features for each
tail assignment problem.
Beskrivning
Ämne/nyckelord
tail assignment, column generation, subgradient optimization, airline optimization, aircraft routing, shortest path problem, machine learning, supervised learning, classification.