NOMENCLATURE
- AC
Altitude Change
- ACC
Area Control Center
- AD
Airborne Delay
- APC
Aircraft Performance Category
- ATC
Air Traffic Control
- ATCos
Air Traffic Controllers
- CDR
Conflict Detection And Resolution
- EA
Entry Area
- EP
Entry Point
- FC
Fuel Consumption
- FL
Flight Level
- FT
Flight Time
- GA
Genetic Algorithm
- HAC
Heading Angle Change
- MEP
Multi Entry Point
- MILP
Mixed Integer Linear Programming Model
- MINLP
Mixed Integer Nonlinear Programming
- MIP
Mixed Integer Programming
- NB
Narrow Body
- PSO
Particle Swarm Optimization
- SC
Airspeed Change
- TS
Tabu Search
- WB
Wide Body
- XP
Exit Point
1.0 INTRODUCTION
As the world economy grows rapidly, the importance of the air transportation industry increases tremendously. Because of this growth, the airspace and airport capacities an unable to handle the traffic demand and congestions begin to appear at airports and airspaces. This situation leads to more aircraft conflicts within en route and terminal airspaces. The minimum separation distance between aircraft should be sustained to maintain safe flight operations. To avoid conflicts in the airspace, various resolution manoeuvers are applied to aircraft such as altitude change (AC), heading angle change (HAC) and airspeed change (SC). AC manoeuvers allow air traffic controllers (ATCos) to resolve potential conflicts quickly, on the other hand, they may lead to disruptions in air traffic flow at different flight levels (FL) such as new potential conflicts in the same or adjacent airspaces. HAC manoeuvers can provide resolutions for a wide range of conflict geometries in a reasonably short time in the horizontal plane but they cause increased task-load, monitoring and frequency occupancy time for ATCos. SC manoeuvers do not require any deviations in the flight path; therefore they can provide long-term resolutions using a single instruction without any extra monitoring. They also cause less fuel consumption than HAC. Their applicability, on the other hand, is highly dependent on the conflict geometry such that they are only appropriate for the narrow route crossing angle of conflicting aircraft. Combined manoeuvers (i.e. HAC and SC) offer more effective resolutions in terms of flight path disruption, ATCo task-load, monitoring and frequency occupancy time, as well as fuel consumption, for a wider range of conflict geometries(Reference Cetek1).
To provide prompt conflict resolution, the use of an automated decision support system in air traffic control (ATC) becomes more important. Therefore, the aircraft conflict detection and resolution (CDR) problem becomes a widespread subject for the tactical and pre-tactical phases of flights.
Kuchar and Yang(Reference Kuchar and Yang2) and Martin Campo(Reference Martin-Campo3) have presented comprehensive review articles regarding various CDR approaches. The following studies to be discussed include noteworthy and recent approaches implementing mixed integer programming (MIP) techniques for the CDR problem. Pallottino et al.(Reference Pallottino, Feron and Bicchi4) presented a mixed integer linear programming (MILP) model for aircraft conflict resolution that was based on a geometrical construction, which included trigonometric functions, to maintain conflict free flight operations. The model allows aircraft to use either HAC or SC in order to avoid collision, but the model does not apply the two manoeuvers at the same time. Christodoulou and Costoulakis(Reference Christodoulou and Costoulakis5) developed the previous model and integrated the HAC and SC together to avoid conflicts for small-scale problems. Vela et al.(Reference Vela, Solak, Singhose and Clarke6,Reference Vela, Solak, Clarke, Singhose, Barnes and Johnson7) proposed two different models that use AC-SC and HAC-SC techniques to minimise fuel consumption. They used a space discretisation technique to deal with the CDR problem. Alonso Ayuso et al.(Reference Alonso-Ayuso, Escudero and MartÍn-Campo8) developed the geometrical construction model of Pallottino et al.(Reference Pallottino, Feron and Bicchi4) by combining AC manoeuvers with SC manoeuvers. Then, Alonso Ayuso et al.(Reference Alonso-Ayuso, Escudero and MartÍn-Campo9) presented a mixed integer nonlinear programming (MINLP) model using SC manoeuvers that takes the acceleration impact into consideration. The objective of this function was to minimise the acceleration rate. Also, Alonso Ayuso et al.(Reference Alonso-Ayuso, Escudero and MartÍn-Campo10) proposed a MINLP model that uses HAC manoeuvers to resolve conflicts and then forces the aircraft to return to their original trajectories. Cafieri and Durand(Reference Cafieri and Durand11) proposed a MINLP model that utilises SC manoeuvers to avoid conflicts. Due to the complexity of the problem, they developed a new heuristic approach. Cafieri and Rey(Reference Cafieri and Rey12) presented a different MINLP model from that of Cafieri and Durand(Reference Cafieri and Durand11). They aimed to obtain the largest conflict-free aircraft set and to maximise the number of resolved conflicts using SC manoeuvers. To improve the performance of the model, a pre-processing algorithm was implemented to determine potential conflicts. Moreover, Cafieri and Omheni(Reference Cafieri and Omheni13) presented another MINLP model that utilises HAC and SC sequentially. The results showed that combining HAC and SC manoeuvers made a progressive contribution to conflict resolution. Omer(Reference Omer14) presented three MILP models that use HAC and SC manoeuvers to minimise fuel consumption and airborne delay. The first model uses a space discretisation technique to resolve air conflicts. The second and third models utilise time horizon discretization and time decomposition, respectively. The models allow aircraft to perform one initial manoeuver. Alonso-Ayuso et al.(Reference Alonso-Ayuso, Escudero, MartÍn-Campo and MladenoviĆ15) proposed a multi-objective model that implemented HAC, SC and AC manoeuvers. The model uses goal programming and aimed to minimise the deviation from the current heading angle, airspeed and flight level. Hong et al.(Reference Hong, Choi, Oh, Lee and Kim16) proposed a MINLP model in order to maintain conflict-free flight by HAC and SC. The model adopted the particle swarm optimisation (PSO) technique to resolve conflicts, because the nonlinear constraints increased the solution time and made it difficult to reach a feasible solution. Cecen and Cetek(Reference Cecen and Cetek17) proposed a two-step mathematical model based on the multi entry point (MEP) approach and vector manoeuver model to prevent aircraft conflicts. The presented MILP model aimed to find the best entry point assignment combination. Due to the complexity of the problem, two metaheuristics, such as genetic algorithm (GA) and tabu search (TS), were chosen to obtain the result. The first step aimed to minimise the total conflict resolution time. If any conflict occurred in the first step, a fuel optimal vector manoeuver would be applied to conflicting aircraft pairs for resolution before the aircraft enter the airspace.
In this paper, an aircraft conflict resolution model is formulated using an MILP technique to further enhance the MEP approach introduced in our previous work (Cecen and Cetek(Reference Cecen and Cetek17)) by integrating it with airspeed adjustment and a new heuristic approach. The idea of adding alternate entry points to existing airspace configurations is to create alternate conflict geometries by moving potential conflict points to different locations in the airspace. Thus, the number of the potential conflicts can be reduced significantly by simply changing the entry points. The SC manoeuvers, on the other hand, alter the flyover of the aircraft at the potential conflict points. The use of SCs combined with MEP, therefore, enhances the conflict resolution capability and generates a set of conflict-free trajectories. The proposed heuristic searches for the optimal combination of entry point and airspeed assignments in this conflict-free trajectory set. The combined use of SC and MEP can also offer a reduced number of instructions and monitoring times for ATCos, relatively easy pilot procedures, and reduced fuel consumption for airlines compared to the vector manoeuvers in the conventional airspace route structure with fixed entry and exit points. The proposed model uses a space discretisation technique to consider the potential aircraft conflicts instead of searching the entire airspace. Besides which, all manoeuvers are implemented by aircraft prior to entry into the airspace. The model aims to create conflict free trajectories while minimising the total changes in entry points and airspeed values. Due to the complexity of the problem (i.e., the large number of variables and parameters), a new heuristic algorithm was created to resolve aircraft conflicts and regulate the air traffic flow management. The algorithm was tested for a wide range of traffic scenarios and yielded promising results.
More specifically, our contributions are as follows: First, we integrated the MEP with SC manoeuvers to generate conflict free trajectory in en-route operations. Second, the proposed model consists of an effective and applicable aircraft conflict resolution algorithm from air traffic controller, pilot and airline perspectives. This model can also be implemented in pre-tactical conflict resolution which allows ATCos to manage the entire airspace rather than resolving short-term conflicts. Third, we present a new heuristic algorithm with a new perspective of a neighbourhood generation technique. Finally, the model can obtain conflict-free trajectories for different air traffic-flow rates for a reasonable time period in less than a minute for complex airspace route configurations.
The rest of the paper is structured as follows: Section 2 presents the problem description; Section 3 presents the mathematical models; Sections 4 , 5 and 6 describe the heuristic algorithm, the computational results and the conclusion, respectively.
2.0 PROBLEM DESCRIPTION
The aircraft conflict resolution techniques allow aircraft to fly through airspace without violating the safe separation distance D min between each other. Air traffic control services are provided in the airport zones, terminal control areas and en-route airspaces. En-route airspaces constitute the largest portion of the airspaces where aircraft can perform climb, descend and cruise operations, and these are handled by area control centers (ACC). In each of these centres, air traffic controllers monitor and control aircraft flying on direct or indirect routes between fixed entry and exit points in to and out of the airspace. They forecast possible conflicts based on the position and airspeed of the aircraft and give instructions such that vector maoneuvers, airspeed and altitude changes can be applied in order to avoid collisions.
This study focuses on aircraft conflict resolutions in the horizontal plane within the en-route airspace. The motions of aircraft are assumed to be deterministic for the selected altitude and flight conditions. In order to evaluate the proposed approach, a baseline model was generated to represent the existing en-route airspace (i.e. fixed entry points) and conflicts were assumed to be resolved using conventional vector manoeuver techniques with fixed bank angle turns (i.e., 20°) in the horizontal plane. After obtaining the baseline results, the same scenarios were run for the proposed approach that implements MEP and airspeed reduction techniques instead of vector manoeuvers.
A space discretisation technique was implemented to detect aircraft conflicts by controlling only the critical points of the airspace which are referred to as “potential conflict points” without searching the entire airspace. Aircraft conflicts take place on entry into the airspace, route intersections and exit points. Therefore, two different conflict configurations, that are crossing and trailing conflicts, occur in this model (Fig. 1). However, head on conflicts are not taken into consideration because air traffic flow takes place in only one direction for a single flight level.
Figure 1. Conflict geometries: (a) crossing conflict and (b) trailing conflict.
The minimum separation time between aircraft pairs, 
${T_{ii'}}$ can be expressed by the following equation(Reference Carlier, Nace, Duong and Nguyen18):
\begin{equation}{T_{ii'}} = {{{D_{min}}} \over {{V_i}{V_{i'}}\left| {\sin {\theta _{ii'}}} \right|}}\sqrt {{{\left( {{V_i}} \right)}^2} + {{\left( {{V_{i'}}} \right)}^2} - 2{V_i}{V_{i'}}\cos \left( {{\theta _{ii'}}} \right)} {\rm{}}\end{equation}In Equation (1), 
${D_{min}}$ is the horizontal separation distance in the airspace, 
${V_{i}}$ and 
${V_{i^{\prime}}}$ are the airspeeds of the leading and trailing aircraft, respectively, and 
${\theta_{ii^{\prime}}}$ is the intersection route crossing angle. In order to provide safe separation, the model can alter their route configuration, their airspeed together, or individually, prior to entry into the airspace. The separation time of each potential conflict point is calculated and added to the model as a parameter using Equation (1). The model checks any potential crossing conflict for time separations between aircraft using different entry points but the same exit point (
$cre{q_{{k_1}{k_2}{v_1}{v_2}l}}$), aircraft using the same entry point but different exit points (
$bre{q_{{l_1}{l_2}{v_1}{v_2}k}}$) and aircraft using different entry and exit points (
$sre{q_{{v_1}{v_2}n}}$). A generic route structure is given in Fig. 2. The conventional route structure consists of only one entry point (EP) for each entry area (EA) which is EP2, EP5, EP8 and EP11. But the proposed approach has three entry points for each entry area. The model creates two alternate entry points with 10 NM distance between each entry area without changing the exit points (XP), such as XP1, XP2, XP3 and XP4.
Table 1 Discretisation of airspeed values (knots) at FL370
Figure 2. A generic airspace route configurations.
The model checks each aircraft pair if they use the same potential conflict points. The main idea is to generate conflict free trajectories for each aircraft by using entry point and airspeed assignment manoeuvers. It is assumed that entry point and airspeed assignments are performed within a distance of 20 NM prior to the entry into the airspace. The MEP approach allows changes of the initial entry point of the aircraft but it does not make any changes of the airspace exit point, therefore aircraft are able to follow their original route configurations in the next airspace. Furthermore, the airspeed changes do not lead to any extra deviations from the route between the entry and exit points. Therefore, the proposed approach allows the model to alter potential conflict points with different airspeeds. It is also assumed that once the initial airspeeds of aircraft are changed, they maintain their new airspeed in order to ensure conflict-free flight through the airspace. Aircraft are classified into two different performance categories such as narrow-body jet (NB) and wide-body jet (WB). Four different airspeed values are determined for each aircraft performance category (APC) based on the base of aircraft data (BADA)(19) (Table 1). The model assigns an airspeed value to each aircraft at the airspace entry area, thus, it is easy to estimate flyover times at each potential conflict point.
The nominal airspeeds of NB and WB aircraft were estimated for the selected flight level (FL370) as 473kts and 495kts, respectively. The minimum airspeeds were kept above the minimum drag airspeed for the given aircraft and flight conditions. The proposed heuristic algorithm calculates the average airborne delay, average fuel consumption and average flight time according to the entry point and airspeed combination. The fuel consumption rates are taken from BADA and calculated based on flight distance and airspeed values.
In this study, the model aims to minimise three functions: total conflict resolution time (A), total changes in entry points (B) and total changes in airspeed (C). It is clear that the proposed model is a multi-objective optimisation problem and the linear scalarisation technique was applied so as to transform the problem into a single-objective optimisation problem:
\begin{equation}{\rm{Min\;}}{\alpha _1}A + {\alpha _2}B + {\alpha _3}C\end{equation}In Equation (2), the weights of 
${\alpha _1}$ , 
${\alpha _2}$ and 
${\alpha _3}$ are selected as 0.96, 0.02 and 0.02, respectively. The weight of 
${\alpha _1}$ is set to a much larger value than the others because the model primarily attempts to resolve all conflicts (i.e. to minimise A to zero) within the airspace rapidly. After finding conflict-free trajectories, it searches for a solution with minimum changes in entry points and airspeeds. These two objectives are equally important for ATC operations; therefore, their weights are set to the same values.
3.0 MATHEMATICAL MODEL
The aim is to assign each aircraft to the most suitable entry point according to their entry area with the appropriate airspeed value to avoid conflict. The objective function is to minimise the total conflict resolution time and the total changes of initial entry points and nominal airspeed values at the same time.
Therefore, sets, parameters, variables, objective functions and constraints are given as follows:
Sets
I set of aircraft
$i,{i_1},{i_2} \in I$J set of entry areas
$j \in J$K set of entry points
$k,{k_1},{k_2} \in K$L set of exit points
${\rm{\;}}l,{l_1},{l_2} \in L$P set of aircraft performance categories
$p \in P$N set of intersection points
$n \in N$V set of airspeed values
$v,{v_1},{v_2} \in V$
Parameters
M1: big number enough
M2: big number enough
M3: big number enough
- ${D_{min}}$: minimum separation distance between aircraft
- ${g_i}$: scheduled airspace entry time of aircraft i
- ${t_i}$: performance category of aircraft i
- ${r_i}$: entry area of aircraft I
- ${s_v}$: initial airspeed value of performance category v
- ${e_i}$: exit point of aircraft i
- $b{g_i}$: initial entry point of aircraft i
- ${h_v}$: the value of airspeed v
- ${d_{kn}}$: distance between entry point k and intersection point n
- $t{d_{kl}}$: distance between entry point k and exit point l
- ${p_{iknv}}$: fly over time of aircraft i from entry point k at intersection point n with airspeed v
- ${c_{iklv}}$: fly over time of aircraft i from entry point k at exit point i with airspeed v
- $sre{q_{{v_1}{v_2}n}}$: separation time at intersection point n between aircraft with airspeeds ${v_1}\;$and ${v_2}$, respectively
- $tre{q_{{k_1}{k_2}{v_1}{v_2}l}}$: separation time at exit point l between aircraft flying from entry point ${k_1}$and ${k_2}$ with aircraft airspeeds ${v_1}$and ${v_2}$
- $bre{q_{{l_1}{l_2}{v_1}{v_2}k}}$: separation time at entry point k between aircraft flying to exit point ${l_1}$and ${l_2}$ with aircraft airspeeds ${v_1}$and ${v_2}$
- ${u_{jk}}$: 0-1 parameter that is one if the entry point k is in the entry area j; otherwise, it is zero
- $ve{l_{pv}}$: 0-1 parameter that is one if the performance category of p is allowed to assign airspeed v; otherwise, it is zero
- ${o_{kln}}$: 0-1 parameter that is one if an aircraft flies from entry point k to exit point l via intersection point n; otherwise, it is zero
Variables
- $q{r_{ik}}$: actual entry time of aircraft i at entry point k
- ${w_i}$: conflict resolution time of aircraft i
A: the total conflict resolution time
B: the total changes in entry point
C: the total changes in airspeed value
- ${b_1}_{{i_1}{i_2}}$: 0-1 variable that is 1 if aircraft ${i_2}$ enters and leaves the airspace from the same entry and exit points before aircraft$\;{i_1}$; otherwise, it is zero
- ${b_2}_{{i_1}{i_2}}$: 0-1 variable that is 1 if aircraft ${i_2}$ exits the airspace before aircraft$\;{i_1}$ using the same entry point and different exit points; otherwise, it is zero
- ${b_3}_{{i_1}{i_2}}$: 0-1 variable that is 1 if aircraft ${i_2}$ enters the airspace before aircraft$\;{i_1}$ using different entry points and the same exit points; otherwise, it is zero
- ${b_4}_{{i_1}{i_2}}$: 0-1 variable that is 1 if aircraft ${i_2}$ flies over the intersection point before aircraft$\;{i_1}$ using different entry and exit points; otherwise, it is zero
- ${x_{ik}}$: 0-1 variable that is 1 if aircraft i is assigned to entry point k; otherwise, it is zero
- ${y_{iv}}$: 0-1 variable that is 1 if aircraft i is assigned to airspeed v; otherwise, it is zero
The objective functions and constraints used are as follows.
Subject to
\begin{equation}\mathop \sum \limits_{k|{u_{jk}} = 1} {x_{ik}} = 1{\rm{\;\;\;}}\forall {\rm{\;}}i,j|j = {r_i}\end{equation}
\begin{equation}\mathop \sum \limits_{v|ve{l_{pv}} = 1} {y_{iv}} = 1\;\;\;\forall \;i,p|p = {t_i}\end{equation}
\begin{equation}q{r_{ik}} = {g_i} + {\rm{\;}}{w_i}{\rm{\;\;\;\;\;\;\;}}\forall i,k\end{equation}
\begin{equation}{p_{iknv}} = q{r_{ik}} + \frac{{{d_{kn}}}}{{{h_v}}}{\rm{\;\;\;}}\forall i,k,n,v\end{equation}
\begin{equation}{c_{iklv}} = q{r_{ik}} + \frac{{T{D_{kl}}}}{{{h_v}}}{\rm{\;\;\;}}\forall i,k,l,v\end{equation}
\begin{equation}\begin{array}{lll} q{r_{{i_2}k}} - q{r_{{i_1}k}} \ge \frac{{{D_{min}}}}{{{h_{{v_2}}}}} - \left( {2 - {x_{{i_1}k}} - {x_{{i_2}k}}} \right)M1 - & \left( {2 - {y_{{i_1}{v_1}}} - {y_{{i_2}{v_2}}}} \right) M1 - ({b_1}_{{i_1}{i_2}})M1\\[8pt]
& \forall \;{i_1},{i_2},\;k,{v_1},\;{v_2}\;|{i_1} \ne {i_2},\;{e_{{i_1}}} = {e_{{i_2}}}\end{array}\end{equation}
\begin{equation}\begin{array}{lll} q{r_{{i_1}k}} - q{r_{{i_2}k}} \ge \frac{{{D_{min}}}}{{{h_{{v_1}}}}} - \left( {2 - {x_{{i_1}k}} - {x_{{i_2}k}}} \right)& M1 - \left( {2 - {y_{{i_1}{v_1}}} - {y_{{i_2}{v_2}}}} \right)M1 - \left( {1 - {b_1}_{{i_1}{i_2}}} \right)M1\\[8pt]
&\qquad\forall \;{i_1},{i_2},\;k,{v_1},\;{v_2}\;|{i_1} \ne {i_2},\;{e_{{i_1}}} = {e_{{i_2}}}\end{array}\end{equation}
\begin{equation}\begin{array}{lll} {c_{{i_2}kl{v_2}}} - {c_{{i_1}kl{v_1}}} \ge \frac{{{D_{min}}}}{{{h_{{v_2}}}}} - \left( {2 - {x_{{i_1}k}} - {x_{{i_2}k}}} \right)& M2 - \left( {2 - {y_{{i_1}{v_1}}} - {y_{{i_2}{v_2}}}} \right)M2 - \left( {{b_1}_{{i_1}{i_2}}} \right)M2\\[8pt]
& \forall \;{i_1},{i_2},\;k,{v_1},\;{v_2},l\;|{i_1} \ne {i_2},\;{e_{{i_1}}} = {e_{{i_2}}}\end{array}\end{equation}
\begin{equation}\begin{array}{lll} {c_{{i_1}kl{v_1}}} - {c_{{i_2}kl{v_2}}} & \ge \frac{{{D_{min}}}}{{{h_{{v_1}}}}} - \left( {2 - {x_{{i_1}k}} - {x_{{i_2}k}}} \right)M2 - \left( {2 - {y_{{i_1}{v_1}}} - {y_{{i_2}{v_2}}}} \right)M2 - \left( {1 - {b_1}_{{i_1}{i_2}}} \right)M2\\[8pt]
& \phantom{\forall \;{i_1},{i_2},\;k,l,{v_1},\;{v_2}\;|{i_1}\forall \;{i_1},{i_2}\ \ }\forall \;{i_1},{i_2},\;k,l,{v_1},\;{v_2}\;|{i_1} \ne {i_2},\;{e_{{i_1}}} = {e_{{i_2}}} \end{array}\end{equation}
\begin{equation}\begin{array}{lll} q{r_{{i_2}k}} - q{r_{{i_1}k}} & \ge bre{q_{{l_1}{l_2}{v_1}{v_2}k}} - \left( {2 - {x_{{i_1}k}} - {x_{{i_2}k}}} \right)M1 - \left( {2 - {y_{{i_1}{v_1}}} - {y_{{i_2}{v_2}}}} \right)M1 - ({b_2}_{{i_1}{i_2}})M1\\[8pt]
& \phantom{\forall \;{i_1},{i_2}\;{i_1}\ }\forall \;{i_1},{i_2},\;{l_1},\;{l_2},k,{v_1},\;{v_2}|{i_1} \ne {i_2},\;{e_{{i_1}}} \ne {e_{{i_2}}},\;{l_1} = {e_{{i_1}}},\;{l_2} = {e_{{i_2}}}\end{array}\end{equation}
\begin{equation}\begin{array}{lll} q{r_{{i_1}k}} - q{r_{{i_2}k}} & \ge bre{q_{{l_1}{l_2}{v_1}{v_2}k}} - \left( {2 - {x_{{i_1}k}} - {x_{{i_2}k}}} \right)M1 - \left( {2 - {y_{{i_1}{v_1}}} - {y_{{i_2}{v_2}}}} \right)M1 - \left( {1 - {b_2}_{{i_1}{i_2}}} \right)M1\\[8pt]
& \phantom{\forall \;{i_1},{i_2}\;{i_1}\ \ \ \ } \forall \;{i_1},{i_2},\;{l_1},\;{l_2},k,{v_1},\;{v_2}|{i_1} \ne {i_2},\;{e_{{i_1}}} \ne {e_{{i_2}}},\;{l_1} = {e_{{i_1}}},\;{l_2} = {e_{{i_2}}}\end{array}\end{equation}
\begin{equation}\begin{array}{l} {c_{{i_2}{k_2}l{v_2}}} - {c_{{i_1}{k_1}l{v_1}}} \ge tre{q_{{k_1}{k_2}{v_1}{v_2}l}} - \left( {2 - {x_{{i_1}{k_1}}} - {x_{{i_2}{k_2}}}} \right)M2 - \left( {2 - {y_{{i_1}{v_1}}} - {y_{{i_2}{v_2}}}} \right)M2 \\[8pt]
\qquad\ \ \ - \left( {{b_3}_{{i_1}{i_2}}} \right)M2 \qquad \forall \;{i_1},{i_2},\;{k_1},{k_2},l,{v_1},\;{v_2}\;|{i_1} \ne {i_2},\;\;{e_{{i_1}}} = {e_{{i_2}}},\;{k_1} \ne {k_2},l = {e_{{i_1}}}\end{array}\end{equation}
\begin{equation}\begin{array}{l} {c_{{i_1}{k_1}l{v_1}}} - {c_{{i_2}{k_2}l{v_2}}} \ge tre{q_{{k_1}{k_2}{v_1}{v_2}l}} - \left( {2 - {x_{{i_1}{k_1}}} - {x_{{i_2}{k_2}}}} \right)M2 - \left( {2 - {y_{{i_1}{v_1}}} - {y_{{i_2}{v_2}}}} \right)M2 \\[8pt]
\qquad\ \ \ - \left( {1 - {b_3}_{{i_1}{i_2}}} \right)M2 \qquad \forall \;{i_1},{i_2},\;{k_1},{k_2},l,{v_1},\;{v_2}\;|{i_1} \ne {i_2},\;\;{e_{{i_1}}} = {e_{{i_2}}},\;{k_1} \ne {k_2},l = {e_{{i_1}}}\end{array}\end{equation}
\begin{equation}\begin{array}{l} {p_{{i_2}{k_2}n{v_2}}} - {p_{{i_1}{k_1}n{v_1}}} \ge sre{q_{{v_1}{v_2}n}} - \left( {2 - {x_{{i_1}{k_1}}} - {x_{{i_2}{k_2}}}} \right)M3 - \left( {2 - {y_{{i_1}{v_1}}} - {y_{{i_2}{v_2}}}} \right)M3 - ({b_4}_{{i_1}{i_2}})M3\\[8pt]
\forall \;{i_1},{i_2},\;{l_1},{l_2},{k_1},\;{k_2},\;{v_1},\;{v_2}\;|\;{i_1} \ne {i_2},\;{e_{{i_1}}} \ne {e_{{i_2}}},\;\;{k_1} \ne {k_2},\;{l_1} = \;{e_{{i_1}}},\;\;{l_2} = \;{e_{{i_2}}},\;{o_{{k_1}{l_1}n}} = 1,\\[3pt]
\quad\qquad {o_{{k_2}{l_2}n}} = 1\end{array}\end{equation}
\begin{equation}\begin{array}{l} {p_{{i_1}{k_1}n{v_1}}} - {p_{{i_2}{k_2}n{v_2}}} \ge sre{q_{{v_1}{v_2}n}} - \left( {2 - {x_{{i_1}{k_1}}} - {x_{{i_2}{k_2}}}} \right)M3 - \left( {2 - {y_{{i_1}{v_1}}} - {y_{{i_2}{v_2}}}} \right)M3 \\[8pt]
\qquad\quad - \left( {1 - {b_4}_{{i_1}{i_2}}} \right)M3 \qquad\forall \;{i_1},{i_2},\;{l_1},{l_2},{k_1},\;{k_2},\;{v_1},\;{v_2}\;|\;{i_1} \ne {i_2},\;\;{e_{{i_1}}} \ne {e_{{i_2}}},\;{k_1} \ne {k_2},\\[3pt]
\qquad\qquad\qquad\qquad\qquad\quad\qquad\qquad{l_1} = \;{e_{{i_1}}},\;{l_2} = \;{e_{{i_2}}},\;{o_{{k_1}{l_1}n}} = 1,\;{o_{{k_2}{l_2}n}} = 1\end{array}\end{equation}
\begin{equation}\mathop \sum \limits_i \left[ {b{g_i} - {\rm{\;}}\left( {\mathop \sum \limits_k {x_{ik}} \cdot k} \right)} \right] = B\end{equation}
\begin{equation}\mathop \sum \limits_i \mathop \sum \limits_{v|v = {t_i}} \left[ {{s_v} - \mathop \sum \limits_q {y_{iq}} \cdot q} \right] = C\end{equation}
\begin{equation}\mathop \sum \limits_i {w_i} = A\end{equation}
\begin{equation}{b_1}_{{i_1}{i_2}},{\rm{\;\;}}{b_2}_{{i_1}{i_2}},{\rm{\;}}{b_3}_{{i_1}{i_2}},{b_4}_{{i_1}{i_2}} \in \left\{ {0,1} \right\}{\rm{\;\;\;\;\;}}\forall {\rm{\;}}{i_1},{i_2}\end{equation}
\begin{equation}x_{ik} \in \left\{ {0,1} \right\}\quad \forall {\rm{\;}}i,k \end{equation}
\begin{equation}{y_{iv}} \in \left\{ {0,1} \right\}\quad \forall {\rm{\;}}i,v \end{equation}The objective function (3) aims to minimise the total conflict resolution time, the total changes of the initial entry points and the total changes of the nominal airspeed values at the same time. Constraint set (4) assigns each aircraft to one entry point according to its entry area. Constraint set (5) ensures that each aircraft is assigned to one airspeed according to its APC. Constraint sets (6), (7) and (8) calculate the flyover times at the entry, intersection and exit points for each aircraft, respectively. Constraint sets (9), (10), (11) and (12) maintain the required separation time between all aircraft pairs for trailing conflicts. A binary decision variable 
${b_1}_{{i_1}{i_2}}$ determines which aircraft enters and exits the airspace first. During the flight no overtaking is considered for trailing aircraft. Constraint sets (13) and (14) maintain the required separation time between all aircraft pairs for conflicts using the same entry point with different exit points. The binary decision variable 
${b_2}_{{i_1}{i_2}}$ determines which aircraft enters the airspace first. Constraint sets (15) and (16) maintain the required separation time between all aircraft pairs for conflicts using different entry points and the same exit point. The binary decision variable 
${b_3}_{{i_1}{i_2}}$ determines which aircraft leaves the airspace first. Constraint sets (17) and (18) maintain the required separation time between all aircraft pairs for conflicts using different entry and exit points. The binary decision variable 
${b_4}_{{i_1}{i_2}}$ determines which aircraft crosses the route intersection point first. Constraint sets (19) and (20) calculate the total changes in entry point assignment and nominal airspeed value for each aircraft. Constraint set (21) calculates the total conflict resolution time. Constraints (22)-(24) are sign constraints.
4.0 HEURISTIC ALGORITHM
The proposed mathematical model requires considerable computational time to obtain optimal results. Therefore, a new heuristic algorithm was developed to find a feasible solution in a short time. The general structure of the heuristic is presented in Fig. 3. The entry area, initial entry point, exit point, aircraft performance category and the corresponding initial airspeed are provided to the algorithm as the parameters. Then the heuristic generates an initial solution, S based on this information. Using this initial solution, it produces neighboring solutions, S ’ and calculates the fitness (objective) function for each of them. To find the fitness functions, the algorithm checks for any conflicts between aircraft first. If any conflict is detected, it calculates the conflict resolution time for each aircraft and the conflicting aircraft pair is added to the conflicting aircraft set to generate new neighboring solutions. After that the total conflict resolution time, total changes in entry point and airspeed values are computed to obtain the fitness function of each neighboring solution. One of the neighboring solutions is chosen as the new current solution, S based on the selection criteria. The algorithm repeats these steps until the termination criteria are reached. The algorithm provides the best solution (i.e. the best combination of entry point and airspeed assignments) minimizing the fitness function. The steps of the algorithm are explained in more detail in the following subsections 4.1 - 4.5.
Figure 3. General structure of the heuristic algorithm.
4.1. Solution representation
The algorithm adopts a 2 × n matrix solution representation. Columns correspond to an aircraft index, i entering to the airspace in ascending order (i.e., i = 1 to n). The first and second rows indicate the airspace entry point (k) and airspeed (v) indices assigned to the corresponding aircraft. A randomly generated sample solution matrix is presented in Fig. 4. In this sample solution, while aircraft 2 is assigned to entry point 5 and airspeed 2, aircraft 6 is assigned to the entry point 11 and airspeed value 2. In the algorithm, each airspeed assignment represents a specific airspeed value as presented in Table 4. The entry point and airspeed assignments are performed according to the entry area and aircraft performance category information. For example, airspeed indices 1, 2, 3 and 4 of NB aircraft correspond to 473, 450, 432 and 420kts, respectively. Likewise, airspeed indices 1, 2, 3 and 4 of WB aircraft correspond to 495, 472, 450 and 432kts.
Figure 4. Matrix solution representation.
4.2. Initial solution
The heuristic algorithm begins the search with an initial solution and aims to improve the fitness value in each iteration. In the algorithm, it is assumed that the aircraft initially use the entry points of a conventional route structure at their nominal airspeeds for their performance category at the given flight level. Therefore, the initial solution is generated based on these conventional entry points of each entry area (i.e., k = 2, 5, 8 and 11) and nominal airspeed values of each aircraft category (i.e., v = 1 corresponding to V1 = 473kts for NB and V1 = 495kts for WB) as presented in Fig. 5.
Figure 5. Representation of the selected initial solution.
4.3. Fitness function evaluation and selection process
The algorithm checks for any loss of separation between each aircraft pair for each potential conflict point in the entire airspace. The model looks for the conflicts in the entry points, crossing points and exit points according to the necessary time separation. The time separation values for each point is added to the model as a parameter. If any conflict is detected, the model calculates the necessary conflict resolution time for each aircraft and updates the airspace entry times to solve this conflict based on entry point and airspeed assignments. The time difference between the updated entry time and the initial entry time is referred to as the “conflict resolution time”, w i. According to the assignments, it also calculates the total changes in entry points and airspeed values. The heuristic algorithm uses two strategies to select the current solution. First, if the fittest neighbourhood solution bs has a lower fitness value than the current solution S, bs replaces S as the current solution. Second, if bs is higher than or equal to S, the roulette wheel technique is implemented to select the new S. This technique allows the algorithm to jump to other parts of the solution space and increase the possibility of reaching an optimal or near-optimal solution.
4.4. Neighborhood generation
Neighborhood generation is an important step to obtain feasible solutions. This step uses the current solution, S in each iteration to generate neighbourhood solutions. Two different approaches are presented in this process. First, the algorithm selects all conflicting aircraft and produces all possible neighbourhood solutions based on the current solution. Second, if no conflict is detected during the iterations, the algorithm chooses one or more aircraft from the current solution randomly and generates neighbourhood solutions. If any conflict occurs, the algorithm can generate 12 solutions using all possible combinations of three entry points and four airspeed values for a single aircraft. Therefore, the algorithm can produce a different number of neighbourhood solutions in each iteration. The process is illustrated in Fig. 6 for aircraft 2 using the selected initial solution presented in Fig. 5. Aircraft 2 initially enters from point 5 in the second entry area (Fig. 2) with its nominal airspeed as shown in the current solution, S. The algorithm generates 11 different neighborhood solutions, S ’ from S.
Figure 6. Neighbourhood generation technique: the current solution, S and its neighbouring solutions (S’1, S’2…. S’11).
4.5. Termination criteria
The algorithm is designed to create conflict-free trajectories with minimum changes from initial flight conditions in a short time. Therefore, the algorithm is set to terminate if the computation time exceeds 5 minutes or no improvement is found in the fitness function after 10 iterations. These termination parameters are selected to find fast and feasible solutions to assist air traffic controllers.
5.0 COMPUTATIONAL RESULTS
Three different air traffic flow rates were selected as 20, 25 and 30 aircraft per hour for the given airspace (Fig. 2). The airspace has a total of 12 entry points in four entry areas and four exit points. For the experiments, all aircraft were assumed to cruise at 37000 feet (i.e., FL370) eastbound (i.e., aircraft headings are between 00–1800). Aircraft are supposed to fly along direct routes between the entry and exit points of the airspace. Therefore, the airspace has 48 routes and 396 potential conflict points at these route intersections. EA and XP parameters were assigned to each aircraft using uniform probability distribution. Three different traffic mixtures for each traffic flow were selected as 25% NB - 75% WB, 50% NB - 50% WB and 75% NB - 25%WB. The inter-arrival times for each air traffic flow rate were obtained using exponential distribution (i.e. β1 = 180 secs for 20 aircraft/hr, β2 = 144 secs for 25 aircraft/hr, β3 = 120 secs for 30 aircraft/hr, each). In the proposed model, each EA consists of three entry points which are placed 10 NM apart. For the generic airspace configurations, 150 different scenarios were generated for each air traffic flow rate. A computer with a 2.3 GHz Intel Core i7 processor and 16 GB RAM was used in all computations.
5.1. Validation of the heuristic algorithm
To evaluate the performance of the proposed heuristic algorithm, various scenarios were generated for the generic en-route airspace. Twenty test problems were produced for the air traffic flow rates of 20 and 25 aircraft/hour, respectively.
In these test problems, the number of the routes and potential conflict points were limited to 12 and 36, respectively. Optimal results provided by the GAMS/CPLEX solver and results of the heuristic algorithm are presented in Tables 2 and 3. The first three columns in the tables present the number of each scenario, the objective function (z), and the CPU time (t) in seconds for the GAMS/CPLEX solver, respectively. The following columns present the objective functions (z*, z**, z***) and CPU times (t*, t**, t***) for three different runs of the heuristic algorithm. The last three columns show the minimum value of the objective function, the average value of the objective function and the average CPU time. In Table 2, the heuristic algorithm found optimal solutions in 18 scenarios for the air traffic flow rate of 20 aircraft/hr. The average solution time of the heuristic algorithm was approximately 9 seconds while the GAMS/CPLEX solver was approximately 1120 seconds for 20 aircraft. No conflict was detected in scenarios 4 and 13 according to the given parameters. However, the model generation time of the GAMS/CPLEX solver took a considerable amount of time to prove a conflict free aircraft set. Similarly, the heuristic algorithm was able to obtain an optimal solution for 17 scenarios for 25 aircraft/hr. The algorithm found near optimal results for scenarios 9, 10 and 14 which are colored in grey in Table 3. The average solution time of the heuristic algorithm was approximately 12 seconds while the GAMS/CPLEX solver was approximately 1785 seconds for 25 aircraft.
Table 2 Test problem results with 20 aircraft
Table 3 Test problem results with 25 aircraft
Table 4 The average results of A, B, C, z and CPU times
5.2. Results of the proposed heuristic
After the validation, the proposed heuristic algorithm was run for each flow rate and traffic mixture combination implemented in the generic airspace configuration (Fig. 2). In total, 450 scenarios were generated and tested for three different flow rates and three different traffic mixes. The average conflict resolution time (A), the average number of entry point (B) and the average number of airspeed (C) value changes, the average objective function Z and average CPU times are presented in Table 4. The average number of initial conflicts were estimated as 3.7, 5.9 and 8.1 for the traffic flow rates of 20, 25 and 30 aircraft/hr, respectively. The algorithm resolved all these initial conflicts using new entry point and airspeed assignments without any conflict resolution time (w i = 0). Conflict-free trajectories were achieved in less than 46 seconds for all scenarios. The average of entry point changes was calculated as 1.6, 2.5 and 3.3 for 20, 25 and 30 aircraft/hr, respectively. Similarly, the average of airspeed changes was calculated as 0.9, 1.6 and 2.3 for 20, 25 and 30 aircraft/hr. These results indicate that the algorithm handles all conflicts and minimises the total changes in initial entry points and airspeed values. Increasing traffic flow rates, on the other hand, requires more entry point and airspeed changes. The highest objective functions were obtained at 30 aircraft/hr with the traffic mix of 50% WB because the increased aircraft performance differences within the traffic flow leads to greater separation times between aircraft. The results of the airborne delays (AD), fuel consumptions (FC), and flight times (FT) for the baseline and heuristic algorithm are presented in Table 5.
Table 5 The average results of AD, AFC and AFT
The proposed model improved the average fuel consumption by 2.28%, 3.01% and 3.04% for 20, 25 and 30 aircraft, respectively with respect to the baseline scenarios. However, the proposed model resulted in a minor increase of 0.3%, 0.46% and 0.53% in the average flight times for 20, 25 and 30 aircraft, respectively. Likewise, the proposed model resulted in an increase of 1 sec., 1.6 sec. and 2.4 sec. average airborne delay for 20, 25 and 30 aircraft.
6.0 CONCLUSION
An MILP model was developed to handle aircraft conflicts using horizontal resolution manoeuvers in a generic en-route airspace. The model aimed to create conflict free trajectories with minimal changes of the initial entry point and airspeed values. MEP was implemented along with the airspeed reduction technique for CDR. Although the GAMS/CPLEX solver reached optimal solutions for the test problem; it required high computational times, which are not practical for real-time ATC operations. Therefore, a new heuristic algorithm was developed based on neighborhood search in order to obtain optimal or near-optimal solutions for real-time operations. A large number of operational scenarios were implemented for a generic en-route airspace configuration and the proposed algorithm provided conflict-free routes in no more than 46 seconds. As expected, higher air traffic flow rates and increased aircraft traffic mix (i.e. %50 NB and %50 WB) required more entry point and airspeed changes due to the increased traffic complexity. The algorithm also improved the average fuel consumptions by up to approximately 3% with insignificant increases in both average delay and flight time. Considerable fuel savings can be achieved compared to the vectoring manoeuvers in a conventional airspace structure although entry point assignments and airspeed reductions let aircraft fly on relatively longer routes at their optimal cruise airspeed. The algorithm also allows ATCos to resolve conflicts using at most two instructions, such as entry point and airspeed change, at the same time at the airspace entrance. Additionally, the monitoring time of conflicts can be reduced significantly because the algorithm ensures conflict-free trajectories for all aircraft entering into and flying within the airspace. The conventional vectoring manoeuvers, however, require higher monitoring times for conflict resolution and recovery. In addition, sometimes a single vectoring manoeuver is insufficient to resolve predicted conflicts; therefore, the number instructions for ATCos and pilots can be increased significantly as the air traffic flow rates increase. The proposed algorithm provides a good insight for decision support systems, especially for free route airspace operations. Although, the MEP approach is presented for a single airspace in this study, it can be expanded for several neighbouring airspaces. In order to implement this approach, alternative exit points can be introduced in each airspace. Therefore, these alternative exits points will be the new entry points of the consecutive airspace(s). After minor changes, the algorithm can assign entry and exit points as well as airspeed for each aircraft based on air traffic flow information in all airspaces. Furthermore, the stochastic version of the algorithm can be considered in subsequent studies. In addition to this, to test the algorithm with air traffic controllers, real-time simulations can be tested for the selected airspace according to the algorithm results.
