Meta-heuristic algorithm for aircraft pre-tactical conflict resolution with altitude and heading angle change maneuvers

Abstract

Aircraft conflict resolution is of great importance for the safe and efficient management of air traffic. This study proposes a two-step optimization approach for the aircraft conflict resolution problems within the pre-tactical time window in generic free route airspace. Safe separation between aircraft pairs is maintained using either altitude or heading angle change maneuvers in a pre-defined buffer zone within the boundaries of the airspace. The first step of the model aims to minimize the total number of conflicting aircraft and the total fuel consumption together using altitude change maneuvers. A mixed-integer linear programming model is proposed for the first step but, due to the high computational time, a metaheuristic algorithm (simulated annealing) was developed. If the altitude change does not resolve all conflicts in the first step, the proposed model implements heading angle change maneuvers with minimum extra fuel burn in the second step. A nonlinear programming model is presented for the second step. Numerical results show that the proposed approach can resolve all conflicts in less than 4 min for the highest traffic flow rate.

1 Introduction

Air transportation makes a significant contribution to international and domestic economies in many ways, for example, by accelerating economic integration, increasing international trade and mobility, providing tourism support, and by generating more employment opportunities globally. This industry has grown by more than 60% in terms of annual air traffic volume over the last decade. For the next 20 years, global annual air traffic is expected to grow by an average of 4.3% (Scherer 2019). Airspace capacities, however, will be unable to meet this rapid demand in many parts of the world unless air traffic controllers supplied with advanced decision support tools to cope with these air traffic rates. Recent developments enable us to obtain more accurate information about aircraft positions and airspeeds. Therefore, these new tools, along with enhanced air traffic data, allow the detection and resolution of aircraft conflicts in a pre-tactical time window (i.e. up to 2 h prior to the conflict). The purpose of aircraft conflict detection and resolution (CDR) is to create conflict-free trajectories for each aircraft that shares the same airspace. Conflict avoidance can be ensured by applying some basic maneuvers that are heading angle change (HAC), altitude change (AC) and airspeed change (SC). CDR becomes a very critical issue especially for the novel concept of free route airspace (FRA), which allows airlines to plan their routes freely between predefined entry and exit points of the airspace. Although FRA provides efficient and economic use of an airspace, it increases the number of potential conflict points (Antulov-Fantulin et al. 2018). Pre-tactical CDR can handle this traffic complexity efficiently within FRAs.

The problem of aircraft conflict detection and resolution (CDR) has been studied by a number of researchers. Extensive reviews have been presented regarding various CDR approaches by Kuchar and Yang (2000) and Martin-Campo (2010). The mixed-integer programming (MIP) techniques have been widely used in CDR problems. Pallottino et al. (2002) proposed two different mixed-integer linear programming (MILP) models to resolve aircraft conflicts using either HAC or SC maneuvers. Christodoulou and Costoulakis (2004) presented an MILP model that uses both HAC and SC to resolve conflicts for small-scale problems. Vela et al. (2009, 2010) proposed two different MILP models to minimize aircraft fuel consumption using AC-SC and HAC-SC maneuvers, respectively. Rey et al. (2012, 2015) also presented two different models based on SC to minimize the total conflict duration time between aircraft. Alonso-Ayuso et al. (2011) adopted the geometric transformations of Pallottino et al. (2002) for SC and AC methods. Alonso-Ayuso et al. (2012) also introduced a mixed-integer nonlinear programing (MINLP) model which uses SC maneuvers and takes the acceleration rates of aircraft into account. The model aims to minimize acceleration rates of the aircraft during conflict resolution. Later, Alonso-Ayuso et al. (2014) developed an MINLP model using HAC to resolve conflicts and return aircraft to their original flight paths. Cafieri and Durand (2014) proposed another MINLP model with SC for aircraft conflict resolution. Omer (2015) presented a mixed-integer linear programming model which uses both SC and HAC together based on a space discretization technique. Alonso-Ayuso et al. (2016a, b) proposed an MINLP multi-objective optimization model that uses a variable neighborhood search (VNS) algorithm with HAC, SC and AC maneuvers. To present conflict-free paths for aircraft, preemptive goal programming was implemented to the model. To obtain fast calculations for conflict resolution, a sequential MILP model was also presented. The objective function was to minimize the deviation cost from the initial configurations. Alonso-Ayuso et al. (2016a, b) presented MILP model that performs both horizontal and vertical maneuvers using the exact solver MINO. The model implements these maneuvers in lexicographic order similar to the previous work. The model can handle only ten aircraft because of the non-convexity of the problem. Cafieri and Rey (2017) presented a mixed-integer nonlinear programming model that uses SC approach to maximize the largest conflict-free aircraft set. Hong et al. (2017) presented an MINLP model that aimed to provide conflict-free flight operations by altering HAC and SC. The model uses the particle swarm optimization (PSO) technique to resolve conflicts due to the nonlinear constraints. Cecen and Cetek (2019) presented a two-step mathematical model that utilizes the Multi-Entry Point (MEP) approach and vector deflection maneuvers to avoid aircraft conflicts. The model, however, does not include altitude changes. It basically aims to find the best entry point combination and optimal fuel vector maneuvers for the conflicting aircraft. Due to the complexity of the problem, genetic algorithm (GA) and tabu search (TS) were implemented to obtain a feasible result. Vector maneuvers are applied to the aircraft prior to the entrance into the airspace. Aircraft fuel consumption for a given airspeed during the level flight depends on the distance travelled and the propulsive characteristics of the aircraft. Turning maneuvers, on the other hand, lead to extra fuel consumption not only because of the extended flight path but also of the increase in the bank angle, which results in higher load factors. Cecen and Cetek (2020) proposed a mixed-integer linear programming model that integrates the MEP approach with airspeed change maneuver to provide conflict-free en route operations. Due to the complexity of the model, a heuristic algorithm was presented to resolve aircraft conflict.

