Sonia Cafieri

Riadh Omheni

Mixed-Integer Nonlinear Programming for Aircraft Conflict Avoidance by Sequentially Applying Velocity and Heading Angle Changes

Keywords: Air traffic management, Conflict avoidance, Mixed-integer nonlinear programming, Deterministic global optimization, Modeling, MINLP

We consider the problem of aircraft conflict avoidance in Air Traffic Management systems. Given an initial configuration of a number of aircraft sharing the same airspace, the main goal of conflict avoidance is to guarantee that a minimum safety distance between each pair of aircraft is always respected during their flights. We consider aircraft separation achieved by heading angle deviations, and propose a mixed 0-1 nonlinear optimization model, that is then combined with another one which is based on aircraft speed regulation. A two-step solution approach is proposed, where the two models are sequentially solved using a state-of-the-art mixed-integer nonlinear programming solver. Numerical results validate the proposed approach and clearly show the benefit of combining the two considered separation maneuvers.

Introduction

We address a real-life problem arising in the context of Air Traffic Management (ATM), and more specifically in Air Traffic Control, that is the problem of aircraft conflict avoidance during en-route flights. Two aircraft are said to be in conflict if during their flights there is a loss of a standard separation between their trajectories, that has to be always respected instead to guarantee air traffic safety. The main aim of Air Traffic Management is that of ensuring that aircraft are always safely guided in the sky and on the ground, and aircraft conflict avoidance constitutes one the major challenges to be faced. This is specially due to safety issues in a context of growing air traffic on the world scale. Air traffic in Europe, for example, is expected to double within the next two decades [START_REF]Eurocontrol long-term forecast: IFR Flight Movements 2010-2030[END_REF]. This implies an increasing workload for air traffic controllers, with a consequent growing difficulty in ensuring air traffic safety. Thus, ATM needs more automation in tackling crucial processes like aircraft conflicts resolution, as pointed out in the context of major ATM projects Sesar [START_REF] Omheni | The european ATM master plan[END_REF] and NextGen [START_REF] Hansman | Impact of NextGen integration on improving efficiency and safety of operations[END_REF].

Developing mathematical models and efficient and reliable algorithms for aircraft conflict avoidance has been the focus of a great deal of research attention in last years. Aircraft conflict avoidance could indeed be probably considered as an emerging application of Operations Research.

Problem statement

Let us consider a set of aircraft sharing the same airspace. Conflict avoidance is performed monitoring a selected portion of the airspace over a given time horizon, and issuing suitable separation maneuvers when a loss of pairwise separation between aircraft is detected. We consider the case of aircraft in the en-route airspace, where the standard separation norms are 5 NM horizontally and 1000 ft vertically (1NM (nautical mile)= 1852 m; 1ft (feet)= 0.3048 m). Furthermore, we consider aircraft that are all allocated to the same flight level, and thus our focus is on horizontal separation maneuvers. Flight level changes to resolve conflicts are in fact rarely employed because of fuel consumption and of passengers discomfort. The problem we address is at a tactical level, i.e., aircraft in their en-route cruise flights are monitored in a short time window (20-30 minutes) and conflicts are resolved a short time before the loss of separation potentially occurs (so, a fast solving, preferably in the order of seconds, is generally expected). We are given aircraft with their initial positions in the observed airspace, and with their velocity vectors, that is their speed and their heading angles defining their trajectories. The aim is that of providing, starting from such initial configuration, a new one that is conflict-free for all aircraft.

To solve an aircraft conflict, various maneuvers can be employed, mainly including altitude changes (AC), heading angle changes (HAC) and velocity changes (VC). Mathematical models are then based on this kind of maneuvers. Optimization problems naturally arise in this context, as in general one aims at separate aircraft while deviating them as less as possible from their original trajectory.

Based on the comprehensive survey conducted by Kuchar and Yang [START_REF] Kuchar | A review of conflict detection and resolution modeling methods[END_REF], it appears that the majority of detection and resolution methods up to the year 2000 focus on AC and HAC. In particular, the great attention towards heading angle changes is related to the fact that these maneuvers are currently the most used by air traffic controllers. In the last 15 years, some subliminal speed control-based models have been proposed. The subliminal speed control, that was firstly introduced in the context of the European project ERASMUS [START_REF] Brochard | Erasmus -en route air traffic soft management ultimate system[END_REF], consists of modifying the aircraft speeds within a very small range around their original speeds, without informing air traffic controllers. This kind of control is highly promising to introduce some automation in ATM, thus reducing the workload of air traffic controllers.

In the following, we review some approaches based on mixed-integer programming, that constitutes the framework of the approaches developed in this paper.

Mixed-integer programming literature

