Efficient Computation of Separation Compliant Speed Advisories for Air Traffic Arriving in Terminal Airspace
View/ Open
Date
2014Author
Sadovsky, Alexander V.
Davis, Damek
Isaacson, Douglas R.
Metadata
Show full item recordAbstract
A class of problems in air traffic management (ATM) asks for a scheduling algorithm that supplies the air traffic services authority not only with a schedule of arrivals and departures but also with speed advisories. Since advisories must be finite, a scheduling algorithm must ultimately produce a finite data set, hence must either start with a purely discrete model or involve a discretization of a continuous one. The former choice, often preferred for intuitive clarity, naturally leads to mixedinteger programs (MIPs), hindering proofs of correctness and computational cost bounds (crucial for realtime operations). In this paper, a hybrid control system is used to model air traffic scheduling, capturing both the discrete and continuous aspects. This framework is applied to a class of problems, called the fully routed nominal problem. We prove a number of geometric results on feasible schedules and use these results to formulate an algorithm that attempts to compute a collective speed advisory, effectively piecewise linear with finitely many vertices, and has computational cost polynomial in the number of aircraft. This work is a first step toward optimization and models refined with more realistic detail.