Hybrid Metaheuristics to Aid Runway Scheduling at London Heathrow Airport

Although London Heathrow is one of the busiest airports in the world, it has only one runway for use by departing aircraft at any time. Separations are required between each pair of aircraft at take-off---depending on their routes, weights, and speeds---to ensure safety. Efficient scheduling of the aircraft for take-off can reduce the total separations and increase throughput. A runway controller is responsible for take-off scheduling. This is a very intensive job with responsibility for all communication with aircraft and continuous monitoring to assure safety. The high workload limits the number of aircraft that the controller can take account of when scheduling. The geometry of the runway holding points adds physical constraints to the reordering of aircraft that are usually ignored in the academic literature. We present models for evaluating a schedule and determining the effects of the physical constraints. We propose a hybrid metaheuristic system that takes account of more aircraft than a human controller can handle, and so can aid the runway controller by recommending schedules that anticipate some future problems. We present results to show the effectiveness of this system, and we evaluate those results against real-world schedules.