This study proposes a two-step optimization approach for the aircraft conflict resolution problems within the pre-tactical time window in generic free route airspace. Safe separation between aircraft pairs is maintained using either altitude or heading angle change maneuvers in a pre-defined buffer zone within the boundaries of the airspace. A space discretization technique is used to control the minimum safe separation of aircraft at a limited number of potential conflict points, including entry and exit fixes and route intersections, instead of searching the whole airspace. Cecen and Cetek (2019) previously presented a two-step conflict resolution approach in the horizontal plane for a single flight level using HAC only. The proposed model, however, applies either an AC or a HAC maneuver to resolve conflict at multiple flight levels. The first step of the model aims to minimize the total number of conflicting aircraft and the total fuel consumption together by using AC only. AC maneuvers are convenient for ATCos because they allow conflicts to be resolved with a single instruction and require much lower conflict resolution and conflict monitoring time than HAC maneuvers. Therefore, their use can reduce monitoring time of ATCos significantly and increase the airspace capacity. A mixed-integer linear programming model is proposed for the first step but due to the high computational time, a metaheuristic algorithm (simulated annealing) was developed. If the AC maneuver does not resolve all conflicts in the first step, the proposed model implements HAC maneuver with minimum extra fuel burn in the second step. A nonlinear programming model is presented for the second step. The model allows climb/descent or HAC maneuvers in the buffer zone within the boundaries of the airspace. Each aircraft can perform either a flight level change (i.e., a 2000 ft climb or descent) or an HAC maneuver. The model also ensures safe vertical separation between aircraft during AC maneuvers within the buffer zone.

The paper is organized as follows. In Sect. 2, we provide a general description of the problem for aircraft conflict resolution and free route airspace. In Sect. 3, a mixed-integer linear program based on AC is first proposed. Then, a mixed-integer nonlinear program optimization model for HAC is presented. In Sect. 4, meta-heuristic algorithm is explained in detail. In Sect. 5, the numerical results are presented and some numerical issues are discussed. Conclusions and perspectives for future work are discussed in Sect. 6.

2 Problem statement

Aircraft fly along their trajectories through one or more airspaces with defined boundaries and air traffic service provisions. En-route airspaces have the largest share of the entire air transportation network and these accommodate climb, cruise and descend phases of flights. Area control centers (ACC) are in charge of monitoring and controlling aircraft within the en-route airspaces to ensure safe separation between aircraft and provide orderly and efficient air traffic flow. Airspace boundaries can be defined by geographic coordinates of entry and exit fixes horizontally. Flight levels divide the airspace into parallel horizontal planes separated by 1000 ft vertically up to 29,000 ft (i.e. FL290) above mean sea level (MSL) for nominal operations or up to 41,000 ft (i.e. FL410) above MSL for designed airspaces with reduced vertical separation minima (ICAO Doc 2007). Aircraft flying through the airspace are assigned to a flight level depending on its heading with respect to magnetic north. Aircraft with a heading 0°–179° (eastbound) use odd-numbered flight levels (e.g. FL290, FL310, FL330…) while aircraft with a heading180°–359° (westbound) use even numbered flight levels (e.g. FL300, FL320, FL340…). There are two common en-route airspace structures which are fixed-route and free route airspaces. Fixed-route airspaces consist of a network of predefined waypoints and routes which aircraft should follow. Free route airspaces, on the other hand, allow aircraft to select direct routes between the pre-defined entry/exit fixes. Figure 1 presents generic free-route airspace with a set of entry fixes (EF) (i.e. ef₁, ef₂, …, ef_k), exit fixes (XF) (i.e. xf₁, xf₂, …, xf_f), and flight levels (i.e. FL_s-1, FL_s, FL_s+1).

Fig. 1

Generic FRA configuration

Each aircraft should be separated from others by 1000 ft. vertically and 5 NM horizontally in en-route airspaces with ATC provisions (ICAO 2007). Vertical separation can be ensured via flight level change maneuvers (i.e., climb or descent) within the airspace. In a similar way, horizontal separation can be maintained via heading changes or airspeed adjustments. This study involves flight level and heading change maneuvers. All resolution maneuvers are assumed to be performed within a buffer zone inside the en-route airspace (Fig. 1). The depth of the buffer zone ($\Delta L$) is assumed as 20 NM and this value guarantees the conflict resolution using either AC or HAC maneuvers. All aircraft are assumed to maintain their flight level and airspeed during their flight within the airspace after the resolution. When aircraft fly in the same flight level, two different types of conflicts can occur depending on their route encounter geometries, namely crossing and trailing conflicts (Fig. 2).

Fig. 2

Conflict geometries: a crossing conflict and b trailing conflict

The crossing conflicts can arise in intersecting, diverging or merging routes while the trailing conflicts take place in the same route. To avoid crossing conflicts, the necessary time separation can be calculated between aircraft pairs depending on airspeeds and the route crossing angle that is given by Carlier et al. (2003):

$${\text{NT}}_{{ii^{\prime}}} = \frac{{D_{\min } }}{{V_{i} V_{{i^{\prime}}} \left| {\sin \theta_{{ii^{\prime}}} } \right|}}\sqrt {\left( {V_{i} } \right)^{2} + \left( {V_{{i^{\prime}}} } \right)^{2} - 2V_{i} V_{{i^{\prime}}} \cos \left( {\theta_{{ii^{\prime}}} } \right)} .$$

(1)

