A Dynamic Programming approach to the Aircraft Sequencing problem

Abstract

In this report, a number of Dynamic Programming algorithms for three versions of the Aircraft Sequencing problem are developed. In these, two alternative objectives are considered: How to land all of a prescribed set of airplanes as soon as possible, or alternatively, how to minimize the total passenger waiting time. All these three versions are "static", namely, no intermediate aircraft arrivals are accepted until our initial set of airplanes land. The versions examined are (a) The single runway-unconstrained case, (b) The single runway-Constrained Position Shifting (CPS) case and (c) The two-runway-unconstrained case. In the unconstrained case, no priority considerations exist for the airplanes of our system. By contrast, CPS prohibits the shifting of any particular airplane by more than a prespecified number of positions (MPS) from its initial position in the queue. All three algorithms exploit the fact that the airplanes in our system can be classified into a relatively small number of distinct categories and thus, realize drastic savings in computational effort, which is shown to be a polynomially bounded function of the number of airplanes per category. The CPS problem is formulated in (b) in a recursive way, so that for any value of MPS, the computational effort remains polynomially bounded as described above. All algorithms of this work are tested by various examples and the results are discussed. Implementation issues are considered and suggestions on how this work can be extended are made.