Efficient Computation of Separation-Compliant Speed Advisories for Air Traffic Arriving in Terminal Airspace

A class of problems in air trac management asks for a scheduling algorithm that supplies the air trac services authority not only with a schedule of arrivals and departures, but also with speed advisories. Since advisories must be nite, a scheduling algorithm must ultimately produce a nite 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 mixed-integer programs, hindering proofs of correctness and computational cost bounds (crucial for real-time operations). In this paper, a hybrid control system is used to model air trac 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, eectively nite, and has computational cost polynomial in the number of aircraft. This work is a rst step toward optimization and models rened with more realistic detail.