In Eq. (1) D_min is the minimum horizontal separation distance. $V_{i}$ and $V_{{i^{\prime}}}$ are the airspeeds of the leading and trailing aircraft, respectively, and $\theta_{{ii^{\prime}}}$ is the route crossing angle. To ensure safe separation, either aircraft should climb or descend to another flight level and/or it should be delayed by ${\text{NT}}_{{ii^{\prime}}}$ using a vector maneuver. In the case of trailing conflicts, no overtaking is allowed. Airspeeds V_i and V_i′ depend on the aircraft performance category (APC) at the given flight level.

The required time separation of each possible conflict point is estimated and put to the model using Eq. (1). The model controls any possible crossing conflict between aircraft using different entry points but the same exit point (${\text{treq}}_{{r_{{i_{1} }} ,r_{{i_{2} }} ,t_{{i_{1} }} ,t_{{i_{2} }} ,e_{{i_{1} }} }}$), aircraft using the same entry point but different exit points (${\text{breq}}_{{e_{{i_{1} }} ,e_{{i_{2} }} ,t_{{i_{1} ,}} t_{{i_{2} }} ,r_{{i_{1} }} }}$), aircraft using different entry and exit points (${\text{sreq}}_{{t_{{i_{1} }} ,t_{{i_{2} }} ,o_{{i_{1} }} }}$) and aircraft using same entry and exit points (${\text{freq}}_{{t_{{i_{1} }} ,t_{{i_{2} }} }}$).

In this study, aircraft were classified into two different performance categories, narrow-body jet (NB) and wide-body jet (WB). Flight level changes were treated as a steady linear climb or descent maneuvers of the aircraft. The fuel consumption due to the flight level change depends on three parameters which are APC, initial flight level and assigned flight level. These parameters were calculated using the Base of Aircraft Data (BADA 2013). The following assumptions were imposed on the model:

• (1) All aircraft travel eastbound at FL290–FL330.

• (2) Eastbound traffic is separated horizontally from westbound traffic at FL300 and FL320 during altitude changes within the buffer zone.

• (3) All operations take place under standard atmospheric (ISA) conditions at the given flight levels of the airspace.

• (4) Wind speed and acceleration are zero.

• (5) Weights of all aircraft remain constant during their flight along the airspace.

• (6) Heading change maneuvers are performed at a constant bank angle.

3 Mathematical model

Figure 3 presents the general methodology of the proposed two-step solution approach. To evaluate the proposed model, an initial conflict number was calculated. The estimated time of arrivals (ETA), APC, EF and XF of each flight were generated randomly as inputs for both cases. The proposed approach also obtains the total and individual number of conflicts resolved by AC and SC maneuvers as well as new flight level assignments.

Fig. 3

Flow chart of the entire mathematical model

3.1 First step: altitude change maneuvers

A MILP model is presented to minimize the total number of conflicting aircraft and the total aircraft fuel consumption for the first step. The main aim is to generate a conflict-free trajectory for each aircraft using only altitude change maneuvers. It is clear that our model is a multi-objective optimization model. To transform the multi-objective optimization model into a single objective model, the linear scalarization method was implemented. Since aircraft conflict resolution is more important than optimizing fuel consumption, we selected two different coefficients $\gamma_{1}$ and $\gamma_{2}$ for the objectives that are 0.96 and 0.04, respectively. Therefore, the model gives priority to provide safe separation and then searches for the optimal fuel AC maneuvers.

Sets:

$I = \left\{ {1, \ldots ,\alpha } \right\}$ set of aircraft in the sector $i,i_{1} ,i_{2} \in I$

$K = \left\{ {1, \ldots ,\beta } \right\}$ set of entry points $k,k_{1} ,k_{2} \in K$

$V = \left\{ {1, \ldots ,} \right\}$ set of aircraft performance categories $v,v_{1} ,v_{2} \in V$

$N = \left\{ {1, \ldots ,} \right\}$ set of crossing conflict points $n \in N$

$F = \left\{ {1, \ldots ,\delta } \right\}$ set of exit points $f,f_{1} ,f_{2} \in F$

$S = \left\{ {1, \ldots ,} \right\}$ set of flight levels $s,s_{1} ,s_{2} \in S.$

Parameters:

$\alpha$: number of aircraft.

$\beta$: number of entry points.

$\mu$: number of aircraft performance categories.

$\sigma$: number of crossing conflict points.

$\delta$: number of exit points.

$\lambda$: number of flight levels.

$M_{1}$, $M_{2}$, $M_{3}$: a large enough positive number

$$M_{1} = \left( {g_{{i_{2} }} - g_{{i_{1} }} } \right) \cdot 2$$

$$M_{2} = \left( {\left( {g_{{i_{2} }} + \frac{{{\text{TD}}_{{r_{{i_{2} }} e_{{i_{2} }} }} }}{{h_{{t_{{i_{2} }} }} }}} \right) - \left( {g_{{i_{1} }} + \frac{{{\text{TD}}_{{r_{{i_{1} }} e_{{i_{1} }} }} }}{{h_{{t_{{i_{1} }} }} }}} \right)} \right) \cdot 2$$

$$M_{3} = \left( {\left( {g_{{i_{2} }} + \frac{{d_{{r_{{i_{2} }} o_{{i_{2} }} }} }}{{h_{{t_{{i_{2} }} }} }}} \right) - \left( {g_{{i_{1} }} + \frac{{d_{{r_{1} o_{{i_{1} }} }} }}{{h_{{t_{{i_{1} }} }} }}} \right)} \right) \cdot 2,$$

where i₁ and i₂ are the first and the last aircrafts entering the airspace, respectively.

$g_{i}$: planning airspace entry time of aircraft i.

