Heuristics for a runway-queue management problem

Reducing the delays of the departing aircraft can potentially lead to improving the efficiency of surface operations at airports. This article addresses a runway-queue management problem that aims to assign the departing aircraft to runway-queues and find a departing time for each aircraft at the runway such that the total delays of all the aircraft are minimized subject to the timing, safety, en route and ordering constraints of the aircraft. Novel, local search heuristics that find runway sequences of high solution quality in milliseconds are developed for the runway-queue management problem. A mixed integer linear program that can compute an optimal solution for the runway-queue management is also presented. Computational results show that the developed heuristics run very fast and find sequences whose delays are, on average, at most 2 per cent away from the optimal cost for all the tested instances. Moreover, the heuristics are able to find an optimal sequence in at least 50 per cent of all the tested instances.