Scheduling Aircraft Departures to Avoid Enroute Congestion

When scheduled flights are forecast to overcrowd sections of enroute airspace, an air traffic control authority may need to delay departures. Mixed integer linear programming can be used to compute a schedule that resolves the congestion while bringing the sum of all delays to a minimum. Standard linear programming constraint formulations for such scheduling problems, however, have poor run times for instances of realistic size. A new constraint formulation based on cycles and paths through a route graph reduces run times in computational experiments. It shows particularly strong performance for schedules that approach the worst-case solution times in standard formulations