Using machine learning to improve a column generation framework for a tail assignment optimizer

Abstract

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.