Greedy algorithms and metaheuristics for a multiple runway combined arrival-departure aircraft sequencing problem

Abstract

This paper examines the Aircraft Sequencing Problem (ASP) over multiple runways, under mixed mode operations with the objective of minimizing the total weighted tardiness of aircraft landings and departures simultaneously. The ASP can be modeled as a parallel machine scheduling problem with unequal ready-times, target times and deadlines. Furthermore, sequence-dependent separation times on each runway are considered to prevent the dangers associated with wake-vortex effects. Due to the problem being NP-hard, greedy heuristics and metaheuristics are applied in this paper to obtain solutions in reasonable computation times. The algorithms' solutions are compared to optimal solutions and their performances are evaluated in terms of solution quality and CPU time.