Airspace sectorisation based on Voronoi diagrams

• Main Author: Ang, Ding Jie
• Other Authors: Mao Jianfeng
• Format: Final Year Project
• Language: English
• Published: 2016
• Subjects: DRNTU::Engineering
• Online Access: http://hdl.handle.net/10356/68603
• Institution: Nanyang Technological University

The increasing air traffic demand has called for more efficient methods of airspace sectorisation to prevent overloaded sectors. Overloaded sectors lead to congestion which can impose delays and traffic rerouting, resulting in billions of dollars lost every year. Airspace sectorisation partitioned the airspace into sectors such that workloads between sectors are balanced and total system cost is minimised. This work examined the use of Voronoi Diagrams and Genetic Algorithms to sectorise airspace. Two airspace sectorisation models were developed and test using flight data from a small airspace with modest traffic. The first model successfully balanced surveillance workload between sectors. However, multiple optimal solutions were obtained. The second one managed to minimise coordination workload, while balancing surveillance workload between sectors. With the inclusion of minimum distance constraint and minimum sector crossing time constraint, a particular unique solution type was obtained from the model. Through the implementation of these two models, the strength and weakness of using Voronoi Diagrams and Genetic Algorithm became clear. Using Voronoi Diagrams automatically fulfils the convexity and connectivity constrains, but unique solutions are usually not achievable as different site locations can give rise to sector boundaries that are essentially the same. Genetic Algorithm can be implemented with relative ease, but it does not scale well with complexity and the efficiency of the model can be significantly affected by the local optima problem.