Existence and Determination of Separation-Compliant Speed Control in Terminal Airspace

Among the premises of the Next Generation Air Transportation System initiative is the necessity for precision procedures in air traffic operations. Conformance with such procedures can help safety and the ability to accommodate higher traffic demand. The contribution of this paper is an algorithm for automating the process of speed control, aimed at separation assurance and conducted in current air traffic operations by human air traffic controllers. If a separation-compliant collective speed profile for the given set of aircraft exists, the algorithm computes this profile. If no such speed profile exists, the computer reports the nonexistence. Uncertainties such as weather are not considered, but the algorithm can be modified to include them. The algorithm proceeds in two stages. First, it finds an arrival sequence for the aircraft. The computational complexity of this stage is factorial in the number of aircraft but allows substantial parallelization. The second stage finds a collective speed profile for a given arrival sequence and has computational complexity that is polynomial in the number of aircraft. The algorithm is proved to find a solution whenever one exists and to ascertain nonexistence correctly.