# Flight Level Assignment Using Graph Coloring
## 3 Experimental Evaluation
### Algorithms Used  
Given the intersection graph obtained from the air routes, we will use some variations of the optimization techniques proposed in [29], with utility functions and hard constraints adapted to the context of ATM. Four algorithms are used to address the graph coloring problem, two are inspired by Simulated Annealing (SA), and two by Hill-Climber (HC) optimization approaches. Similarly, two of the algorithms use a more greedy approach, where FLs are assigned as close to the optimum as possible for each route, whereas the other two use a global approach, where any FL may be assigned.  
There is a hard constraint on this graph coloring problem, which is that nodes sharing an edge should have a separation of at least \(\delta\) FLs. This is due to the fact that these nodes represent intersecting routes, so having them at the same FL would be unsafe. This illustrates how such an optimization pivots around finding a trade-off between safe and fuel-efficient FL assignments.  
The versions of SA and HC used work basically by starting at a random solution point (in our scenario, a random assignment of FLs to all flights), and iterating through single issue (in our case, single route) random mutation. Accordingly, at each iteration, the FL of a randomly selected airway is assigned a random new value. The key difference between HC and SA is that, for the hill-climber, the new mutated solution is only _accepted_ (and therefore used as a basis for the next iteration) when it yields an improvement in terms of utility, while for the annealer there is a finite probability to accept a solution even when it causes utility losses. That finite probability depends on a parameter called _annealing temperature_, and decreases as the algorithm iterates. The rationale is that this randomized acceptance approach allows the annealer to escape local optima, which gives it an advantage in highly rugged utility spaces [17].  
For the problem studied in this paper, the algorithms have been modified to enforce a separation of at least \(\delta\) FLs between crossing routes, and to take into account the utility function based on fuel efficiency. In both the SA and HC algorithms, conflicts are avoided at every color assignment. To prevent conflicts, the algorithm follows these steps when assigning a new random color to a node:  
1. Create a list of available colors representing FLs (this depends mostly on whether it is a global or greedy approach).
2. Iterate through the node's neighbors (that is, all intersecting routes), and remove from the list of available colors all colors within separation \(\delta\).
3. Once this process is done, if there are still colors available, one is chosen randomly.
4. For the Greedy HC and Greedy SA: If none of the colors within the original range are available, the algorithm assigns the next closest available FL (i.e., if FL\({}_{opt}\) is the optimal FL for a given route and the original range is FL\({}_{opt}\pm 5\), then the algorithm will assign the first available FL out of FL\({}_{opt}\pm 6\), FL\({}_{opt}\pm 7\), etc.).
5. If none of the 40 FLs are available, this means the current node cannot be changed.  
Then, the utility function for fuel efficiency depends on the distance of the route and the assigned FL. Since the length of the route is fixed, utility optimization becomes completely dependent on FLs. Since not all routes can be assigned their optimum FL, part of the optimization implicitly revolves around determining which routes have the least negative effect when assigned a suboptimal FL.