# Flight Level Assignment Using Graph Coloring
## 2 Flight-Level Assignment as Spectrum Coloring Problem with Hard Constraints
### Individual and Social Utility Models
#### 2.1.1 Individual Utility Model: Fuel Consumption  
Individuals (e.g., flight operators) will want to minimize their utility functions, defined as the fuel consumption for each flight. Fuel consumption is a function of both the distance traveled and the cruise flight level, and takes into account fuel consumption at the cruise phase and during the climb phase. For longer flights, more time will be spent in the cruise phase, so flying at sub-optimal altitude will have a more noticeable effect on fuel consumption than in a shorter flight. In this work, we will neglect the fuel used during the descent phase as literature suggests that the descent profile for most flights is approximately the same regardless of total distance [8], and the idle setting of engines during this phase makes fuel expenditure invariant to distance and flight level. With the aforementioned considerations, the individual utility function corresponding to fuel consumption that we will use for a flight of distance \(d\) and assigned flight level \(x\) is:  
\[F(d,x)=F_{climb}(x)+F_{ cruise}(d-\varepsilon,x), \tag{1}\]  
where \(F_{climb}\) represents the fuel consumption during the climb phase, \(F_{ cruise}\) is the fuel consumption during the cruise phase, and \(\varepsilon\) is the horizontal distance traversed during the climb. \(F_{climb}\) and \(F_{ cruise}\) are defined as piecewise functions depending on the aircraft used. In this work, we will focus on the Airbus A320 aircraft, which is one of the most common aircrafts used for Spanish domestic routes. There exists a trade-off between the better Specific Air Range (SAR) ((SAR) is the distance traveled per fuel unit) provided by higher flight levels (until the optimal FL for the A320 is reached), and the fuel required to reach a given FL. In other words, some flights may be so short that reaching their optimum flight level may not be worthy, since the fuel savings during the time spent at cruise level do not compensate the fuel cost of reaching that altitude. To pre-calculate these optimum flight levels, we will define the functions as piecewise linear approximations based on existing literature. For the climb costs, we use [24] to construct Table 1.  
In view that the relationship between the flight level number and the fuel consumption is approximately linear, we can then define the following piecewise linear approximation:  
\[\left\{ \begin{array}{ll}F_{climb}(x)=2.75(x-200)+600,&200\leq x\leq 300\\ F_{climb}(x)=3(x-300)+875,&300\leq x\leq 400\end{array} \right. \tag{2}\]  
For the cruise phase, we use [25] to obtain the results in Table 2, where different FLs are listed, along with the SAR goodness (expressed as % deviation from optimal SAR) and the slope resulting from comparing to the previous (lower) FL. We use these slopes to make a piecewise-linear approximation defining an auxiliary function \(S(x)\), which gives an approximate value for this percentage deviation from the optimum SAR corresponding for a given flight level:  
\[\left\{ \begin{array}{ll}S(x)=-4-0.2(340-x),&200\leq x\leq 340\\ S(x)=-4+0.125(x-340),&340<x\leq 360\\ S(x)=-1.5+0.125(x-360),&360<x\leq 380\\ S(x)=-0.15(x-380),&380<x\leq 400\end{array} \right. \tag{3}\]  
Based on the \(S(x)\) function and the fact that  
\[\text{SAR}=\frac{\text{distance}}{\text{Unit Fuel}}\Rightarrow F_{ cruise}=\frac{\text{distance}}{\text{SAR}}, \tag{4}\]  
we can deduce an expression for the fuel required in the cruise phase, based on distance \(d\), flight level \(x\) and a constant \(\varphi\) that represents the optimum SAR:  
\[F_{ cruise}(d,x)=\frac{d}{(1+S(x))\varphi}. \tag{5}\]  
We can now find the total fuel required, based on these piecewise functions. We recall the previous expression  
\[F(d,x)=F_{climb}(d)+F_{ cruise}(d-\varepsilon,x). \tag{6}\]  
Since we now have explicit expressions for climb and cruise, we can calculate the utility function, just needing to set the parameters \(\varepsilon\) and \(\varphi\) to a realistic value. The values that are used will be set appropriately to the type of aircraft.