原文传递
Applying Graph Theory to Problems in Air Traffic Management
| 题名： | Applying Graph Theory to Problems in Air Traffic Management |
| 作者： | Farrahi, A. H.; Goldbert, A.; Bagasol, L. N.; Jung, J. |
| 关键词： | Air traffic control##Graph theory##Air transportation##Traffic control##Airspace##Systems integration##Flight paths##Airports##Scheduling##Arrivals##Polynomials##Problem solving## |
| 摘要： | 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. |
| 总页数： | 19 |
| 报告类型： | 科技报告 |
相关文献
- Optimal Control of Fully Routed Air Traffic in the Presence of Uncertainty and Kinodynamic Constraints.
- Cooperative Clustering Techniques For Space Network Scalability.
- Applying Safety-Critical Fault Tolerant Principles to Survivable Transportation Control Networks.
- Wavelet Analysis Approach for Categorizing Air Traffic Behavior.
- Problems of applying regional ETC systems to developing countries.
- Dynamic Flow Management Problems in Air Transportation
检索历史
应用推荐
