|
 
|
[Fay18] A quadratic time algorithm for computing the optimal landing times of a ï¬xed sequence of planes
Revue Internationale avec comité de lecture : Journal European Journal of Operational Research, vol. 270, pp. 1148-1157, 2018, (doi:https://doi.org/10.1016/j.ejor.2018.04.021)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 predeï¬ned time windows and safety sep-
aration constraints between two successive aircraft landing on the same runway, must be satisï¬ed. The
objective is to minimize the total cost of landing deviation from predeï¬ned target times within the time
windows. On each runway, for a ï¬xed 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 ï¬xed
amount of time.
BibTeX
| @article { | |||
| Fay18, | |||
| title | = | "{A quadratic time algorithm for computing the optimal landing times of a ï¬xed sequence of planes}", | |
| author | = | "A. Faye", | |
| journal | = | "European Journal of Operational Research", | |
| year | = | 2018, | |
| volume | = | 270, | |
| pages | = | "1148-1157", | |
| doi | = | "https://doi.org/10.1016/j.ejor.2018.04.021", | |
| } | |||
