Graph theory is used to investigate three different problems arising in air traffic management. First, using a polynomial reduction from a graph partitioning problem, it is shown that both the airspace sectorization problem and its incremental counterpart, the sector combination problem are NP-hard, in general, under several simple workload models. Second, using a polynomial time reduction from maximum independent set in graphs, it is shown that for any fixed e, the problem of finding a solution to the minimum delay scheduling problem in traffic flow management that is guaranteed to be within n1-e of the optimal, where n is the number of aircraft in the problem instance, is NP-hard. Finally, a problem arising in precision arrival scheduling is formulated and solved using graph reachability. These results demonstrate that graph theory provides a powerful framework for modeling, reasoning about, and devising algorithmic solutions to diverse problems arising in air traffic management.
Applying Graph Theory to Problems in Air Traffic Management
AIAA Aviation and Aeronautics Forum ; 2017 ; Denver, CO, United States
2017-06-05
Miscellaneous
No indication
English
Applying Graph Theory to Problems in Air Traffic Management (AIAA 2017-3775)
British Library Conference Proceedings | 2017
|Traffic management system applying deep neural network to intelligent traffic
European Patent Office | 2021
|Applying availability SLAs to traffic management systems
IEEE | 2011
|4.2 Applying graph theory terms to description of VTS
British Library Conference Proceedings | 2009
|