Scheduling aircraft landings

Abstract:

In this talk we consider the problem of scheduling aircraft (plane) landings at an airport. This problem is one of deciding a landing time for each plane such that each plane lands at some time within a predetermined time window and separation criteria between the landing of a plane, and the landing of all successive planes, are respected. The objective is to minimise the total (weighted) deviation from a desired target landing time for each plane. We present a mixed-integer zero-one formulation of the problem for the single runway situation and extend it to the multiple runway situation. We strengthen this formulation by introducing additional constraints.

We distinguish two cases:

(a) the static, or off-line, case, where we have complete knowledge of the set of planes that are going to land

(b) the dynamic, or on-line, case, where decisions about the landing times for planes must be made as time passes and the situation changes (planes land, new planes appear, etc).

The dynamic problem is viewed as a particular case of a important generic decision problem, the displacement problem. The displacement problem arises where we have to make a sequence of decisions and each new decision that must be made has an explicit link to the previous decision that was made. This link is quantified by means of the displacement function. We provide a systematic description of the displacement problem and discuss a number of issues related to the problem. Computational results are presented, for both heuristic and optimal algorithms, for the solution of problems (both static and dynamic problems) involving up to 50 planes and four runways.