Mixed-integer programming approaches have been used in aircraft conflict detection and resolution since the 2000's. An overview of MINLP modeling is presented in [START_REF] Cafieri | MINLP in Air Traffic Management: Aircraft conflict avoidance[END_REF]. In 2002, Pallottino, Feron and Bicchi [START_REF] Pallottino | Conflict resolution problems for air traffic management systems solved with mixed integer programming[END_REF] proposed two different formulations of the multi-aircraft conflict avoidance problem as a mixed-integer linear program (MILP) by allowing all aircraft to perform either VC or HAC, but not both. These models are then solved by standard MILP software. Christodoulou and Costoulakis [START_REF] Christodoulou | Nonlinear mixed integer programming for aircraft collision avoidance in free flight[END_REF] proposed a combinatorial approach that combines aircraft velocities and heading angles. The obtained problem is a mixed-integer nonlinear program (MINLP), that is solved for small-scale instances. Vela et al. [START_REF] Vela | A mixed integer program for flight-level assignment and speed control for conflict resolution[END_REF] proposed a mathematical model that is formulated as a MILP and is based on concepts of speed control and flightlevel assignment. In a second work, Vela et al. [START_REF] Vela | Near real-time fuel-optimal en route conflict resolution[END_REF] presented a MILP model to identify the required heading angle and speed changes for each aircraft to avoid conflicts. As an objective function, they chose to minimize the fuel costs incurred due to the considered changes. MILP models based on speed control were also proposed in [START_REF] Rey | Minimization of potential air conflicts through speed regulation[END_REF][START_REF] Rey | Subliminal speed control in air traffic management: Optimization and simulation[END_REF] where the total conflict duration is minimized. Since 2011, Alonso-Ayuso, Escudero and Martín-Campo have proposed three mathematical models which all extend the work of Pallottino, Feron and Bicchi [START_REF] Pallottino | Conflict resolution problems for air traffic management systems solved with mixed integer programming[END_REF]. In [START_REF] Alonso-Ayuso | Collision avoidance in air traffic management: A mixed-integer linear optimization approach[END_REF], the authors presented a mixed 0-1 linear optimization model based on VC and AC. The second model, presented in [START_REF] Alonso-Ayuso | A mixed 0-1 nonlinear optimization model and algorithmic approach for the collision avoidance in ATM: velocity changes through a time horizon[END_REF], is a mixed 0-1 nonlinear optimization one where velocity change is used as a maneuver to resolve conflicts. In 2014, a non-convex MINLP model based on turn changes has been developed [START_REF] Alonso-Ayuso | Exact and approximate solving of the aircraft collision resolution problem via turn changes[END_REF]. Once all conflicts are solved, the aircraft are forced to return to the original flight configuration by solving an unconstrained quadratic program. This feature will be used in our work presented in this paper. Note finally that there is no computational comparison of the performances of above three models. Cafieri and Durand [START_REF] Cafieri | Aircraft deconfliction with speed regulation: new models from mixed-integer optimization[END_REF] proposed MINLP formulations for deconfliction based on speed regulation, where each aircraft is allowed to fly with a modified speed in a time window. More recently, a MINLP model for maximizing the number of conflicts that can be solved when only velocity regulation is performed has been introduced by Cafieri [START_REF] Cafieri | Maximizing the number of solved aircraft conflicts through velocity regulation[END_REF]. In addition to mixed-integer programming, local continuous optimization to air traffic conflict resolution has been proposed. Peyronne et al. [START_REF] Peyronne | Solving air traffic conflict problems via local continuous optimization[END_REF] presented a B-spline trajectory model involving only one continuous variable per aircraft, and a semi-infinite programming formulation for the separation constraints and showed some numerical results on problems involving up to six conflicting aircraft.

Contribution statement and paper structure

In this paper, we consider aircraft separation achieved by heading angle changes and by speed regulation. First, a mixed-integer nonlinear program (HAC) is proposed, where aircraft conflicts are solved by aircraft heading angle deviations. Then, this model is combined with another mixed 0-1 nonlinear program, that maximizes the number of aircraft conflicts that can be solved by subliminal speed regulation.

These two MINLPs are solved using a state-of-the-art global exact solver. A two-step methodology is then proposed, where the solution of the second MINLP is used as a pre-processing step for the first one. This is shown to be able to significantly speed-up the resolution process. Numerical results clearly show, indeed, the benefit of the proposed combination of the two considered aircraft separation maneuvers, thus validating the proposed approach. Such an approach appears to be, on the other hand, appropriate for the considered real-time application, where subliminal speed control is expected acting as a first filter for the traffic. Then, the traffic is made fully conflict-free thanks to heading changes, that correspond to maneuvers currently mainly employed by air traffic controllers.

The paper is organized as follows. In Section 2, we provide a general description of the addressed problem and present two MINLP models for aircraft conflict avoidance. A mixed-integer nonlinear program based on HAC is first proposed. Then, a mixed-integer program aiming to maximize the number of solved conflicts using VC is presented. We give thereafter, in Section 3, a detailed description of the proposed algorithm, combining the solution of the above MINLPs. In Section 4, numerical results are presented and some numerical issues are discussed. Conclusions and perspectives for future work are drawn in Section 5.

Modeling aircraft conflict avoidance

