Community Detection for Air Traffic Networks and Its Application in Strategic Flight Planning

An environmentally and economically sustainable air traffic management system must rely on fast models to assess and compare various alternatives and decisions at the different flight planning levels. Due to the numerous interactions between flights, mathematical models to manage the traffic can be computationally time-consuming when considering a large number of flights to be optimised at the same time. Focusing on demand–capacity imbalances, this paper proposes an approach that permits to quickly obtain an approximate but acceptable solution of this problem. The approach consists in partitioning flights into subgroups that influence each other only weakly, solving the problem independently in each subgroup, and then aggregating the solutions. The core of the approach is a method to build a network representing the interactions among flights, and several options for the definition of an interaction are tested. The network is then partitioned with existing community detection algorithms. The results show that applying a strategic flight planning optimisation algorithm on each subgroup independently reduces significantly the computational time with respect to its application on the entire European air traffic network, at the cost of few and small violations of sector capacity constraints, much smaller than those actually observed on the day of operations.