Keywords

1 Introduction

With the high increasing demand for commercial flights each year, the Air Traffic Management (ATM) is becoming more and more complex and less efficient in reducing air traffic congestion. With respect to air traffic congestion, two main types can be identified corresponding to areas of airspace: terminal congestion (around airports) and en-route congestion (between airports). We are interested in reducing the en-route congestion and its induced cost while taking into account uncertainties. The paper studies the flight level assignment (FLA) problem and its robust variant. Our goal is reducing the total cost (and more specifically the flight delay) induced by airspace congestion through an appropriated FLA taking account of uncertainties such as weather condition, flight velocity, flight departure time, etc. We have shown in [7] that the FLA problem is NP-hard even for instances with only three altitude levels. It may also be shown easily that for a single altitude level the problem of maximizing the number of flights accommodated to this level is NP-hard by reduction to the maximum independent set problem. This work is in continuation of [7, 11].

This paper is organized as follows. After this introduction, in Sect. 2 we report a short discussion on related works and position the problem with respect to ATM. In Sect. 3 we present our approach and discuss in detail the FLA problem for a single level. In Sect. 4, we firstly report a discussion on conflict probability estimation based on the flight departure time and its induced cost, then computational results illustrate our findings. Finally, a conclusion is given in Sect. 5.

2 Context of the Work

Related Works. Optimization problems in ATM have been widely studied these last decades. We focus on some works related to a certain extent to the flight level assignment problem. Let us firstly refer to [6], Cook et al. have shown that how uncertainty affects the ATM system is the key element to a proper model and control it and improve its performance. The source of uncertainties varies from aircraft velocity and weather condition to flight departure time, etc. Based on uncertain predicted trajectories, Irvine presented in [10] a more simplified geometrical calculation of conflict probabilities. Babak et al. in [1] studied on the stochastic methods of conflict situation detection and conflict probability evaluation. A more recent study which accounts for the effects of wind uncertainties was presented in [8].

For a conflict resolution by rerouting, let us firstly cite Bertsimas and Stock [3] who show how to optimally control aircraft by rerouting, delaying, or adjusting the speeds of the aircraft in the ATC (Air Traffic Control) system to avoid airspace regions with reduced capacities due to weather conditions. In [4], Bertsimas et al. proposed a new ILP model for large-scale instances which covered all the phases of each flight and solved it for an optimal combination of flow management actions, including rerouting decisions. Constans et al. have proposed minimizing potential conflict quantity by dynamically imposing feasible modifications on the speeds of the aircraft in [5]. In [7, 11] we have already presented some work on FLA problem. This paper uses a similar mathematical model and extends it for the case of aircraft departure time following Mixture Gaussian distribution. New numerical results are also reported.

Problem Description. In real air traffic management, the airspace is regulated by a certain number of rules, one of them is the “Semicircular Rule”. According to this rule, an aircraft is not assigned consecutively one by one altitude levels but two by two at least, as in the European airspace, and even four by four in the USA since the European airspace is more restrictive than the American one. The air traffic controllers classify the aircraft depending on the angle of motion of the trajectories. So, they divide the set of aircraft under consideration in two groups: the ones flying with an angle of motion between \(-\pi \) and 0 radians (for instance) and the rest of aircraft (flying in the opposite direction). The aircraft in the first group are requested to fly only in the odd altitude levels and the ones in the second group are requested to fly only in the even altitude levels, even if they must change their altitude due to other conditions during the flight. In order to provide more safety to the airspace, the air traffic controllers follow these guidelines to reduce the number of conflict situations. So, if a conflict situation takes place, at least one aircraft is requested to follow some maneuver as heading angle or velocity changes, or in some situation climbing or descending to the following altitude level in which it is allowed to fly according to the Semicircular Rule. In our work we assume that during the planning phase, there will be a fixed level assigned to each aircraft and the aircraft is supposed to stay to this level for or the entire enroute flight period. We assume that for each aircraft there is a most preferred flight level which is decided mostly by the type of the aircraft and fuel consummation considerations. There are also some other alternative eligible immediate upper or lower levels, which allow to deal with congestion, whereas involving an additional cost. This paper deals with the problem of assigning a set of flights with given flight paths to different levels such that potential costs of conflict over all flights are minimized. We explore a stochastic version under a robust optimization framework. Some numerical results based on a test instance are also reported.

