# Flight Level Assignment Using Graph Coloring
## 3 Experimental Evaluation
### Experimental Results
HC and SA is fairly similar and that the solutions obtained by the Global algorithms are better, with a lower fuel consumption, but they need more iterations to reach those improvements. It is interesting to observe that, for both \(\delta=0\) and \(\delta=1\), the Greedy approaches reach reasonably good solutions in a much shorter time than the Global approaches. For \(\delta=2\), our experiments have shown that the complexity of the graph does not allow to obtain feasible colorings, i.e., it is unfeasible to obtain FL assignments that ensure a separation of two flight levels when a pair of routes cross. Thus, we move the focus from the total fuel consumption to an in-depth analysis of the assignment of flight levels obtained by the different algorithms. In Figure 8 we show how FLs are assigned to routes. In all cases, we have considered the results obtained after 10,000 iterations of each algorithm. Moreover, although we ran 20 experiments, for the sake of clarity and without loss of generality, we only show the results of the first five of them. More specifically, the figure shows the number of times each flight level is used, for the cases \(\delta=0\) and \(\delta=1\). It is interesting to note that for \(\delta=1\) the FLs are more evenly used than for \(\delta=0\), and it is worth highlighting the peak in FL380 for \(\delta=0\), where the Airbus A320 has its optimum for the cruise (recall Table 2). Moreover, it is also interesting to note that, although for \(\delta=0\) all the algorithms converge to the optimal solution (as shown in Figure 6), the number of times that FL380 is used turns out to be lower in the Global approaches. Tables 3 and 4 deepen this analysis of the FL assignment provided by different techniques for \(\delta=0\) and \(\delta=1\), respectively, and using 10,000 iterations and 20 runs for each algorithm. First, the column labeled as 'FL use' describes the average number of times that each FL in use is used. For example, a value of 288 stands for the fact that flight levels in use are used, on average, 288 times each. The standard deviation of this value is key to understand if FLs are evenly used or not. Analyzing this performance parameter in both tables, we conclude that FLs are re-used less times in \(\delta=1\) and, as the standard deviation is much lower, the use of FLs is more even in \(\delta=1\), as it was also expected from Figure 8. The column labeled as 'FLs used' in Tables 3 and 4 represents the number of FLs used at least once in the solutions provided by the different techniques. We can observe that the mean number of FLs used is clearly higher in \(\delta=1\) than in \(\delta=0\). Finally, the column labeled as 'FL separation' represents the separation between crossing routes measured in FLs. For example, if two routes cross each other, one is assigned FL350, and the other FL370, then their separation is 2 FLs. This performance parameter is key for improving safety. The differences in this parameter between \(\delta=0\) and \(\delta=1\) are clear, as the mean separation between intersecting routes in \(\delta=0\) (resp. \(\delta=1\)) is around 1.2 (resp. 7) FLs. It is worth noting that, for the most interesting setting \(\delta=1\), although the fuel consumption of  
Figure 7: Total fuel consumption for the different techniques and \(\delta=1\). the Greedy approaches is slightly higher, the separation between FLs of crossing routes is also higher, which again confirms the trade-off between safety and fuel consumption. \begin{table}
\begin{tabular}{l c c c c c c} \hline \hline  & \multicolumn{2}{c}{**FL use**} & \multicolumn{2}{c}{**FLs used**} & \multicolumn{2}{c}{**FL separation**} \\  & **Mean** & **Std Dev** & **Mean** & **Std Dev** & **Mean** & **Std Dev** \\ \hline
**SA Global** & 250.43 & 183.46 & 21.55 & 0.59 & 6.03 & 0.35 \\
**SA Greedy** & 221.54 & 168.50 & 23.60 & 1.16 & 7.61 & 0.27 \\
**HC Global** & 261.82 & 178.75 & 21.60 & 0.58 & 6.14 & 0.22 \\
**HC Greedy** & 213.33 & 170.51 & 23.75 & 0.89 & 7.59 & 0.35 \\ \hline \hline \end{tabular}
\end{table}