Sequence assignment model for the flight conflict resolution problem

Zhe Liang, Wanpracha Art Chaovalitwongse, Elsayed A. Elsayed

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)334-350
Number of pages17
JournalTransportation Science
Issue number3
StatePublished - Aug 1 2014

All Science Journal Classification (ASJC) codes

  • Civil and Structural Engineering
  • Transportation


  • Air traffic management
  • Branch-and-price method
  • Column generation
  • Equity
  • Flight conflict resolution
  • Flight scheduling
  • Integer programming


Dive into the research topics of 'Sequence assignment model for the flight conflict resolution problem'. Together they form a unique fingerprint.

Cite this