Robust 3D dynamic airspace sectorization: A multilayer graph-based approach

This paper presents a robust algorithm for three-dimensional dynamic airspace sectorization, introducing for the first time multilayer traffic networks in the study field. Distinct from widely used meta-heuristic algorithms, this approach delivers consistent results for the same traffic scenario, avoiding the instability of stochastic search techniques. This approach uses a graph-based model, taking the air traffic network as input, based on which we calculate traffic complexity. To quantify the complexity assigned to the network, we employ two parameters: one derives from the traffic scenarios based on flight vectors, and the other from the network topology. Using this complexity-weighted network as input, a multi-layer spectral clustering algorithm is applied to generate the desired number of communities. To achieve an ideal sector structure, we introduce a boundary refinement framework to produce smooth and tightly connected three-dimensional sectors. The performance of the proposed algorithm is validated using three Key Performance Indicators (KPIs): workload, sector flight time, and dynamic density, demonstrating its capability to generate more load-balanced sector configurations compared to both the current UK operational sectors and the widely used Voronoi diagram-based methods. The performance of the algorithm is evaluated through eight experiments under both peak and off-peak traffic conditions, including four-hour short-term and four six-hour long-term scenarios, with the number of target sectors kept consistent with the operational configuration. The reduced standard deviations and coefficients of variation of the KPIs indicate that the proposed sectorization achieves a more balanced distribution of traffic loads across sectors. This research provides Air Navigation Service Providers (ANSPs) with an automatic tool for three-dimensional airspace sectorization, enabling more balanced workload distribution while adapting to evolving air traffic flow patterns.