A quadratic time algorithm for computing the optimal landing times of a fixed sequence of planes

This paper considers the Aircraft Landing Problem. The aim is to schedule arriving aircraft at the airport under the condition of safe landing. Landing times lie within predefined time windows and safety separation constraints between two successive aircraft landing on the same runway, must be satisfied. The objective is to minimize the total cost of landing deviation from predefined target times within the time windows. On each runway, for a fixed landing sequence, the problem can be solved by a linear program. When safety separation times satisfy the Triangle Inequality, we propose an O(n2) algorithm for solving the problem where n is the number of planes of the sequence. We compare the performance of this polynomial time algorithm to the linear programming method. The two methods are embedded in an iterative algorithm, based on simulated annealing, for solving the single runway case. Computational tests, performed on publicly available problems, show that the heuristic based on our algorithm is much faster than the one using linear programming. This gain in CPU time allows to obtain better solutions in a fixed amount of time.