$t_{i}$: performance category of aircraft i.

$r_{i}$: entry point of the sector of aircraft i.

$e_{i}$: exit point of the sector of aircraft i.

$bg_{i}$: initial flight level of each aircraft i.

$h_{{t_{i} }}$: velocity of performance category $t_{i}$.

$d_{{r_{i} ,o_{i} }}$: distance between entry point $r_{i}$ and crossing conflict point $o_{i}$.

${\text{TD}}_{{r_{i} ,e_{i} }}$: distance between entry point $r_{i}$ and exit point $e_{i}$.

${\text{freq}}_{{t_{{i_{1} }} ,t_{{i_{2} }} }}$: separation time on trailing route conflicts between aircraft performance category $t_{{i_{1} }}$ and $t_{{i_{2} }}$.

${\text{sreq}}_{{t_{{i_{1} }} ,t_{{i_{2} }} ,o_{{i_{1} }} }}$: separation time on crossing conflict point $o_{{i_{1} }}$ between aircraft performance category $t_{{i_{1} }}$ and $t_{2}$.

${\text{treq}}_{{r_{{i_{1} }} ,r_{{i_{2} }} ,t_{{i_{1} }} ,t_{{i_{2} }} ,e_{{i_{1} }} }}$: separation time for exit point $e_{{i_{1} }}$ between aircraft pair using entry point $r_{{i_{1} }}$ and $r_{{i_{2} }}$ with performance category $t_{{i_{1} }}$ and $t_{{i_{2} }}$.

${\text{breq}}_{{e_{{i_{1} }} ,e_{{i_{2} }} ,t_{{i_{1} ,}} t_{{i_{2} }} ,r_{{i_{1} }} }}$: separation time for entry point $r_{{i_{1} }}$ between aircraft pair using exit point $e_{{i_{1} }}$ and $e_{{i_{2} }}$ with performance category $t_{{i_{1} ,}}$ and $t_{{i_{2} ,}}$.

$o_{i}$: conflict point of aircraft i.

$\varepsilon :$ minimal non-zero value of $w_{i}$.

${\text{FLCC}}_{{t_{i} ,s}}$: cruise flight fuel consumption per nautical mile for aircraft performance category $t_{i}$ at flight level $s$.

${\text{FLCT}}_{{t_{i} ,bg_{i} ,s}}$: fuel consumption due to flight level change for aircraft performance category $t_{i}$ from flight level $bg_{i}$ to $s$.

CT1: the time separation for an aircraft pair if they are assigned the same altitude from different initial flight levels within the buffer zone.

CT2: the time separation for an aircraft pair with crossing flight paths in the vertical plane during their AC maneuver within the buffer zone.

Decision variables:

$q_{i}$: actual entry time of the sector for aircraft i.

$w_{i}$: delay induced by conflict resolution for aircraft i.

$p_{i}$: fly over time of crossing conflict point for aircraft i.

$c_{i}$: fly over time of exit point for aircraft i.

$va_{i}$: 0–1 variable that takes a value of 1 if $w_{i}$ greater than 0; otherwise, it is zero.

${\text{AC}}_{i}$: 0–1 variable that takes a value of 1 if any flight level change occurs; otherwise, it is zero.

$b1_{{i_{1} ,i_{2} }}$: 0–1 variable that takes a value of 1 if aircraft $i_{2}$ enters and exits the sector before aircraft $i_{1}$; otherwise, it is zero.

$b2_{{i_{1} ,i_{2} }}$: 0–1 variable that takes a value of 1 if aircraft $i_{2}$ exits the sector before aircraft $i_{1}$; otherwise, it is zero.

$b3_{{i_{1} ,i_{2} }}$: 0–1 variable that takes a value of 1 if aircraft $i_{2}$ enters the sector before aircraft $i_{1}$; otherwise, it is zero.

$b4_{{i_{1} ,i_{2} }}$: 0–1 variable that takes a value of 1 if aircraft $i_{2}$ flies over crossing conflict point before aircraft $i_{1}$; otherwise, it is zero.

$x_{i,s}$: 0–1 variable that takes a value of 1 if aircraft i is assigned to flight level s; otherwise, it is zero.

${\text{sp}}_{i} ,{\text{sn}}_{i}$ the number of increases or decreases of flight level from the initial flight level for aircraft i.

The objective function and constraints used in the first step are as follows.

$$\min \;\gamma_{1} \mathop \sum \limits_{i \in I} va_{i} + \gamma_{2} \mathop \sum \limits_{i \in I} \mathop \sum \limits_{s \in S} x_{i,s} ({\text{FLCC}}_{{t_{i} ,s}} \cdot {\text{TD}}_{{r_{i} ,e_{i} }} + ({\text{FLCT}}_{{t_{i} ,bg_{i} ,s}} )).$$

(2)

Subject to

$$\mathop \sum \limits_{s \in S} x_{i,s} = 1\quad \forall i \in I$$

(3)

$$q_{i} = g_{i} + w_{i} \quad \forall i \in I$$

(4)

$$p_{i} = q_{i} + \frac{{d_{{r_{i} ,o_{i} }} }}{{h_{{t_{i} }} }}\quad \forall i \in I$$

(5)

$$c_{i} = q_{i} + \frac{{{\text{TD}}_{{r_{i} ,e_{i} }} }}{{h_{{t_{i} }} }}\quad \forall i \in I$$

(6)

$$q_{{i_{2} }} - q_{{i_{1} }} \ge {\text{freq}}_{{t_{{i_{1} }} ,t_{{i_{2} }} }} - \left( {2 - x_{{i_{1} ,s}} - x_{{i_{2} ,s}} } \right)M_{1} - \left( {b1_{{i_{1} ,i_{2} }} } \right)M_{1} \quad \forall i_{1} ,i_{2} \in I, s \in S |i_{1} \ne i_{2} , e_{{i_{1} }} = e_{{i_{2} }} , r_{{i_{1} }} = r_{{i_{2} }}$$

