Design and implementation of a graph-coloring algorithm for optimizing flight-level allocation in air traffic management in Iran

The rapid growth of air traffic demand highlights the necessity of efficient and reliable methods for air traffic flow management (ATFM). In Iran, the current flight level allocation is predominantly performed manually by human operators, which is prone to errors, lacks scalability, and does not guarantee optimal use of available airspace resources. To address this limitation, this study proposes a novel optimization framework based on graph coloring techniques for the allocation of flight levels.The airspace is modeled as a graph, where each flow corresponds to a node and potential conflicts are represented as edges. The problem is then formulated as an optimization model with the goal of minimizing the number of distinct flight levels while ensuring safety constraints. A hybrid algorithm is developed that combines the DSatur heuristic for generating an initial solution with a constraint programming (CP) model enhanced by maximal clique detection for refinement and optimization.The approach is applied to real operational data from Tehran’s Mehrabad and Mashhad Hasheminejhad Airports during peak hours. In a benchmark example, the proposed method reduces the number of required flight levels compared to DSatur from four to three, corresponding to a ۲۵% improvement. In addition, experimental results based on real operational data from Tehran Mehrabad and Mashhad Hasheminejhad Airports during peak hours demonstrate the practicality of the proposed approach for determining conflict-free flight-level allocations under realistic operational conditions.

کلیدواژه ها:

Air Traffic Flow Management (ATFM) ، Graph coloring techniques ، DSatur heuristic ، Constraint Programming (CP)