Solving the European Air Traffic Flow Management Problem with Kernel Search Matheuristics and Machine Learning

The Air Traffic Flow Management (ATFM) problem has the goal of planning flights within a set of constraints representing both capacity limits of the air space and airline company needs, consisting in a delay and a preference assigned to each trajectory; several mathematical linear programming models exist to solve this problem, and the main issue is their size, since they may contain up to millions of variables for real instances. As a consequence, the computational effort required to solve the model to optimality is huge, and not suitable for practical use. This thesis presents a heuristic method based on Kernel Search. The goal of Kernel Search is to solve the model using only an initial subset of variables, called kernel, and dividing the remaining variables into small groups called buckets, ordered by "promising impact on the solution", that is computed from variable information obtained through the resolution of the linear relaxation of the problem. Each iteration of the Kernel Search method consists in solving a small subproblem given by variables from the kernel and from a single bucket, whose size allows to solve it to optimality in a small amount of time; furthermore, in this thesis, Machine Learning techniques have been used in the process of defining the "quality" of each variable, in order to see if such modification in the bucket defining procedure can lead to more efficient or effective methods. The developed algorithms have been implemented and tested on real instances obtained from European data repositories, showing their ability to find optimal or very close to optimal solutions.