(7)

$$q_{{i_{1} }} - q_{{i_{2} }} \ge {\text{freq}}_{{t_{{i_{2} }} ,t_{{i_{1} }} }} - \left( {2 - x_{{i_{1} ,s}} - x_{{i_{2} ,s}} } \right)M_{1} - \left( {1 - b1_{{i_{1} ,i_{2} }} } \right)M_{1} \quad \forall i_{1} ,i_{2} \in I, s \in S |i_{1} \ne i_{2} ,e_{{i_{1} }} = e_{{i_{2} }} , r_{{i_{1} }} = r_{{i_{2} }}$$

(8)

$$c_{{i_{2} }} - c_{{i_{1} }} \ge {\text{freq}}_{{t_{{i_{1} }} ,t_{{i_{2} }} }} - \left( {2 - x_{{i_{1} ,s}} - x_{{i_{2} ,s}} } \right)M_{2} - \left( {b1_{{i_{1} ,i_{2} }} } \right)M_{2} \quad \forall i_{1} ,i_{2} \in I, s \in S |i_{1} \ne i_{2} , e_{{i_{1} }} = e_{{i_{2} }} , r_{{i_{1} }} = r_{{i_{2} }}$$

(9)

$$c_{{i_{1} }} - c_{{i_{2} }} \ge {\text{freq}}_{{t_{{i_{2} }} ,t_{{i_{1} }} }} - \left( {2 - x_{{i_{1} ,s}} - x_{{i_{2} ,s}} } \right)M_{2} - \left( {1 - b1_{{i_{1} ,i_{2} }} } \right)M_{2} \quad \forall i_{1} ,i_{2} \in I, s \in S|i_{1} \ne i_{2} , e_{{i_{1} }} = e_{{i_{2} }} , r_{{i_{1} }} = r_{{i_{2} }}$$

(10)

$$q_{{i_{2} }} - q_{{i_{1} }} \ge {\text{breq}}_{{e_{{i_{1} }} ,e_{{i_{2} }} ,t_{{i_{1} ,}} t_{{i_{2} }} ,r_{{i_{1} }} }} - \left( {2 - x_{{i_{1} ,s}} - x_{{i_{2} ,s}} } \right)M_{1} - \left( {b2_{{i_{1} ,i_{2} }} } \right)M_{1} \quad \forall i_{1} ,i_{2} \in I, s \in S|i_{1} \ne i_{2} , e_{{i_{1} }} \ne e_{{i_{2} }} ,r_{{i_{1} }} = r_{{i_{2} }}$$

(11)

$$q_{{i_{1} }} - q_{{i_{2} }} \ge {\text{breq}}_{{e_{{i_{2} }} ,e_{{i_{1} }} ,t_{{i_{1} }} ,t_{{i_{2} }} ,r_{{i_{1} }} }} - \left( {2 - x_{{i_{1} s}} - x_{{i_{2} s}} } \right)M_{1} - \left( {1 - b2_{{i_{1} i_{2} }} } \right)M_{1} \quad \forall i_{1} ,i_{2} \in I, s \in S|i_{1} \ne i_{2} , e_{{i_{1} }} \ne e_{{i_{2} }} ,r_{{i_{1} }} = r_{{i_{2} }}$$

(12)

$$c_{{i_{2} }} - c_{{i_{1} }} \ge {\text{treq}}_{{r_{{i_{1} }} ,r_{{i_{2} }} ,t_{{i_{1} }} ,t_{{i_{2} }} ,e_{{i_{1} }} }} - \left( {2 - x_{{i_{1} ,s}} - x_{{i_{2} ,s}} } \right)M_{2} - \left( {b3_{{i_{1} ,i_{2} }} } \right)M_{2} \quad \forall i_{1} ,i_{2} \in I, s \in S |i_{1} \ne i_{2} , e_{{i_{1} }} = e_{{i_{2} }} ,r_{{i_{1} }} \ne r_{{i_{2} }}$$

(13)

$$c_{{i_{1} }} - c_{{i_{2} }} \ge {\text{treq}}_{{r_{{i_{2} }} ,r_{{i_{1} }} ,t_{{i_{1} }} ,t_{{i_{2} }} ,e_{{i_{1} }} }} - \left( {2 - x_{{i_{1} s}} - x_{{i_{2} s}} } \right)M_{2} - \left( {1 - b3_{{i_{1} i_{2} }} } \right)M_{2} \quad \forall i_{1} ,i_{2} \in I, s \in S|i_{1} \ne i_{2} , e_{{i_{1} }} = e_{{i_{2} }} ,r_{{i_{1} }} \ne r_{{i_{2} }}$$

(14)

$$p_{{i_{2} }} - p_{{i_{1} }} \ge {\text{sreq}}_{{t_{{i_{1} }} ,t_{{i_{2} }} ,o_{{i_{1} }} }} - \left( {2 - x_{{i_{1} ,s}} - x_{{i_{2} ,s}} } \right)M_{3} - \left( {b4_{{i_{1} ,i_{2} }} } \right)M_{3} \quad \forall i_{1} ,i_{2} \in I, s \in S| i_{1} \ne i_{2} , e_{{i_{1} }} \ne e_{{i_{2} }} , r_{{i_{1} }} \ne r_{{i_{2} }} , o_{{i_{1} }} = o_{{i_{2} }}$$

(15)

