Ground delay program planning: Delay, equity, and computational complexity

•Introduces several two-phase methods for ground delay program planning.•Finds unsupported Pareto-optimal policies minimizing delay and inequity.•Does not require translating delay and inequity into common units.•Allows the user to bound the computational complexity of ground delay program planning.

The Federal Aviation Administration, in consultation with air carriers, manages Ground Delay Programs, delaying aircraft scheduled to land at capacity constrained airports prior to takeoff to increase the safety and efficiency of air travel. Prior research optimizes Ground Delay Program planning to minimize either delay or a weighted combination of delay and measures of inequity, a key concern in practice. Such approaches have several shortcomings including an inability to find all Pareto-optimal policies and a reliance on (one or many) models relating fundamentally incompatible objectives. This article introduces several two-phase approaches to Ground Delay Program planning that address the problems of weighted sum methods while managing computational burdens, another key concern in practice. A computational study demonstrates the benefits of the new approaches on realistic problem instances.