Geometric algorithms for dynamic airspace sectorization

The National Airspace System (NAS) is designed to accommodate a large number of flights over North America. For purposes of workload limitations for air traffic controllers, the airspace is partitioned into approximately 600 sectors each sector is observed by one or more controllers. In order to satisfy workload limitations for controllers, it is important that sectors be designed carefully according to the traffic patterns of flights, so that no sector becomes overloaded.We formulate and study the airspace sectorization problem from an algorithmic point of view, modeling the problem of optimal sectorization as a geometric partition problem with constraints. We evaluate our algorithms experimentally. We conduct experiments using actual historical flight track data for the NAS as the basis of our partitioning. We compare the workload balance of our methods to that of the existing set of sectors for the NAS and find that our resectorization yields competitive and improved workload balancing. In particular, our methods yield an improvement by a factor between 2 and 3 over the current sectorization in terms of the time-average and the worst-case workloads of the maximum workload sector.Further, we investigate the dynamic nature of air traffic and use that to guide sector designs that evolve over time. Depending on the time of day, demand profiles, weather changes, etc. the traffic density of various parts of the NAS changes. In such a scenario, it is more practical to have dynamic sector designs in order to accommodate the changing traffic in fact this is a common practice even today. The goal is to automate the identification and re-configuration of these dense traffic areas. A simple solution would just compute separate sectorizations for different instances of air traffic within a sliding time window. While this method gives excellent workload balance for each time window, it does not guarantee that the change in sector design is minimal and local to dense traffic regions a feature which is very important for dynamic sectorization. Hence, we propose an approach which involves local merging and re-partitioning of neighboring sectors in high traffic density regions.