$$p_{{i_{1} }} - p_{{i_{2} }} \ge {\text{sreq}}_{{t_{{i_{2} }} ,t_{{i_{1} }} ,o_{{i_{1} }} }} - \left( {2 - x_{{i_{1} ,s}} - x_{{i_{2} ,s}} } \right)M_{3} - \left( {1 - b4_{{i_{1} ,i_{2} }} } \right)M_{3} \quad \forall i_{1} ,i_{2} \in I, s \in S | i_{1} \ne i_{2} , e_{{i_{1} }} \ne e_{{i_{2} }} , r_{{i_{1} }} \ne r_{{i_{2} }} , o_{{i_{1} }} = o_{{i_{2} }}$$

(16)

$$\mathop \sum \limits_{s \in S} x_{i,s} \cdot s - {\text{sp}}_{i} + {\text{sn}}_{i} = bg_{i} \quad \forall i \in I$$

(17)

$${\text{sp}}_{i} + {\text{sn}}_{i} \le 1\quad \forall i \in I$$

(18)

$${\text{sp}}_{i} + {\text{sn}}_{i} = {\text{AC}}_{i} \quad \forall i \in I$$

(19)

$$va_{i} M1 \ge w_{i} \quad \forall i \in I$$

(20)

$$\varepsilon \cdot va_{i} \le w_{i} \quad \forall i \in I$$

(21)

$${\text{AC}}_{i} + va_{i} \le 1\quad \forall i$$

(22)

$$g_{{i_{2} }} - g_{{i_{1} }} \ge {\text{CT}}1 - \left( {2 - x_{{i_{1} ,s}} - x_{{i_{2} ,s}} } \right)M_{1} - (b5_{{i_{1} ,i_{2} }} )M_{1} \quad \forall i_{1} ,i_{2} \in I, s \in S\left| {i_{1} \ne i_{2} , r_{{i_{1} }} = r_{{i_{2} }} ,bg_{{i_{1} }} \ne bg_{{i_{2} }} } \right.$$

(23)

$$g_{{i_{1} }} - g_{{i_{2} }} \ge {\text{CT}}1 - \left( {2 - x_{{i_{1} ,s}} - x_{{i_{2} ,s}} } \right)M_{1} - \left( {1 - b5_{{i_{1} ,i_{2} }} } \right)M_{1} \quad \forall i_{1} ,i_{2} \in I, s \in S\left| {i_{1} \ne i_{2} , r_{{i_{1} }} = r_{{i_{2} }} ,bg_{{i_{1} }} \ne bg_{{i_{2} }} } \right.$$

(24)

$$g_{{i_{2} }} - g_{{i_{1} }} \ge {\text{CT}}2 - \left( {4 - {\text{sp}}_{{i_{1} }} - {\text{sn}}_{{i_{2} }} - x_{{i_{1} s_{1} }} - x_{{i_{2,} s_{2} }} } \right)M_{1} - (b6_{{i_{1,} i_{2} }} )M_{1}$$

$$\forall i_{1} ,i_{2} \in I,s_{1} ,s_{2} \in S\left| {i_{1} \ne i_{2} , r_{{i_{1} }} = r_{{i_{2} }} ,bg_{{i_{1} }} \ne bg_{{i_{2} }} , s_{1} \ne s_{2} } \right.$$

(25)

$$g_{{i_{1} }} - g_{{i_{2} }} \ge {\text{CT}}2 - \left( {4 - {\text{sp}}_{{i_{1} }} - {\text{sn}}_{{i_{2} }} - x_{{i_{1} s_{1} }} - x_{{i_{2} ,s_{2} }} } \right)M_{1} - \left( {1 - b6_{{i_{1} ,i_{2} }} } \right)M_{1}$$

$$\forall i_{1} ,i_{2} \in I,s_{1} ,s_{2} \in S\left| {i_{1} \ne i_{2} , r_{{i_{1} }} = r_{{i_{2} }} ,bg_{i1} \ne bg_{i2} ,s_{1} \ne s_{2} } \right.$$

(26)

$$q_{i} \ge 0\quad \forall i \in I$$

(27)

$$w_{i} \ge 0\quad \forall i \in I$$

(28)

$$p_{i} \ge 0\quad \forall i \in I$$

(29)

$$c_{i} \ge 0\quad \forall i \in I$$

(30)

$${\text{sp}}_{i} ,{\text{sn}}_{i} \ge 0\quad \forall i \in I$$

(31)

$$b1_{{i_{1} ,i_{2} }} , b2_{{i_{1} ,i_{2} }} , b3_{{i_{1} ,i_{2} }} , b4_{{i_{1,} i_{2} }} , b5_{{i_{1} ,i_{2} }} ,b6_{{i_{1} i_{2} }} ,va_{i} , {\text{AC}}_{i} \in \left\{ {0,1} \right\}\quad \forall i_{1} ,i_{2} \in I$$

(32)

$$x_{i,s} \in \left\{ {0,1} \right\}\quad \forall i \in I,s \in S.$$

(33)

