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

Document Type : Research Article

Authors

Seyed Ali Asghar Mosavi ¹

Ahmad Erfanian ¹

Narjes Sabeghi ²

¹ Department of Pure Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, Mashhad, Iran.

² Departments of Mathematics, Faculty of Basic sciences, Velayat University, Iranshahr, Iran

10.22067/ijnao.2026.95911.1749

Abstract

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 25% 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.

Keywords

Air Traffic Flow Management (ATFM)

Graph coloring techniques

DSatur heuristic

Constraint Programming (CP)

Subjects

• Computational Mathematics

---

References

[1] Barnier, N., and Brisset, P. Graph coloring for air traffic flow management, Ann. Oper.
Res., 130(1) (2004), 163–178.
[2] Bomze, I.M., Budinich, M., Pardalos, P.M., and Pelillo, M. The maximum clique problem,
In Handbook of Combinatorial Optimization: Supplement Volume A (pp. 1–74). Boston,
MA: Springer US, 1999.
[3] Brélaz, D. New methods to color the vertices of a graph, Commun. ACM., 22(4) (1979),
251–256.
[4] Gimenez-Guzman, J.M., Martínez-Moraian, A., Reyes-Bardales, R.D., Orden, D., and
Marsa-Maestre, I. Flight level assignment using graph coloring, Appl. Sci. 10(18) (2020),
6157.
[5] Yekezare, N., Zohrehbandian, M., Maghasedi, M., and Bonomo-Braberman, F. Optimality
of DSatur algorithm on chordal graphs, Oper. Res. Lett., 57 (2024), 107185