Sequence Assignment Model for the Flight Conflict Resolution Problem

Each and every day, certain air route traffic control centers receive a large number of requested flight plans, each detailing the level, track, and entry time for the flight to enter the oceanic airspace. Because each airline independently optimizes its own flight plans, it is common that the requested flight plans result in an unbalanced usage of level and track capacities and a conflicting schedule that violates the Federal Aviation Administration (FAA) safety standards. In such a situation, the flight conflict resolution problem is to provide a schedule that minimizes the total penalty cost of delay, level change, and track change while maintaining the FAA separation standards. In this paper, we propose a flight sequence assignment model (FSAM) that selects an optimal set of flight sequences to minimize the total penalty cost. We develop a column generation framework with a bilinear pricing subproblem to solve the linear relaxation of the FSAM, and use a branch-and-price method to find the integer optimal solution. The proposed model is tested on 10 simulated instances randomly constructed based on a real data set. The results show that the FSAM outperforms all other methods in all test instances. We also extend the FSAM to incorporate equity of flight plans among airlines. The computational results show that the equity constraints marginally increase the overall schedule disruption.