Objective function (2) is to minimize the total conflicting aircraft number and fuel consumption together. Constraint set (3) ensures every aircraft is assigned to one flight level. Constraint sets (4–6) calculate the aircraft fly overtimes at the entry fix, crossing conflict point and exit fix of the airspace, respectively. Airspeed values are assumed constant for each APC for the selected flight levels, therefore, these fly overtimes are altitude independent. In addition, constraint set (4) calculates the conflict resolution time for each aircraft. Constraint sets (7–9) and (10) maintain the separation time between aircraft pairs on trailing route configurations at the same flight level. Constraint sets (11, 12) maintain the separation time between aircraft pairs at the entry fix if the aircraft pairs use the same entry fix and different exit fixes at the same flight level. Constraint sets (13) and (14) maintain the separation time between aircraft pairs at the exit fix if the aircraft pairs use different entry fixes and the same exit fix at the same flight level. Constraint sets (15, 16) maintain the separation time between aircraft pairs at the path crossing point if the aircraft pairs use different entry and exit fixes at the same flight level. Constraint set (17) calculates the altitude difference between the initial flight level and new flight level for each aircraft. Constraint set (18) does not allow any aircraft to climb and descend at the same time. Constraint set (19) calculates whether any flight level change occurs or not for each aircraft. Constraint sets (20, 21) are relationship constraints between decision variables w_i and va_i. Constraint set (22) ensures that each aircraft can perform either the altitude change or vector maneuver. Constraint sets (23–26) prevent any conflicts within the buffer zone due to AC changes. While the constraints (23, 24) control the time separation between aircraft assigned to the same flight level from different initial altitudes, constraints (25, 26) control the time separation between aircraft assigned different flight level from the different initial altitudes. Therefore, we avoid any violation in vertical and horizontal separation minima within the buffer zone. Constraint (27–33) are sign constraints.

3.2 Second step: vector maneuver model

Flight level assignment is capable of resolving many potential conflicts without requiring any extra resolution maneuvers. In case of the calculated conflict resolution time ($w_{i}$) being greater than zero, the vector (HAC) maneuvers are applied to the aircraft instead of the AC maneuver within the buffer zone. Certainly, there are an infinite number of vector deflection maneuvers which can resolve the conflict. In this step, the model searches vector deflection resolutions with minimal fuel consumption per aircraft under the given constraints described in Sect. 2. In Fig. 4, the vector maneuver consists of steady coordinated turns with a constant bank angle and steady straight flights with zero bank angle in the horizontal plane (Cecen and Cetek 2019). Besides, the deflection angle ψ_i and maneuver distance, l_i are used as decision variables. Other variables, such as the turning radius (tr_i), distance traveled along the arc (a_i), projected arc distance on the undeflected route (b_i) and deflected straight route (l_di), are calculated based on these decision variables which are limited in the model with upper and lower values due to operational constraints.

Fig. 4

Vector maneuver representation

The second step is as follows:

Sets:

I set of aircraft $i \in I$.

Parameters:

$tr_{i}$: turn radius of aircraft i.

$dx_{i}$: extra distance due to conflict resolution time i.

$y_{i,0}$: fuel consumption value with no bank angle for aircraft i.

$y_{i,1}$: fuel consumption value with $25^{\circ}$ bank angle for aircraft i.

Decision variables:

$\psi_{i}$: deflection angle of aircraft i.

$l_{i}$: maneuver distance of aircraft i.

$a_{i}$: arc distance travelled by aircraft i during turning maneuver.

$b_{i}$: total distance travelled by aircraft i projected on the undeflected route during turning maneuver.

$ld_{i}$: distance travelled by aircraft i along the deflected route with no bank.

Objective:

$$\min \mathop \sum \limits_{i} y_{i,1} \cdot 4a_{i} + y_{i,0} \cdot 2ld_{i} - y_{i,0} \cdot l_{i} .$$

(34)

Subject to

$$a_{i} = {\text{tr}}_{i} \psi_{i} \quad \forall i \in I$$

(35)

$$ld_{i} = \frac{{l_{i} - b_{i} }}{{2 \cdot \cos \left( {\psi_{i} } \right)}}\quad \forall i \in I$$

(36)

$$b_{i} = {\text{tr}}_{i} \cdot \sin \left( {\psi_{i} } \right)\quad \forall i \in I$$

(37)

$$4a_{i} + 2ld_{i} - l_{i} - {\text{d}}x_{i} = 0\quad \forall i \in I$$

(38)

$$4b_{i} \le l_{i} \quad \forall i \in I$$

(39)

$$0 \le \psi_{i} \le \frac{\pi }{2}\quad \forall i \in I$$

(40)

$$l_{i} \le 20 \quad \forall i \in I$$

(41)

$$\psi_{i} ,l_{i} ,a_{i} ,b_{i} ,ld_{i} \ge 0 \;\forall i \quad \forall i \in I.$$

(42)

The objective function (34) is to minimize the total extra fuel consumption due to vector maneuvers. Constraint sets (35–37) calculate the distance traveled along the arc ($a_{i}$), deflected straight route ($l_{di}$) and projected arc distance ($b_{i}$) on the undeflected route, respectively. Constraint set (38) guarantees that the distance traveled during the vector deflection maneuver satisfies the required airborne delay. Constraint set (39) ensures that the sum of arc distances projected on the undeflected route cannot be longer than the vector maneuver distance. While Constraint sets (40, 41) limit the upper and lower bounds of the deflection angle and maneuver distance. Constraint set (42) is the sign constraint set.

4 Simulated annealing

The presented model consists of a flight level assignment and vector deflection model. The first step of the problem is implemented into complex airspace configurations and, therefore, it is difficult to get an optimal solution in a reasonable time period. Thus, the SA algorithm is applied to solve the first step of the problem. In the second step, the vector deflection model is proposed to provide a necessary airborne delay for aircraft to avoid conflicts. SA is a probabilistic metaheuristic that uses a local search algorithm for complex problems. It starts by searching the solution space with an initial solution. It generates a neighborhood solution S′ from the current solution S. If S′ shows a better performance than S, S′ is chosen as the current solution. On the other hand, if S′ demonstrates worse performance than the current solution, the current solution is determined by using the probability:

$$P = {\text{e}}^{{{\raise0.7ex\hbox{${ - \Delta }$} \!\mathord{\left/ {\vphantom {{ - \Delta } T}}\right.\kern-\nulldelimiterspace} \!\lower0.7ex\hbox{$T$}}}} .$$

