A Study of Heuristic Approaches for Runway Scheduling for the Dallas-Fort Worth Airport

摘要

Recent work in air transit efficiency has increased en-route efficiency to a point thatairport efficiency is the bottleneck. With the expected expansion of air transit it willbecome important to get the most out of airport capacity. Departure scheduling isan area where efficiency stands to be improved, but due to the complicated natureof the problem an optimal solution is not always forthcoming. A heuristic approachcan be used to find a sub-optimal take-off order in a significantly faster time than theoptimal solution can be found using known methods.The aim of this research is to explore such heuristics and catalog their solutioncharacteristics. A greedy approach as well as a k-interchange approach were developedto find improved takeoff sequences. When possible, the optimal solution was found tobenchmark the performance of the heuristics, in general the heuristic solutions werewithin 10-15% of the optimal solution. The heuristic solutions showed improvementsof up to 15% over the first-in first-out order with a running time around 4 ms.