3 Mathematical Model and Solution Approach

We start with the mathematical formulation of the robust FLA problem with probability constraints. We assume that each constraint has to be feasible with some probability \(1 - \epsilon \).

Notation:

  • L gives the set of the flight levels l and \(F^l\) groups all flights allowed to fly to level l.

  • \(x_i^l\) is a binary variable that takes value 1 when the aircraft i flies on level l and 0 otherwise;

  • \(b_i^l\) gives the profit associated with flight i when assigned at level l;

  • \(P_i^l\) gives the admissible cost for a given flight i at level l;

  • \(S_i^l\) gives the set of flights j having a potential conflict with flight i when they fly in the same level l;

  • \({p_{ij}}\) is the induced cost associated with aircraft i when resolving a potential conflict with aircraft j;

  • \(M_i\) is a large number.

Assuming separate probability conditions, the mathematical formulation of the probabilistic FLA problem follows:

$$\begin{aligned} \max \qquad&\sum _{i\in F^l, l \in L}b_{i} x_i \end{aligned}$$
(1a)
$$\begin{aligned} s.t. \qquad&Pr(\sum _{j\in S_{i}^l} p_{ij}x_{j} + M_ix_i \le M_i + P_{i}) \ge 1 -\epsilon , \forall i\in F^l, l \in L \end{aligned}$$
(1b)
$$\begin{aligned}&\sum _{l\in L_i} x_{i}^l = 1, \forall i \in F, \end{aligned}$$
(1c)
$$\begin{aligned}&x_{i}^l \in \{0,1\}, \forall i \in F, l \in L_i. \end{aligned}$$
(1d)

Probability constraints (1b) ensure for each aircraft that the sum of experienced costs/delays will not exceed some given admissible cost with a high probability \(1 -\epsilon \). Constraints (1c) assigns each aircraft to some of its eligible levels, while the objective function looks for a solution that assigns the aircraft to the most preferred flight levels possible. Following the Bertsimas and Sim work [2], we can deduce the robust variant of the above problem by converting the probability constraints through some deterministic ones. This yields some ILP problem, which is at least as difficult as the conventional deterministic problem. All this justifies heading to approximated methods to deal with it. The main idea behind the proposed approach is to decompose the problem by altitude levels and deal with each of them separately. We handle the connections between levels through a greedy algorithm described at the end of the Section. We report below a detailed study of the problem associated to a single flight level called \(RP^l\).

3.1 The Problem Associated with a Single Flight Level \((RP^l)\)

Similarly to above, the mathematical formulation associated with the probabilistic FLA restricted to level l follows:

$$\begin{aligned} \begin{aligned} max \qquad&\sum _{i \in F^l } {b_i x_i } \\ s.t. \qquad&Pr\left( \sum _{j\in S_i^l}{{p}_{ij} x_j } \le M_i (1-x_i ) + P_i \right) \ge 1-\epsilon , \forall i \in F^l \\&x_i \in \lbrace 0, 1 \rbrace , \forall i \in F^l \end{aligned} \end{aligned}$$
(2)

where for sake of simplicity we use \(b_i, x_i, P_i\) instead of \(b_i^l, x_i^l, P_i^l\). Note also that \({p_{ij}}\) stands here for a random variable.

The above program is known to be a very difficult one. One way to tackle it is to use the Bertsimas and Sim model [2] which is used under some mild probability conditions not applied in our problem. Hence, to solve the above problem we have opted to use the model introduced in [12]. Intuitively, we introduce a parameter vector \(\gamma \in [0,1]^{|F^l|}\) which allows tuning the robustness of the solution in a convenient way. Applying this idea, we obtain the following model denoted below \(RP_{l\gamma }\):

