On the airline schedule perturbation problem caused by the ground delay program

The ground delay program is one of several programs that the Federal Aviation Administration is currently administering for efficient and equitable use of scarce airspace and airport capacity. In this paper, we study airline schedule perturbation problem cuased by the ground delay program with the goal of improving airline dependability statistics defined by Department of Transportation as percentage of flights delayed more than 15 minutes. The problem is modeled as an integer program. To solve the model, we have derived valid inequalities for the integer programming formulation for strengthening the LP relaxation bound. The number of integer variables was reduced dramatically based on analysis of the model and its impact on the problem solubility was shown to be of significant importance. A heuristic procedure based on solving a restricted version of the model has been designed for finding good feasible solutions. Computational results indicate the effectiveness of the model reduction and the valid inequalities. Realistic problems have been solved to optimality within seconds on microcomputers. Improvement on airline dependability statistics has been shown to be substantial.