# Flight Level Assignment Using Graph Coloring
## 3 Experimental Evaluation
### Experimental Results  
In this section we evaluate the performance in terms of fuel consumption for the four different algorithms stated before. To conduct this study, simulations were run with 100, 500, 1000, 2000, 3000, 4000, 5000 and 10,000 iterations, making 20 runs for each of them, to ensure statistical relevance of the results. With respect to the complexity of the algorithms used, for both HC and SA and for each iteration of the algorithm we require an approximately constant time for mutating a color. This is followed by an evaluation of the utility function, for which the complexity depends on the problem size. When we change the color of a vertex, the utility only changes for that vertex and all its neighbors. For that reason, being \(K\) the number of iterations of the algorithm and \(deg(G)\) the average degree ofthe graph, the expected complexity will be \(O(K\cdot deg(G))\). Furthermore, the worst-case complexity is \(O(K\cdot|V|)\), for \(|V|\) the number of vertices in the graph. After running the experiments, and as expected, we have observed that the computation time increases linearly with the number K of iterations. For example, using an Intel Core i7-2600 with 8 [EMAIL_ADDRESS] GHz and 8 GB RAM running Ubuntu 14.04.4 LTS, we have measured that the mean time required to run 1000 iterations of SA is 6.84 s with a 95% confidence interval of 0.24 s.  
For \(\delta=0\) (i.e., when crossing routes can use the same FL), airplane behavior is independent, as all the routes can use their optimal FL independently from the rest of the routes. Although this scenario with \(\delta=0\) does not represent a socially acceptable approach, due to its inherent risk, it is interesting as a baseline for three reasons. First, it will provide the minimum total fuel consumption, as each route can use its optimal FL. Second, as each flight is independent from the others, it will allow us to compute that optimum value exactly. Third, as for this scenario we are able to know the optimum value, we can test the validity of the proposed algorithms comparing their solutions with that optimum value. Thus, for \(\delta=0\), Figure 6 shows the evolution of the four algorithms studied, as a function of the number of iterations. For each algorithm, we show both the mean and the 95% confidence intervals of the results. The main conclusion from this figure is that all four approaches converge to the computed optimum fuel consumption, the value of which is 2366 tons of fuel. It must be noted that the convergence to the optimum of Global approaches is slower than that of Greedy approaches. Moreover, it is also interesting to note that there are no statistically significant differences between the results of SA and HC, telling us that SA is not able to take advantage from its ability to escape from local optima, suggesting that the state space is not highly rugged but instead has a monotonic structure. Figure 7 shows the results for the case \(\delta=1\). This is a much more realistic setting than \(\delta=0\), since crossing routes are now restricted not to use the same FL, i.e., these solutions do consider the social safety goal. Note that this figure still shows the optimum fuel consumption for \(\delta=0\), as a baseline and since the complexity of the case \(\delta=1\) (due to the interdependences among routes) makes it unfeasible to compute the optimum fuel consumption in this case. First of all, we can observe that, as expected, solutions with \(\delta=1\) are not able to reach the optimum fuel consumption of the case \(\delta=0\), because when \(\delta=1\) not all flights are able to use their optimum FL to minimize fuel consumption. However, from Figure 7 we can conclude that the cost of forbidding crossing routes to use the same FL is around 5% in fuel consumption. More specifically, this loss is 4% for the Global approaches and 6% for the Greedy ones. Comparing the different approaches, we see again that the performance of  
Figure 6: Total fuel consumption for the different techniques and \(\delta=0\).