$$\begin{aligned} \begin{aligned} \max \qquad&\sum _{i\in F^l}b_{i} x_i \\ s.t. \qquad&M_ix_i + \min \left\{ \sum _{j\in S_{i}^l} \bar{p}_{ij} x_j, \gamma _i \cdot \sum _{j\in S_{i}^l} \bar{p}_{ij} \right\} \le M_i + P_{i}, \forall i\in F^l \\&x_{i} \in \{0,1\}, \forall i \in F^l. \end{aligned} \end{aligned}$$
(3)

where \(\bar{p}_{ij}\) gives the maximal value that can be attained by \(p_{ij}\). The above formulation can be simplified a lot. Let us focus on the robust constraint i. Either we consider the worst case (maximum conflict induced costs), or we have a constraint: \(M_ix_i + \gamma _i.\sum _{j\in S_{i}^l} \bar{p}_{ij} \le M_i + P_{i}\). In this latter case, two sub-cases occur: when \(\gamma _i.\sum _{j\in S_{i}^l} \bar{p}_{ij} > P_{i}\), then \(x_i=0\); when \(\gamma _i.\sum _{j\in S_{i}^l} \bar{p}_{ij} \le P_{i}\), we have a dummy constraint which can be ignored.

These three cases are in fact summarized in the two following ones:

  • either flight i has total conflict costs less than the admissible cost and no constraint is necessary to model this situation;

  • or flight i is associated with maximal conflict costs, that is constraint \(M_ix_i + \sum _{j\in S_{i}^l} \bar{p}_{ij} x_j \le M_i + P_{i}\) represents this situation.

Hence, the analysis of the above robust model leads to a new one, which is very simple. Indeed, for a given value of \(\gamma _i\) we know in advance if the constraint corresponding to flight i is necessary to be put in the model or not. Let denote with \(I_c \subseteq F^l\) a subset of concerned flights with respect to a given vector \(\gamma \). In this way, instead of vector \(\gamma \) we use the subset \(I_c\) as a parameter enabling to tune robustness. We denote the corresponding problem by \(RP^l(I_c)\).

$$\begin{aligned} \begin{aligned} \max \qquad&\sum _{i\in F^l}b_{i} x_i \\ s.t. \qquad&M_ix_i + \sum _{j\in S_{i}^l} \bar{p}_{ij} x_j \le M_i + P_{i}, \forall i\in I_c \\&x_{i} \in \{0,1\}, \forall i \in F^l \end{aligned} \end{aligned}$$
(4)

With respect to vector \(\gamma \) considered, the size of the above LP varies between a few constraints (for small values of \(\gamma _i\)) and all constraints (for \(\gamma _i = 1, \forall i\)).

figure a

In the heuristic we use several parameters as \(p_{ij}, \bar{p}_{ij}, P_i\) for which we have developed specific estimation methods not presented here because of lack of space. The main idea behind the Algorithm 1 is to build the solution by taking into account only the most restrictive constraints while the other flights are set by default to their most preferred flight level. The feasibility of the obtained solution is checked and if necessary new constraints are added in the ILP. Hence, an important aspect studied in this work is the estimation of solution’s feasibility probability as presented below.

3.2 Solution Feasibility Estimation

Note first that the main uncertain parameter that we have considered is the departure time. Hereby we assume that the flight departure time follows a 4-component Mixture Gaussian Distribution proposed in [14].

We discuss now the methods that estimate the feasibility of solution assuming separated constraints for each flight: \(Pr (\sum _{j \in S_i^l} p_{ij} x_j + M_i x_i \le M_i + P_i ) \ge 1- \epsilon \). As \(Pr(\sum _{j \in S_i^l}p_{ij} x_j + M_i x_i \le M_i +P_i) \ge Pr(\sum _{j \in S_i^l}p_{ij} x_j \le P_i) \), we restrict ourselves in ensuring that \( Pr(\sum _{j \in S_i^l}p_{ij} x_j \le P_i) \ge 1- \epsilon \) for all \(x_i=1\).

