Optimal scheduling of arrival flights in terminal airspaces

Abstract

Sequencing and scheduling of arrival flights with safe spacing is studied to help air traffic controllers generate flight commands for each aircraft in a terminal airspace. For the efficient use of a limited airspace, the discrete delay time options corresponding to the predetermined available trajectories or command modes are used as the control variables in sequencing and scheduling of flights. Among various types of algorithms used in scheduling problems, a Genetic Algorithm, a Branch-and-Bound algorithm and a polynomial time algorithm, which is based on a minimum cost perfect matching problem, are developed for wide range of scenarios with various operational constraints, such as Maximum Position Shift or precedence constraints. In addition, for real-time implementations, a new method to improve the computational efficiency of the Branch-and-Bound algorithm is proposed using Lagrangian dual decomposition method, and a new polynomial time algorithm based on minimum cost perfect matching problems is developed. The performances of the proposed Branch-and-Bound algorithm are validated by simulations using real arrival flight data of Gimpo airport, and through the simulations computational efficiency of the proposed algorithms for various scenarios has been analyzed. In order to extend the optimal scheduling problem at a single merging point into the scheduling problem of multiple merging points in an entire terminal airspace, an interaction model of the formulated static optimization problems and the dynamic air traffic estimation model is proposed. Through simulation studies, it is verified that the proposed algorithms are capable of solving the optimal scheduling problem in a reasonably short time to cooperate with the dynamic traffic flow estimation model.