Mining optimal trajectories for the Air Traffic Flow Management Problem

The objective of the Air Tra c Flow Management Problem (ATFM) is to assign 4D trajectories to flights to guarantee both safe operations and efficient use of airspace. Several methodologies have been proposed to manage ATFM operations, and Integer Linear Programming (ILP) proved to be one of the most common. In this talk, we present an ILP model that assigns a trajectory with a possible ground delay to each flight. For each flight, the set of relevant trajectories is extracted from air traffic data repositories using data analytics tools. Because the number of possible trajectories can be extremely large, we propose a heuristic that combines simulated annealing with machine learning. The heuristic iteratively solves the ILP model restricted to subsets of variables (representing trajectory-ground delay pairs) that change at each iteration. At each step, a tree classifier guides a random selection of relevant variables that are likely to improve the current solution. The tree classifier considers features related to both variables and the current solution, according to a preliminary training on reduced size instances. Results are compared to a heuristic based on column generation and show the ability of the proposed method to e ectively solve realistic instances by sensibly reducing running times while preserving the quality of the solutions.