Polynomial Time Algorithms for Scheduling of Arrival Aircraft

A Mixed Integer Linear Program (MILP) formulation of an arrival traffic scheduling problem is used as the starting point in order to evaluate the respective capabilities of two real-time scheduling algorithms. Three main issues are addressed: computational time, suboptimality and statistical performance. The first algorithm is an approximation algorithm, which is polynomial time and has a guaranteed bound on the suboptimality ratio. The second algorithm is a heuristic algorithm, which is polynomial time. Both algorithms are compared to the exact solution (computed with CPLEX) under realistic air-traffic scenarios generated from American Airlines timetable data for arrival traffic into Saint Louis, Missouri. Results show that the heuristic algorithm has the fastest run-time and is nearly optimal in most scenarios. However, the approximation algorithm generates schedules well within theoretical bounds, providing a guarantee on performance that the heuristic cannot provide. The approximation algorithm is also more robust to adverse weather scenarios than the heuristic algorithm.