A pairing algorithm for landing aircraft to closely spaced parallel runways

Abstract

To facilitate pairing of aircraft while meeting a schedule, the pair-scheduling problem for landing aircraft in Very Closely Spaced Parallel Approaches was studied. An earlier prototype was adopted and the scheduling algorithm was extended in several ways to improve the solution quality and expand the range of constraints it could handle. This paper presents the scheduling problem formulation, as well as enhancements made to an earlier prototype that made it suitable for application in a human-in-the-loop simulation carried out recently at NASA Ames Research Center. Experimental data from the simulations as well as an extensive set of stress tests are analyzed and discussed. Results suggest the algorithm succeeded in suggesting aircraft pairs acceptable to the air traffic controllers in over 97% of the cases. Evaluating the performance and scalability characteristics of the algorithm demonstrates its effectiveness in discovering feasible aircraft pairs that meet all the sequencing, separation, pair-group, and runway assignment constraints. Overall, the high solution quality and short runtime makes the proposed algorithm a suitable and attractive candidate for use in a real-time aircraft-pairing application.