# Flight Level Assignment Using Graph Coloring
## 1 Introduction
In doing so, we provide a real-world example of an instance of behavior optimization in a complex self-interested network, in the sense that there are interdependent decision makers (the flight pilots or the airlines governing these flights), whose individual interests (minimizing fuel consumption for their own flights) are different from the social goal (ensuring safety distances between FLs for all the flights). There is, of course, an individual incentive to position a flight in its optimal fuel consumption level, but not all flights can fly at their optimum without this being a great risk in terms of safety. The coexistence of different interests between individual goals which solely depend on individual actions (i.e., how far an aircraft is from its optimal FL), and social goals which depend on the interaction between actions (i.e., at which FLs are conflicting aircrafts flying), suggests to model the problem as a factorized optimization, and to evaluate techniques similar to the ones we have used successfully in other complex network domains [13]. To optimize fuel consumption together with flight level assignment, we can resort to a number of optimization techniques that can be used for graph coloring. Examples of such optimization techniques that we have already successfully used to color graphs are briefly described next. Harmony Search [14] is an evolutionary nonlinear optimization technique inspired in musical composition that we have used in [15]. Another family of optimization techniques that are suited for this problem are the ones based on Particle Swarms [16], which we successfully used for that purpose in [17]. More specifically, in [17] we used an implementation that relies on augmented Lagrange multipliers to deal with restrictions [18]. Another more recent nonlinear optimization technique we have used for graph coloring in [19] is based on Coral Reefs [20]. More specifically, it is a bio-inspired technique, which simulates how a coral reef evolves, considering aspects like the fight for space in the reef and specific features of the corals' reproduction. Although all the aforementioned techniques have shown to be useful to color graphs, in this paper we have chosen Simulated Annealing (SA) [21] as it has been shown it is able to obtain high-utility results very efficiently [22]. In addition to SA, we have also considered Hill-Climbing (HC) as an optimization technique because, as discussed in [23], the comparison between HC and SA will let us assess if the problem under study is highly complex, because in those scenarios greedy optimizers like HC tend to be blocked in local optima, while the exploration probability of SA allows to escape from those local optima. The present paper contributes to this goal in the following ways:  
* We derive functions for the individual and social utilities, which we use later in the model (Section 2.1). * We model the joint optimization of fuel consumption and flight level assignment as a factorized optimization problem (Section 2.2). * We provide an approximate optimization solution to the problem as an instance of a wide class of coloring problems (Section 2.3). To validate our model and evaluate the significance of our contributions, we have performed a set of experiments over a graph representing the Spanish air space, to see the relative performance of different optimization approaches. The experiment settings and the discussion of results are provided in Section 3. Finally, Section 4 summarizes our conclusions and sheds light on future lines of research.