Multi-Objective 3D Airspace Sectorization Problem Using NSGA-II with Prior Knowledge and External Archive

Abstract

Airspace sectorization is a powerful means to balance the increasing air traffic flow and limited airspace resources, which is related to the efficiency and safety of operations. In order to divide sectors reasonably, a multi-objective optimization framework for 3D airspace sectorization is proposed in this paper, including four core modules: Flight clustering, sector generation, workload evaluation, and sector optimization. Specifically, it clusters flights and generates initial sectors using a Voronoi diagram. To further optimize sector shape, the concept of dynamic density is introduced to evaluate the controller workload, based on which a sector optimization model is constructed. The model not only considers intra-sector and inter-sector workloads as objective functions but also sets hard constraints to meet operation and safety requirements. To solve it, a Non-dominated Sorting Genetic Algorithm II (NSGA-II) with prior knowledge and an external archive is designed. By analyzing the optimization results of actual operational data in the Singapore regional airspace, our approach obtains diverse optimal sectorization schemes for decision makers to choose from. Qualitative and quantitative experimental results confirm that the initial population strategy with prior knowledge significantly accelerates the convergence process. At the same time, the mechanism of the external archive effectively enriches the diversity of solutions.

Keywords

• 3D airspace sectorization
• multi-objective optimization
• genetic algorithm
• prior knowledge
• external archive