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

Revue Internationale avec comité de lecture : Journal European Journal of Operational Research, vol. 270, pp. 1148-1157, 2018, (doi:

Auteurs: A. Faye

Mots clés: OR in airlines Aircraft Landing Problem Landing times Dynamic programming Polynomial-time algorithm

Résumé: 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 sep- aration 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(n^2) algorithm for solv- ing 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 it- erative 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.


@article {
title="{A quadratic time algorithm for computing the optimal landing times of a fixed sequence of planes}",
author="A. Faye",
journal="European Journal of Operational Research",