(43)

A real random number is generated for the selection and if the probability is higher than this random value, S′ becomes the new current solution. In Eq. (43), $\Delta$ is the difference between the fitness function values of S′ and S such that $\Delta = f\left( S \right) - f\left( {S^{\prime}} \right)$, and T is the temperature. Each iteration temperature is calculated using the following formula:

$$T_{i + 1} = \beta T_{i} .$$

(44)

In Eq. (44), $\beta$ is the cooling schedule rate and i is the iteration number. The temperature decreases gradually, therefore it allows the worse solution to be selected in the early iterations. When the temperature approaches zero, the probability of selecting the worse solution decreases significantly. Figure 5 demonstrates the neighborhood generation process. Flight level 1, 2 and 3 indicate the 29,000, 31,000 and 33,000 feet, respectively.

Fig. 5

Examples of generating a neighborhood solution in SA

In Fig. 5, aircraft 2 is selected to create a neighborhood solution. The initial flight level of aircraft 2 is 2. The algorithm can assign aircraft 2 to either flight level 1 or flight level 3 because our model allows a single AC maneuver in the airspace. To create a feasible neighborhood solution, our model uses the initial flight level information to avoid an infeasible solution. Furthermore, if any aircraft’s initial flight level is 3, the algorithm can assign this aircraft to either flight level 2 or 3.

5 Computational results

The flight level assignment model was formulated using MILP and ran in GAMS/CPLEX solver for a set of four different air traffic flow rates (i.e. 45, 60, 75 and 90 aircraft per hour). For each air traffic flow rate, ten test-scenarios were generated randomly including ETA, FL, APC, EF and XF. ETAs were generated using exponential distribution while uniform distribution was applied to the other input parameters. Besides, $\varepsilon$ value, the minimal $w_{i}$, was selected as 0.0001 in this study. All scenarios were implemented for a 180 nm² en-route airspace consisting of three flight levels (i.e. FL290, FL310 and FL330) with four entry and exit fixes (Fig. 1). Although the solver obtained global optimal results for all traffic rates, CPU times were very high. Therefore, the SA metaheuristic was applied to the flight level assignment problem in the first step. The parameters used in the metaheuristics presented in Table 1 were determined experimentally. A computer with 2.3 GHz Intel Core i7 processor and 16 GB RAM was used in all computations. MATLAB program was used for the metaheuristic algorithm.

Table 1 The parameters of SA

5.1 Step 1: Flight level assignment model

The initial total conflict number (ICN) (count), the value of the objective function (z), the number of conflicts resolved by HAC maneuver (count), AC maneuver (count), total fuel consumption (fuel) (tons) and CPU time (s) found by GAMS/CPLEX is given in the Tables 2, 3, 4 and 5. Also, SA was run three times for all test problems and the minimum and average values of z, HAC, AC, fuel, and CPU times are presented in Tables 2, 3, 4 and 5.

Table 2 Scenario results using GAMS/CPLEX and SA for 45 aircraft per hour

Table 3 Scenario results using GAMS/CPLEX and SA for 60 aircraft per hour

Table 4 Scenario results using GAMS/CPLEX and SA for 75 aircraft per hour

Table 5 Scenario results using GAMS/CPLEX and SA for 90 aircraft per hour

SA was able to find an optimal objective function in 9, 8, 8 and 6 scenarios for traffic flow rates of 45, 60, 75 and 90 aircraft, respectively. The average number of HAC increases when the traffic flow rates rise. The increased rates of HAC are 100%, 125% and 177.8% from 45 to 60 aircraft, from 60 to 75 aircraft and from 75 to 90 aircraft, respectively. Similarly, the increased rates of AC are 52.6%, 41.3% and 32.9% from 45 to 60 aircraft, from 60 to 75 aircraft and from 75 to 90 aircraft. These results demonstrate that the algorithm uses more altitude changes in lower-traffic flow rates. The proposed model can obtain near-optimal results in less than 4 min for all traffic flow rates. If the number of aircraft decreases, the CPU times also decline sharply. Furthermore, the proposed algorithm can find also very close results in terms of fuel consumption values. This situation shows that our algorithm can provide effective solutions in a short time.

5.2 Step 2: Extra fuel consumption due to vector maneuvers

Extra fuel consumption due to vector deflections was found by GAMS/CONOPT solver in the second step. The nonlinear fuel model uses the individual airborne conflict resolution time found by SA as input and searches for vector maneuvers which generate minimal extra fuel consumption for each aircraft. Table 6 presents the total extra fuel consumption based on airborne delays found by SA that are 122.3, 302.1, 781.7 and 1992 kg of fuel for 45, 60, 75 and 90 aircraft per hour, respectively.

Table 6 Fuel consumption (kg) caused by vector (HAC) maneuvers

6 Conclusion

The proposed two-step approach first performs a conflict resolution with a minimum total number of conflicts via flight level assignment using an SA algorithm and vector maneuvers in a free route airspace. The feasible results in all steps were calculated in a reasonable time for complex route structures. SA was able to obtain a lot of global optimal solutions provided by GAMS/CPLEX solver for 45, 60, 75 and 90 aircraft per hour. Furthermore, the proposed model provided a significant decrease in the total number of conflicts with respect to the total initial conflict number. The vector maneuver model also proposed optimal fuel avoidance trajectories for conflicting aircraft. The proposed approach provides a basis for a decision support system that can be used to regulate air traffic flow and ensure conflict-free trajectories in free route airspaces. In future studies, the performance of this approach can be tested and evaluated using real-time simulations for existing en-route airspaces.