Let A denote a set of aircraft sharing the same airspace and flying during their cruise phase, all at the same flight level. Each aircraft i ∈ A is identified by the triplet (x i , y i , φ i ) giving its abscissa, ordinate and direction of motion in ] -π, π], with (x 0 i , y 0 i , φ i ) the initial triplet, at time t = 0. The minimum separation distance condition between two aircraft i and j ∈ A can be expressed as follows:

(x i (t) -x j (t)) 2 + (y i (t) -y j (t)) 2 ≥ d 2 ∀t, (1)
where d is the minimum required horizontal separation distance and x i (t) and y i (t) are the coordinates of the aircraft i at time t. When condition (1) is not satisfied for some t ≥ 0, aircraft i and j are said to be in conflict. In such a case, (at least) one maneuver to separate the aircraft has to be performed. In the following subsection, we focus on separation achieved by aircraft heading angle changes and propose a MINLP model for solving aircraft conflicts.

MINLP for HAC

Let us consider n aircraft with known initial spatial coordinates and trajectory directions (heading), flying through an air sector during a time window observed by air traffic controllers. Our goal is to determine for each of the n aircraft, i ∈ A, its minimum heading angle change that allows to satisfy the separation condition (1), thus obtaining a conflict-free aircraft configuration. An example is displayed on Figures 1 and2.

• • • • conflict zone φ i φ j φ k φ
• • • • φ i φ j φ k φ θ i θ j θ k θ Figure 2:
After conflict resolution, the new trajectory of each aircraft is given by a solid line.

The proposed approach, presented in the following, is based on the work of Cafieri and Durand [START_REF] Cafieri | Aircraft deconfliction with speed regulation: new models from mixed-integer optimization[END_REF]. In that work, aircraft headings were kept fixed, while velocity vectors were modified by changing aircraft speeds to achieve separation. Here, we consider the opposite situation: aircraft speeds are fixed, while we allow aircraft change their headings.

Assume that uniform motion laws apply for aircraft. The abscissa and ordinate of an aircraft i at time t are given by

x i (t) = x 0 i + cos(φ i + θ i )v i t and y i (t) = y 0 i + sin(φ i + θ i )v i t,
where θ i is the angle variation for aircraft i for solving the conflict situations and v i is its initial speed. Note that v i is fixed for all i, while θ i , for all i represent the decision variables of the optimization problem that we are going to define. Substituting the expressions of x i (t) and y i (t) into (1), we obtain

t 2 V r ij 2 + 2tX r0 ij • V r ij + X r0 ij 2 -d 2 ≥ 0, (2)
where the relative initial distance X r0 ij between aircraft i and j and the rela-tive speed V r ij are vectors in R 2 given respectively by

X r0 ij := x 0 i -x 0 j y 0 i -y 0 j (3)
and

V r ij := cos(φ i + θ i )v i -cos(φ j + θ j )v j sin(φ i + θ i )v i -sin(φ j + θ j )v j (4)
and 2) is a quadratic equation in one unknown t. By differentiating its left-hand side member, the time for which the condition ( 2) is minimal, and so aircraft i and j have minimal relative position, is

