# Flight Level Assignment Using Graph Coloring
## 1 Introduction  
The increasing congestion of the airspace is widely accepted to be one of the outstanding problems in today's society. Researchers agree in considering the state-of-the-art methods for air traffic management (ATM) to be insufficient to handle the expected growth, see the survey by [PERSON] et al. [1]. [PERSON] and [PERSON] [2] describe how the airspace is divided into smaller regions, each one handled by air traffic control (ATC). Therefore, the assignment of flight levels (FLs) is carried out locally within each region, resulting in a suboptimal solution both for individual routes and for the overall network. This is mainly due to the fact that ATM often requires level changes, which are costly in terms of fuel and emissions, as well as deviations from the optimal path from origin to destination, which are also costly in terms of time and fuel. This is why allocation of flight levels is the goal in [2], where a graph coloring problem is solved by a combination of a greedy algorithm and constraint programming. Being a well-established tool coming from discrete mathematics, graph coloring has proved to be useful in many different applications. There are a number of different types of graph coloring problems. For an exhaustive description of most of them, the reader is kindly redirected to the surveys in [3, 4]. For the purposes of this paper, we will discuss the classic graph coloring problem, which is the one used by [PERSON] and [PERSON] in [2], and the spectrum coloring problem, which we proposed in [5]. The classic graph coloring problem assigns to each vertex in the graph a label or color, with the constraint that two vertices of the graph cannot have the same color if there is an edge connecting them--these kinds of edges are called monochromatic edges, and the colorings which avoid them, proper colorings. If we envision a graph where aircraft routes are vertices, edges connect intersecting routes, and colors represent FLs, this problem can be used to ensure that no two crossing routes are assigned the same FL [2]. A limitation of this approach is that routes may cross at adjacent FLs. Safety considerations, however, should favor those colorings where crossing routes use further separated FLs, so that height changes due to flight conditions are less likely to result in accidents. Taking this into account, we consider here the general spectrum graph coloring problem [5], where there is aset of available colors and a matrix of interferences between colors, and the goal is to minimize the total interference. We have achieved significantly good solutions using this technique in domains as diverse as Wi-Fi channel assignment [5] and reactive network resiliency [6]. In this paper we evaluate its applicability to traffic management, by mapping interference to closeness between flight levels, i.e., the closer the FLs, the higher the interference. There are a number of papers on flight level assignment in the literature. [PERSON] et al. [7] propose simulated annealing to optimize air traffic through small reroutes and en-route level changes, as well as flight delays to handle intersecting routes. Flying at an optimal altitude can help to save a significant amount of fuel during the cruise phase of a trip, but there is a fuel cost in reaching that altitude. This yields a trade-off between optimizing fuel expenditure by flying at an optimum altitude and the extra fuel spent to reach that altitude. The length of the air route arises as a significant variable since, the longer the flight, the smaller percentage of total fuel spent is due to reaching optimum flight level [8]. Both fuel consumption (e.g., [9; 10; 11]) and flight level assignment (e.g., [2; 7; 12]) have been addressed in the literature but, to the best of our knowledge, this is the first work considering both of them simultaneously for sets of routes.