Conservative Robust Method: we consider first the Soyster model [13], which looks for a solution robust to the worst case. This gives: \( \sum _{j \in S_i^l} \bar{p}_{ij} x_j \le P_i\) for all \(x_i=1\), which is equivalent to \( Pr(\sum _{j \in S_i^l}p_{ij} x_j \le P_i) =1\).

Probability Bound method: We apply the Hoeffding’s Inequality [9], which gives:

$$\begin{aligned} \begin{aligned} Pr(\sum _{j \in S_i^l}p_{ij} x_j \ge P_i)&=Pr(\sum _{j \in S_i^l}p_{ij} x_j - E[\sum _{j \in S_i^l}p_{ij} x_j] \ge P_i - E[\sum _{j \in S_i^l}p_{ij}] x_j )\\ {}&\le exp(- {2 (P_i - \sum _{j \in S_i^l} E[p_{ij}] x_j)^2}/({\sum _{j \in S_i^l} \bar{p}_{ij}^2 x_j})) =\epsilon _i \end{aligned} \end{aligned}$$
(5)

However, when \(P_i \le \sum _{j \in S_i^l} E[p_{ij}] x_j\), by definition of Hoeffding’s Inequality, the above formula can’t be applied, we thus set the probability \(Pr(\sum _{j \in S_i^l}p_{ij} x_j \le P_i)\) as zero. In case that \(P_i\) is bigger than the sum of all upper bounds of random variables, then the probability is surely 1. Thus, we obtain a piece-wise probability function as follows:

$$\begin{aligned} \begin{aligned} Pr(\sum _{j \in S_i^l}p_{ij} x_j \le P_i) ={\left\{ \begin{array}{ll} 0, \text {if } P_i \le \sum \nolimits _{j \in S_i^l} E[p_{ij}] x_j \\ 1, \text {if } \sum \nolimits _{j \in S_i^l} \bar{p}_{ij} x_j \le P_i \\ 1-\epsilon _i, otherwise \end{array}\right. } \end{aligned} \end{aligned}$$
(6)

Sampling Method: The last method tested is based on Monte-Carlo Simulation. We have randomly generated a large number of scenarios where for each flight the departure time is generated following the above mentioned Mixture Gaussian distribution.

3.3 Putting All the Pieces Together

We describe now a heuristic approach for the Robust FLA problem, that is deciding flight level assignment robust to uncertainties that can affect flights, essentially due to fluctuation on departure time. The main idea behind the Algorithm is to decompose the problem by altitude levels and deal with each of them separately (as described above), while handling the connections between levels.

figure b

4 Implementation and Numerical Results

The code is realized with C++ with Cplex 12 under Ubuntu 16.04 LTS-64 bits, i7-7820 HQ CPU @2.90GHz, 16G RAM. The test data corresponds to French air traffic of August 12th, 1999. Table 1 presents the characteristics of test data.

Table 1. Test instance
Full size table
Table 2. Numerical results
Full size table

In Table 2, \(P_i\) is bounded in [0, 30], calculated by \(P_i\)=duration_of_flight_i*coPi (where CoPi indicates the percentage of flight time allowed for conflict resolution), and the maximal number of iterations in Algorithm 2 is set to 10. eps stands for the infeasibility tolerance of solution, #CL indicates the number of flight changes from their most preferred flight level to a feasible one, #UF denotes the number of unassigned flights, #CM specifies the maximal number of potential conflict occurring for a flight in the given feasible solution, ElaTi gives the elapsed time on seconds to get a robust feasible solution. We have tested two types of instances: the B (basic) instances are these reported in Table 1 and I (incremented) instances give the basic instances incremented with 15% additional flights among the existing ones but scheduled 5 hours later. The obtained results show clearly that Monte-Carlo estimation method gives more satisfactory results for all scenarios.

5 Conclusion

In our work, we deal with robust FLA problem assuming the flight departure time as the main source of uncertainty [14]. We experiment several methods showing that the sampling method (Monte-Carlo Simulation) gives an accurate solution when the distribution of flight-induced cost is hard to analyze, however, the biggest inconvenience is that this method is expensive on computation time. Therefore, an analytical approximate method will be in focus of our future work.