An Efficient Algorithm for Solving an Air Traffic Management Model of the National Airspace System

Growth in traffic and changes in traffic patterns have caused an increase in the congestion and delay in the National Airspace System. Air traffic delay is very costly to the airlines, and minimizing this delay has been a subject of research for over a decade. A large integer programming model developed at the MITRE Corporation for minimizing air traffic delay is presented. Solving problem instances arising from this model involves the use of preprocessing, constraint strengthening, and a carefully designed computer implementation. Results are presented, demonstrating that the model can be solved to provable optimality in real time for problem instances involving over 1 million binary variables.