Managing severe airspace flow programs: The Airlines’ side of the problem

This paper presents a heuristic-based approach for minimizing airlines’ schedule disruptions and operation costs associated with severe airspace flow programs. It considers primary decisions made by flight dispatchers such as flight slot substitution and rerouting outside the boundaries of the flow-constrained area. A two-stage heuristic is developed. In the first, a linear approximation of the problem is used to screen inefficient routing and slot substitution alternatives. The second stage examines possible solution improvements through trading flight assignments for every pair of conflicting routes. A genetic algorithm is developed and used to benchmark the performance of the two-stage heuristic. In the algorithm, flight route and slot allocation schemes are modeled as chromosomes. The fitness of these chromosomes measures the magnitude of schedule disruption and overall operating cost. A set of experiments that compare the performance of the two heuristics considering airspace flow programs with different levels of severity is presented.