An Exact Dynamic Programming Algorithm for the Aircraft Sequencing Problem

We consider the static case of the aircraft sequencing problem on a single runway with constraints on the deviation from the first-come-first-serve order. An exact dynamic programming algorithm is proposed, and the effects of limiting the states in the state space graph are investigated. Completion bounds are computed and are used together with heuristic upper bounds to further limit the number of states. For real world air traffic instances from Milan Linate Airport it is shown that the algorithm is able to outperform the previously best exact algorithm from the literature.

• This seminar is organised by the Erasmus Centre for Optimalization in Public Transport