X r0 ij • V r ij denotes the inner product of X r0 ij and V r ij . Equation (
t m ij = - X r0 ij • V r ij V r ij 2 .
By substituting this into (2), we obtain the following expression:

V r ij 2 X r 0 ij 2 -d 2 -(X r0 ij • V r ij ) 2 ≥ 0, (5)
which no longer depends on t. The separation condition ( 5) is to be imposed only when t m ij ≥ 0. To this end, we introduce a new, binary, variable y ij for each pair of aircraft i and j such that

y ij = 1 if t m ij ≥ 0, 0 otherwise.
This yields the following separation condition for aircraft i and j

y ij V r ij 2 X r 0 ij 2 -d 2 -(X r0 ij • V r ij ) 2 ≥ 0.
For each pair of aircraft, such a condition constitutes the main constraint of the optimization problem for aircraft deconfliction.

As for the objective function, we choose to minimize for all aircraft their heading angle variations, that is

min i∈A θ 2 i .
The main motivation for this choice is to ensure that flight plans of the considered aircraft do not change significantly with respect to the original ones. Notice that other objective functions can be considered, such as the minimization of the fuel cost or the total difference in flight time between the original expected time and that needed to perform the HAC maneuvers to avoid all potential conflicts. The proposed optimization problem is summarized below. For the sake of simplification, we use the notation B := {(i, j) ∈ A × A : i < j}. The decision variables are: θ i , for all i ∈ A, t m ij for all (i, j) ∈ B, and y ij for all (i, j) ∈ B.

min i∈A θ 2 i (6a) s.t. θ min i ≤ θ i ≤ θ max i , ∀ i ∈ A, (6b)
y ij V r ij 2 X r 0 ij 2 -d 2 -(X r0 ij • V r ij ) 2 ≥ 0, ∀ (i, j) ∈ B, (6c)
t m ij = - X r0 ij • V r ij V r ij 2 , ∀ (i, j) ∈ B, (6d)
t m ij (2y ij -1) ≥ 0, ∀ (i, j) ∈ B, (6e)
y ij ∈ {0, 1}, ∀ (i, j) ∈ B (6f)
where X r0 ij and V r ij are given by ( 3) and ( 4) respectively. Constraints (6b) are imposed to ensure that the heading angle variation for each aircraft satisfies some bounds, due to operational reasons. In our implementation, these bounds are set to θ min i = -π/6 and θ max i = π/6, for all i ∈ A. Constraints (6c) are the separation constraints for each pair of aircraft. Constraints (6d) define t m ij , (6e) are added to check the sign of t m ij (the separation condition (6c) is only imposed when t m ij ≥ 0), and (6f) are integrality constraints on y ij .

Note that trigonometric functions appear in the definition of V r ij . Further nonlinearities appear in constraints (6c), (6d) and (6e). Some of these nonlinearities can actually be reformulated using standard techniques [START_REF] Liberti | Reformulations in mathematical programming: A computational approach[END_REF]. Constraints (6e), which contain the product of a binary variable and a continuous variable, can be reformulated for all (i, j) ∈ B to two linear inequalities, once bounds on variables t m ij are computed (starting from bounds deduced on V r ij ). Then, a big-M reformulation can be applied on constraints (6c).

From some numerical experiments, however, it appears that these reformulations do not have a relevant impact on the computational efficiency of the resolution process. This is probably due to the fact that one of the main difficulties in the numerical solution of problem ( 6) is specially related to nonlinearities coming from trigonometric functions. The above reformulations will be therefore not considered in the following. After having solved problem [START_REF] Cafieri | MINLP in Air Traffic Management: Aircraft conflict avoidance[END_REF], and so determined the optimal heading angle change θ * i for each aircraft i ∈ A that ensures avoiding all potential conflicts, new changes in the heading angles have to be made in order to return aircraft to their initial trajectories (see Figure 3). The idea proposed by Alonso-Ayuso, Escudero and Martín-Campo [15, Section 4] can be easily applied in our context. It consists of determining the optimal time for which each aircraft can return to its trajectory in a final conflict-free configuration, by solving an unconstrained quadratic programming (QP) problem for each pair of aircraft (i, j) ∈ B. The objective function of this problem is the relative Euclidean distance between aircraft, that for each pair (i, j) is computed using the new aircraft spatial coordinates obtained by using heading angles from [START_REF] Cafieri | MINLP in Air Traffic Management: Aircraft conflict avoidance[END_REF], and is minimized with respect to time. More precisely, knowing θ * i for each aircraft i ∈ A from the solution of ( 6), the new coordinates of aircraft i are given by

• • • • φ i + θ * i • (x i (T * i ), y i (T * i )) φ j + θ * j φ k + θ * k φ + θ *
x i (t) = x 0 i + cos(φ i + θ * i )v i t and y i (t) = y 0 i + sin(φ i + θ * i )v i t. (7)
Using these formulas, the quadratic program to be solved for each pair of aircraft (i, j) ∈ B is min

t ij x i (t ij ) -x j (t ij ) y i (t ij ) -y j (t ij ) 2 (8)
that allows us to compute for each (i, j) ∈ B the minimum time such that i and j are separated using their new heading. Problem ( 8) is a convex continuous unconstrained QP problem, that can be easily solved by standard QP solvers. In practice, it is always solved, for each (i, j) ∈ B, after the solution of the HAC problem (6), i.e., after computation of optimal θ * i for each aircraft i ∈ A. Once the optimal solution t * ij for problem ( 8) is found, we compute

T * i := max j =i j∈A t * ij
as the optimal time for which aircraft i can return to its initial trajectory in a conflict-free configuration. Using [START_REF] Pallottino | Conflict resolution problems for air traffic management systems solved with mixed integer programming[END_REF], this time corresponds to the point (x i (T * i ), y i (T * i )) as shown in Figure 3. destination Knowing this point and the exit point from the air sector, it is easy to determine the new trajectory of each aircraft to come back to its initial trajectory. This is given by the straight line that connects both points. In [START_REF] Alonso-Ayuso | Exact and approximate solving of the aircraft collision resolution problem via turn changes[END_REF], Alonso-Ayuso, Escudero and Martín-Campo gave an explicit formula of the corresponding new angle of motion.

4, standard terms of the the functions. good The solution, by global MINLP solvers, of the HAC (6) followed by the QP (8) may be quite time consuming (as discussed in Section 4). HAC ( 6) is a nonconvex problem which may have many local minima. Additionally, the presence of mixed 0-1 variables and of the nonlinearity of cosine and sine functions may impact the performance of a global solver. In order to speed up the solution process, the proposed mathematical programming model can be properly combined with another one. This is presented in the next subsection.

Maximizing the number of solved conflicts using VC

Recently, Cafieri [START_REF] Cafieri | Maximizing the number of solved aircraft conflicts through velocity regulation[END_REF] presented a model for the maximization of the number of aircraft conflicts that can be solved by only performing velocity regulation.

We briefly recall hereafter this model. The headings of aircraft are kept fixed (so, no trigonometric functions appear) and the main decision variables are: vi for all i, a continuous decision variable representing the aircraft speed, which is eventually modified with respect to the original one to solve conflicts, and z ij for all (i, j) ∈ B, a binary decision variable defined as

z ij =
1 if aircraft i and j are separated (no conflict), 0 otherwise.

Further variables are y ij for all (i, j) ∈ B, used into another condition for aircraft separation, and a linearizing variable w ij for all (i, j) ∈ B, both described below. The model reads as follows.

max

(i,j)∈B w ij (9a) s.t. vmin i ≤ vi ≤ vmax i , ∀ i ∈ A, (9b)
(X r 0 ij • vr ij ) 2 -vr ij 2 ( X r 0 ij 2 -d 2 ) (2z ij -1) ≤ 0, ∀ (i, j) ∈ B, (9c) (X r 0 ij • vr ij )(2y ij -1) ≥ 0, ∀ (i, j) ∈ B, (9d)
w ij ≥ y ij , ∀ (i, j) ∈ B, (9e)
w ij ≥ z ij , ∀ (i, j) ∈ B, (9f) w ij ≤ y ij + z ij , ∀ (i, j) ∈ B, (9g) w ij ∈ [0, 1], ∀ (i, j) ∈ B, (9h) y ij , z ij ∈ {0, 1}, ∀ (i, j) ∈ B. (9i)
The bounds on vi , given by constraints (9b), are imposed to ensure that speed variations are small enough so that a subliminal control of velocities is performed, as suggested in the context of the ERASMUS project [START_REF] Dupré | How erasmus can support an increase in capacity in[END_REF]. More precisely, the bounds vmin i and vmax i for each aircraft i are respectively given by 0.94v i and 1.03v i , to ensure that speeds vary between -6 % and +3 % of the original speed. Constraint (9c) expresses that i and j are separated when the corresponding z ij is equal to 1. A further constraint, (9d), accounts for pairs of aircraft that are separated when, if separated at their initial positions, they have intersecting trajectories (here considered as straight lines) that are diverging (X r 0 ij • vr ij ≥ 0). To do so, additional binary variables y ij , ∀(i, j) are introduced, equal to 1 when the condition X r 0 ij • vr ij ≥ 0 is satisfied. Variables w ij , ∀(i, j) are then used to model the "or" condition relating the two separation constraints, (6c) (satisfied when z ij = 1) and X r 0 ij • vr ij ≥ 0 (satisfied when y ij = 1). The objective function is a linear function simply counting the pairs of separated aircraft.

Note that one of the main differences of this model with respect to the above presented HAC is that here the aircraft heading angles are kept fixed, while only the speeds are changed. Furthermore, here we do not aim at solving all conflicts optimizing a given criterion, but at maximizing the number of conflicts that the (subliminal) speed control can solve. In this sense, model ( 9) can be used as a first "filter" of air traffic in a given air sector, leaving eventually other conflicts to be solved by means of another separation maneuver, such as heading deviation. Such an approach can be easily seen in the context of an automation of aircraft speed variations expected in a next future, thus reducing the controllers' workload. These considerations lead us to propose the algorithm given in the next section.

3 Algorithm Max VC+HAC Models ( 6) and ( 9) are MINLPs. In both cases, some nonlinearities come from the product of continuous and binary variables. In addition to that, the use of trigonometric functions in the HAC model adds strong nonlinearities that make the problem hard to solve. ( 6) resulting in On the other side, model [START_REF] Vela | A mixed integer program for flight-level assignment and speed control for conflict resolution[END_REF] gives no guarantee to solve all conflicts, in particular head-tohead conflicts whose solutions need the use of maneuvers other than speed changes. Note also that the presence of constraints (9b) can be a source of infeasibility for some instances, meaning that it may happen that some conflicts cannot be solved by carrying out small adjustments in the speeds of aircraft. Remark that providing the HAC problem with input data such that a number of aircraft pairs are already separated (and hence separation constraints are straightforwardly satisfied) can speed up the solution process.

Based on these remarks and in order to take full advantage of the features of both models ( 6) and ( 9) and to provide a trade-off between efficiency and reliability, we propose a new algorithm for aircraft conflict avoidance, whose steps are summarized in Algorithm 1.

Algorithm 1 Aircraft deconfliction: Max VC + HAC

Step 1 Detect all head-to-head conflicts.

Step 2 Solve Max VC ( 9) without considering head-to-head conflicts.

Step 3 If all conflicts are solved then Stop.

Else

Solve HAC ( 6) with aircraft having new velocities given by the solution of Max VC ( 9) and then go to Step 4.

End if

Step 4 Solve the QP (8) for each pair of aircraft (i, j) ∈ B.

Given an initial configuration of n aircraft sharing the same airspace during an observed time window, Algorithm 1 begins the resolution process by detecting all head-to-head conflicts. Then, the Max VC model [START_REF] Vela | A mixed integer program for flight-level assignment and speed control for conflict resolution[END_REF], applied on the remaining pairs of aircraft, is solved at Step 2 to determine the possible changes to the speed of aircraft so as to separate as many aircraft pairs as possible. Our choice of not considering head-to-head conflicts when solving ( 9) is argued by the fact that this type of conflicts cannot be solved by only performing velocity regulation. Step 2 of Algorithm 1 will be henceforth referred as a pre-processing step. It acts as a first filter on the considered air traffic, before completing the deconfliction process by heading deviations. If all conflicts are solved after applying the pre-processing step, then the resolution process stops. Otherwise, model ( 6) is solved to determine a new aircraft configuration such that all conflicts are avoided. Note that for this model, the new speeds computed at Step 2 are used. The benefit of this choice is confirmed by the numerical results presented in Section 4. Once the optimal heading angle changes are found, we force the aircraft to return to their destination points by solving model (8) at Step 4.

Note that Algorithm 1 always outputs an optimal solution corresponding to an aircraft configuration where all conflicts are solved. When Algorithm 1 stops just after the solution of Max VC, because this is enough to solve all conflicts, the obtained solution is optimal with respect to criterion (9a), while when HAC is applied, optimal values are computed to deviate as less as possible from the original flight plans. However, note that from the operational viewpoint, even in the case of a solution obtained using Max VC only, where there is not a minimization of the deviation from original flight plans, such a deviation is never relevant thanks to the subliminal control framework.

Numerical experiments

Models ( 6), ( 8) and ( 9) are implemented using the Ampl modeling Language [START_REF] Fourer | AMPL: A Modeling Language for Mathematical Programming[END_REF]. We made a comparative test of Algorithm 1 with/without Step 1 and Step 2 on two collections of test problems. The first collection is built by randomly placing on a circle of a given radius a number of aircraft that are initially all headed to the center. This leads to a highly symmetric configuration, where symmetry is also reinforced by considering the same speed for all aircraft. It is well known that this kind of test problem, while being unrealistic, is very hard to solve by exact global solvers. These problems, named pb n* in Table 4, are known in the literature as circle problems. For the second collection, aircraft are arranged around a circle and have trajectories randomly chosen with a heading angle ∈ [-π/6, π/6] with respect to the diameter of the circle. The end point of each trajectory belongs to the circle as well. Note that these problems are more realistic than circle problems without deviation. In Table 5, they are referred to as rpb n*. For both collections, the aircraft move at the same speed, namely 400 NM/h. After executing Step 2 of Algorithm 1, new values may be assigned to speeds of all (or some) aircraft. Given constraints (9b), these new values range from 376 NM/h to 412 NM/h. Note that this kind of instances have been also considered by [START_REF] Christodoulou | Nonlinear mixed integer programming for aircraft collision avoidance in free flight[END_REF][START_REF] Alonso-Ayuso | Exact and approximate solving of the aircraft collision resolution problem via turn changes[END_REF][START_REF] Cafieri | Aircraft deconfliction with speed regulation: new models from mixed-integer optimization[END_REF][START_REF] Peyronne | Solving air traffic conflict problems via local continuous optimization[END_REF]. The standard separation distance, d, to be respected between aircraft trajectories is equal to 5 NM. To get a perspective on the size of problems being solved, Table 1 summarizes the sizes of the MINLP problem (HAC model) varying the number of aircraft. Recall that the objective function and the equality and inequality constraints (except the bound constraints) are nonlinear.

In this paper, we are interested in the global solution of the problem at hand by deterministic MINLP solvers (this kind of solvers need an algebraic representation of the objective and constraint functions for the computa- tion of convex envelopes and under-estimators [START_REF] Bussieck | Minlp solver software[END_REF]). MINLP solvers falling in the category of interest are the following: Antigone [START_REF] Misener | Antigone: Algorithms for continuous / integer global optimization of nonlinear equations[END_REF], Baron [START_REF] Sahinidis | Baron: A general purpose global optimization software package[END_REF],

Couenne [START_REF] Belotti | Branching and bounds tightening techniques for non-convex MINLP[END_REF], LindoApi [START_REF] Lin | The global solver in the LINDO API[END_REF] and Scip [START_REF] Achterberg | SCIP: solving constraint integer programs[END_REF]. Our choice of the solver for the numerical experiments has been established on the basis of the capability of the solvers to handle trigonometric functions and of their availability as free solvers. Table 2 summarizes the characteristics of the above MINLP solvers.

To the best of our knowledge, trigonometric functions are handled by two solvers only, Couenne and LindoApi, and only Couenne is a free opensource solver. This motivated our selection of Couenne as MINLP solver for our numerical experiments. For the resolution of the convex QP (8), we used the open source software package for large-scale non-linear optimization Ipopt [START_REF] Wächter | On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming[END_REF], that implements an Interior-Point method. Both solvers were run with their default settings.

- - × - Baron - - × - Couenne × × × × LindoApi - - × × Scip × × × -
Tests were performed on a 2.66 GHz Intel Xeon (octo core) processor with 32GB of RAM and Linux Operating System. Tables 4 and5 show the comparison of the results obtained using HAC with Max VC as a preprocessing step (Algorithm 1) and using HAC only on the original problem. The headings are as follows: n, number of aircraft; n c , number of all potential conflicts; n hthc , number of head-to-head conflicts; time, computing time in seconds, and obj, optimal value of the objective function of model [START_REF] Cafieri | MINLP in Air Traffic Management: Aircraft conflict avoidance[END_REF].

As previously mentioned, the goal of the second step of Algorithm 1 is not to solve all conflicts, but to maximize the number of conflicts that can be solved using the subliminal speed control maneuver. We are specially interested in a first step of the algorithm that could be fast, while solving as many conflicts as possible. In order to avoid a time-consuming resolution of Max VC (9), a CPU time limit of 30 seconds was imposed. As it can be seen from Tables 4 and5, the use of Max VC (9) as a pre-processing step for HAC [START_REF] Cafieri | MINLP in Air Traffic Management: Aircraft conflict avoidance[END_REF] significantly improves the solution in terms of CPU time and quality of solution. The most significant time improvement occurs for problem rpb n8 3, for which the computing time is reduced from 11967.96 seconds to less than 10 seconds, exhibiting a speed-up by a factor of 1316. Note that for this problem, 9 out of 10 conflicts were solved using the preprocessing step. To compare the numerical results presented in Tables 4 and5 more clearly, we make use of the performance profiles of Dolan and Moré [START_REF] Dolan | Benchmarking optimization software with performance profiles[END_REF]. Figure 4 summarizes, using a performance profile, these results. For τ ≥ 0, ρ s (τ ) is the fraction of problems for which the performance of a given algorithm is within 4 clearly highlights the benefit of using the proposed pre-processing step before solving the HAC model. In fact, the efficiency of this version of Algorithm 1, which is readable on the left vertical axis of the performance profile, is 80% whereas that of Algorithm 1 without applying a pre-processing step does not exceed 30%. This efficiency gain can be explained by the fact that the pre-processing step provides model [START_REF] Cafieri | MINLP in Air Traffic Management: Aircraft conflict avoidance[END_REF] with input data where in most cases the majority of conflicts are solved and there only remain some difficult conflicts (e.g. head-to-head conflicts) for which heading angle deviations have to be performed. This greatly simplify the branch-and-bound procedure for the solution of [START_REF] Cafieri | MINLP in Air Traffic Management: Aircraft conflict avoidance[END_REF]. In term of robustness, both versions of Algorithm 1 have the same rate of robustness since they solve all considered instances. However, better solutions were obtained when using a pre-processing for all tested problems, as presented in Tables 4 and5.

One reason behind such improvement is that the use of a pre-processing step breaks up the symmetry introduced in the initial problem by changing the velocity of some (or all) aircraft, thus making the feasible region of problem (6) larger than that without pre-processing. In fact, one observes that the solution of problem (6) without pre-processing consists of a symmetric configuration with all (or some) aircraft deviated either to the left (positive turn) or to the right (negative change). On the contrary, the optimal heading angle changes obtained by solving the HAC model after applying a pre-processing step can be a mixture of positive and negative values. The example in Table 3 illustrates this situation.

Increasing the number of aircraft, the number of constraints and variables (continuous and binary) increases. As expected in a Branch and Bound method, like the one implemented in the exact global solver Couenne, this leads to a significant increase in the computing time required to explore all the branches of the search tree to ensure that the obtained solution is a global optimum. The same conclusion was reached in [START_REF] Cafieri | Aircraft deconfliction with speed regulation: new models from mixed-integer optimization[END_REF][START_REF] Alonso-Ayuso | An exact multiobjective mixed integer nonlinear optimization approach for aircraft conflict resolution[END_REF]. For problems pb n*, that are highly symmetric, instances up to n = 5 are efficiently solved, while from n ≥ 6 they are highly computational demanding. Problems rpb n* appear to be easier to solve than the circle problems, and we are able to efficiently solve instances up to n = 8.

Remark 1. In some cases, the optimal solution returned by Couenne is slightly infeasible. This can be explained by the difficulty of the treatment of trigonometric functions (cosine and sine used in our HAC model) by MINLP solvers. Note that such behavior for Couenne has been already observed on some instances of the MINLPLIB collection [START_REF] Bussieck | MINLPLib -a collection of test models for mixed-integer nonlinear programming[END_REF]. To overcome this problem, we run Ipopt for the HAC model with integer variables fixed and the optimal solution returned by Couenne as a starting point. In all cases, it appears that a small modification of the variables is enough to obtain a "more feasible" solution. For example, by running Algorithm 1 on the problem pb n5 1 we obtain the optimal objective value f * = 0.008227. When testing the feasibility of the solution, it appears that one conflict remains not solved. When applying the procedure described above, Ipopt returns the following slightly modified solution f * = 0.008248, for which all conflicts are solved considering the associated heading angle changes. Note finally that the time needed to accomplish this task is negligible comparing to that needed for solving problem [START_REF] Cafieri | MINLP in Air Traffic Management: Aircraft conflict avoidance[END_REF]. In all our tests, it does not exceed 0.02 seconds.

Conclusions

We proposed a MINLP formulation (HAC) of the aircraft conflict avoidance problem, where potential conflicts are solved by aircraft heading angle deviations. This formulation has a quadratic objective and nonlinear nonconvex constraints. To speed-up the solution process, we also proposed the combination of the above MINLP with another one, Max VC, where the number of conflicts that can be solved by regulating the aircraft speeds is maximized. The idea is to provide the first MINLP with a pre-processing step, that from the operational viewpoint can be interpreted as a preliminary filter of the considered air traffic. Numerical results are encouraging and show the interest of the proposed two-step approach. As expected, the use of exact global solvers allows us to solve medium-scale problems. Alternative solution approaches will be investigated in future work to raise the size of solved problems, as well as further mathematical programming formulations and their possible reformulations.

Figure 1 :

 1 Figure 1: Initial configuration for 4 conflicting aircraft flying towards the center of a circle of a given radius.

Figure 3 :

 3 Figure 3: Forcing aircraft to return to their initial trajectories (dotted lines) after conflict resolution. Superscripts * indicate optimal values. At the point (x i (T * i ), y i (T * i )), aircraft i can return to its initial trajectory being separated from all other aircraft.

Figure 4 :

 4 Figure 4: Performance profile comparing the total CPU time for Algorithm 1 with and without pre-processing on a set of 52 randomly generated problems.

Table 1 :

 1 Dimensions of Problem (4) depending on the number of aircraft.

	n	# variables continuous integer continuous integer equality inequality # auxiliary variables # constraints
	2	5	1	21	1	3	6
	3	12	3	49	3	9	12
	4	22	6	89	6	18	20
	5	35	10	141	10	30	30
	6	51	15	205	15	45	42
	7	70	21	281	21	63	56
	8	92	28	369	28	84	72

Table 2 :

 2 An overview on deterministic global solvers for nonconvex MINLP.

	Solver	Free AMPL Deterministic Trigonometric functions
	Antigone

Table 3 :

 3 Solutions of problem pb n5 1 using HAC with and without preprocessing

	Optimal HACs With pre-processing Without pre-processing
	θ * 1	-0.033039	0.043072
	θ * 2	0.073481	0.074654
	θ * 3	0.030125	0.039003
	θ * 4	-0.020949	0.040227
	θ * 5	0.020258	0.032408
	a factor 2 τ of the best one. Figure

Table 4 :

 4 Conflicts resolution for circle problem without deviation using HAC with and without pre-processing

					Max VC		HAC		HAC
	Name	n n c n hth	Pre-processing n rc time (s)	(with pre-processing) n rc time (s) obj	(without pre-processing) n rc time (s) obj
	pb n2	2	1	1	1	0.00	0	0.14 0.001250	0	0.13 0.001250
	pb n3 1	3	3	0	3	1.99	0	0.82 0.002327	0	0.90 0.002501
	pb n3 2	3	3	0	1	1.22	0	1.29 0.001667	0	1.97 0.006665
	pb n3 3	3	3	1	1	0.05	0	0.43 0.000314	0	1.08 0.000950
	pb n4 1	4	6	0	3	6.18	0	5.07 0.003172	0	9.90 0.007240
	pb n4 2	4	6	0	2	5.60	0	7.26 0.007399	0	31.64 0.017065
	pb n4 3	4	6	2	2	0.09	0	0.21 0.000630	0	0.56 0.001318
	pb n5 1	5 10	1	5	16.14	0	24.49 0.008248	0	58.21 0.011629
	pb n5 2	5 10	1	5	23.85	0	30.69 0.017774	0	68.60 0.018468
	pb n5 3	5 10	1	6	19.24	0	25.79 0.006740	0	89.79 0.017100
	pb n5 4	5 10	2	5	25.81	0	32.71 0.012480	0	80.17 0.014750
	pb n5 5	5 10	0	5	21.65	0	26.73 0.005652	0	63.05 0.012149
	pb n5 6	5 10	0	6	31.21	0	16.45 0.004208	0	47.18 0.011225
	pb n5 7	5 10	1	5	23.62	0	33.46 0.006951	0	66.13 0.012262
	pb n5 8	5 10	2	5	19.92	0	66.16 0.019788	0	122.44 0.017556

Acknowledgment

The authors would like to thank the editor and the two anonymous referees, whose comments helped to improve the presentation of the paper. Financial support by French National Research Agency (ANR) through grant ANR 12-JS02-009-01 "ATOMIC" is gratefully acknowledged.