Heuristic algorithms for aircraft sequencing problem

Abstract

Delays in flights resulting in multi-billion-dollar losses are declared annually worldwide. Hence, an identification of air traffic policies that can reduce frequent and costly inefficiencies is needed. The problem of scheduling aircraft arrivals and departures on single or multiple runways is analogous to a machine job scheduling problem with sequence-dependent setup times and with tardiness penalties. Each plane has an allowable ready time, target time and target time-to-deadline time window. There are costs associated with landing or departing later than this target time. The objective is to optimally land and depart a set of planes on single or multiple runways in such a way that separation criteria between all pairs of planes are satisfied. As aircraft sequencing and scheduling at airports is an NP-hard problem, heuristic algorithms are used to obtain solutions in a reasonable time.