Airspace Sector Redesign Based on Voronoi Diagrams

Dynamic resectorization is a promising concept to accommodate the increasing and fluctuating demands of flight operations in the National Airspace System. At the core of dynamic resectorization is finding an op-timal sectorization. Finding such an optimal sectorization is challenging because it mixes the graph partition problem and NP-hard optimization problem. This paper revisits Voronoi diagrams and Genetic Algorithms, and proposes a strategy that combines these algorithms with the iterative deepening algorithm. Voronoi diagrams accomplish the graph partition, which then needs to be optimized. By defining a multi-objective cost, the combination of the Genetic Algorithm and iterative deepening algo-rithm solves the optimization problem. Experimental results show that this method can accomplish sector design by setting an appropriate cost. Without a need of clustering, this method can capture the dominant flow, which is one of the major concerns in sector design. The design can have balanced aircraft count and low coordination. If the capacity is defined and incorporated into the cost, the sectorization will lead to a design with in-creased capacity. The whole process can be finished within a feasible time period without the need for parallel schemes. I.