Coordinated Sequencing of Traffic on Multiple En-Route Constraint Points

Abstract

Air transportation traffic is progressively increasing over the years and dealing with it is an essential task to guarantee fluid flights in the future. Several works already indexed multiple aspects of aviation, among them, the E-MAN system. It introduced the sequencing of arriving traffic, starting from early stages of the En-route phase. This change facilitated the work for the approach controllers but also increased the workload of the En-route controllers. To handle that workload, controllers are now assisted by tools that consider the new constraints introduced by the arrival management system and propose advisories. From that same perspective, our project focuses on an algorithm for a helper tool that will combine both aspects of traffic sequencing in the En-route phase and conflict resolution. With this novel approach, we automatically generate near-to- optimal flight decisions, given that we can modify the speed and the flight level to respect the sequencing constraints and cut down potential conflicts. We categorize the problem as a mathematical optimization case. Thus, we describe a detailed mathematical model which covers all the aspects of the problem. This model gives a basis for the implementation of the flight optimizer. Later, we propose a solution based on a sliding window simulated annealing algorithm which reduces the complexity and takes into account uncertainties. Finally, we successfully test an implementation of the solution with real-life traffic data. It corresponds to flights within France going towards Paris CDG airport over a period of 24 h. The results demonstrate a total conflicts resolution with satisfying compliance with sequencing constraints.

1 Introduction

The air traffic has been increasing lately. In its Global Market Forecast (GMF) [1], Airbus has predicted that the global air traffic will encounter an annual growth of 4.4% for the next coming 20 years. With that increase of traffic, some major airports will now rely on arrival management systems such as the Extended-Arrival MANager (E-AMAN [6]) system to help them manage their flow of traffic and generate efficient flights sequencing. However, most of the workload is now transferred to the En-route controllers since they will have to deal with occurring conflicts and also try to respect new constraints imposed by the E-AMAN to flights. In En-route, the airspace is characterized by several route flows crossing into potential conflict points. To avoid those conflicts, some separation constraints are defined for the flights and controllers need to make sure they are respected by using classic methods like vectoring, speed controlling or flight level changes. Each decision applied to an aircraft can have an impact on surrounding flights. This research aims to develop an algorithm that will assist the controllers. Based on the traffic flows analysis, this algorithm will provide near optimum flight decisions in order to remove conflicts at the crossing points. From the controller’s side, the main objective is to reduce the workload and minimize the frequency occupation. This will be done by automatically eliminating conflicts due to lack of separation at crossing points and route links. It also implies reducing the number of flight level changes and simplifying the instructions given to pilots. Another objective is to integrate our tool with an E-AMAN system by generating decisions compatible with E-AMAN constraints. Finally, from the airlines point of view, we will need to take into consideration the preferred flight profile by generating decisions not far from that profile. The first part of the paper introduces some previous related works linked to arrival manager optimization in a wide sense. The second part presents the associated mathematical model. The meta-heuristic (simulated annealing) used for solving the underlying optimization problem is presented in the third part. Finally, the fourth part presents the results given by the algorithm on a real case at Paris Chales De Gaulle (CDG, airport code: LFPG).

2 State of the Art

This section presents the concepts and previous works related to our problem. It focuses on points around air traffic sequencing, conflict resolution and mathematical optimization methods. It is concluded by a synthesis which serves as baselines for our modeling and solution approach.

2.1 Extended AMAN

The Cross-border SESAR Trials for Enhanced Arrival Management (X-STREAM) project main objective is to extend the current horizon of the Arrival Management System beyond 200 NM towards the upstream Area Control Center (ACC). Extended-AMAN (E-AMAN) [6] allows for the sequencing of arrival traffic much earlier than is currently the case, by extending the AMAN horizon from the airspace close to the airport to further upstream and so allowing more smooth traffic management. Controllers in the upstream sectors, which may be in a different control center or even a different Functional Airspace Block (FAB), obtain system advisories to support an earlier pre-sequencing of aircraft. Controllers implement those advisories by, for example, instructing pilots to adjust the aircraft speed along the descent or even before top-of-descent, thus reducing the need for holding and decreasing fuel consumption.

2.1.1 Features

The traffic begins to be processed at the Eligibility Horizon (EH) and controllers are provided with AMAN advisories from the Active Advisory Horizon (AAH) onward [5]. EH is the spatial horizon where aircraft start to be considered by the AMAN and AAH is the spatial horizon where actions computed by the AMAN are executed by the aircraft. With the extension of the horizon of the AMAN to the En-route phase, as illustrated on Fig. 1, the EH goes further to around 180–200 NM which supports the controllers in applying more efficient arrival management techniques. The typical optimum top of descent is approximately 100–120 NM from touchdown which implies that up to 100 NM of flight within the extended AAH will be in En-route airspace.

2.1.2 Decisions on Flights

AMAN advice may be in the form of a Target Time at the Initial Metering Point (IMP) or Time To Lose (TTL)/Time To Gain (TTG) advisories to controllers calculated by AMAN working back from the runway time [5]. Upstream ACC controllers can then provide instructions to pilots to make adjustment of speed to meet TTL/TTG need, by executing advisories for speed coming from tools like Speed And Route Advisory (SARA)¹ or to delegate responsibility for adherence to a Controlled Time of Arrival (CTA) to flight crew.

Fig. 1

Simple horizon extension

Fig. 2

Protected area around the aircraft. If two areas overlap, there is a potential conflict

2.2 Previous Works

Optimization problems involve the minimization (or maximization) of a function by choosing input values from a given set of data and computing the value of the function. Nowadays, many studies have been conducted on the resolution of air traffic conflicts and the sequencing using various mathematical optimization techniques. This section will present a few of those works. Vela et al. in [10] presented a new approach based on concepts of speed control and flight-level assignment for conflict resolution over predefined routes. The resolution of this model was based on a Mixed Integer Linear Programming approach (MILP). The way it was formulated helped to reduce fuel burn over time horizons between 15 and 45 min. Qing et al. [7] proposed a flight scheduler for En-route air traffic. It was based on the application of delays or route changes to flights to produce an ordered merged sequence of flights at the exit nodes. They didn’t tackle the conflict resolution aspect in that paper. During the 2017 SESAR Innovation Days, Couchelle et al. [3] presented a method to perform small changes on aircraft speed in order to resolve conflicts. In their model, they considered that the True Air Speed (TAS) was constant for each aircraft in the airspace and the uncertainties appeared due to wind components, with wind data collected from MétéoFrance PEARP (Prévision d’Ensemble ARPège). A protection area, as illustrated in Fig. 2, is defined around each aircraft to represent its potential positions. Thus, two overlapping protection areas imply a potential conflict between the two aircraft that must be dealt with. The solution was implemented in Python using a simulated annealing algorithm. As a result, the algorithm was able to solve at least 70% of virtual conflicts with a computing time of 30 min to 2 h for a 4 h traffic data depending on the refinement of the parameters. On the other hand, Barragan et al. [2] presented their work at the 29th Congress of the International Council of the Aeronautical Sciences (ICAS). It was done on a study for a collaborative tool that aimed at helping controllers with the integration of the Extended Arrival Manager. They studied the aircraft sequencing problem as an optimization problem under different resolution methods (Linear programming, non-linear programming, heuristic methods). The objective function took into consideration the runway capacity, the delays and the fuel consumption. They also didn’t consider the conflict resolution aspect.

2.3 Synthesis

As seen in this section, the Extended Arrival Management tool gives advisory directives to controllers to help create an efficient sequence of flights starting from a distant En-route point. However, it is still up to the controller to decide how he will implement those directives taking into account the potential occurring conflicts. A tool like SARA, in combination with E-AMAN, can help controllers by giving speed directives but no global conflict resolution is provided. Thus, it will be an added value for our solution to provide both sequencing and conflict resolution capabilities. Moreover, most of the previous works done on the optimization of the traffic focused on changes made on aircraft speed or route to delay or advance a flight. Therefore, not many alternatives were given for conflict resolution when there is a dense traffic. In that case, we can introduce changes on flight levels to broaden the solutions possibilities as suggested by Courchelle et al. [3]. As for the optimization method to apply, the nature of our problem makes it more appropriate for a meta-heuristic method, given the dimension of the problem. Also, the simulated annealing appears as a good choice regarding its stability, its memory consumption profile and its speed. Ji et al. [8] introduced an implementation of the simulated annealing algorithm coupled with the sliding window concept, the base of our implementation will be that algorithm. Another added value we can integrate in our solution is the collaboration with multiple E-AMAN tools at the same time. The state of the art review enabled us to define basis for our study case. In the next section, we will define a detailed mathematical model for the problem. This will highlight abstract concepts useful for the design of our solution.

3 Mathematical Model

This section focuses on an abstract mathematical modeling of our problem. Each aspect of the problem is represented using mathematical notations that can be interpreted into any optimization algorithm later. It presents the global network representation, how uncertainties are modeled, equations related to conflict detection, the optimization objective function definition and an evaluation of the complexity of the problem. To simplify our model, we made some assumptions. The TAS of each flight will be considered as constant all along its route in the airspace of interest. Each plane will be flying a constant flight level all along its route in the airspace. For that, we suppose that the application of any decision to change the flight level is performed before entering the airspace of interest. We assume that the time for the aircraft to perform a climb or descend operation is negligible. In other words, we will not consider the time for flight level changes. The wind direction will be considered as constant in all the airspace. Only its intensity will be randomly varying (a more realistic wind may be included in the future). We will not consider uncertainties on the time of entry of a flight in the airspace. Regardless of any action done on a flight prior to its entry in the airspace, we will always use the planned entry time as time of arrival at the entry point.

3.1 Constraints

We have identified some constraints for our model. They are elements that will influence the way the tool will handle the optimization process.

Sequencing constraints: those constraints are coming from the sequencing system. The E-AMAN generates a TTL or TTG for flights. It must be considered during the optimization process.

Aircraft performances: those correspond to the physical performances of the aircraft. It consists of the minimum (maximum) speed and the minimum (maximum) flight level the aircraft can fly. Basically, our tool should not advise a flight to perform outside of its physical limits.

Flight preferred profile: It is a constraint that can be proposed by the airline. In our case, we will consider the preferred cruising flight level. It is a flight level which if cleared to the flight, will help the airline to better achieve their business objective.

Separation constraints: we have three types of separation: the distance separation which is a minimum defined distance should be maintained between two aircraft when crossing a specific point, the time separation for which two consecutive aircraft should reach a given location with a minimum defined time interval and the wake turbulence separation which is the separation distance between two consecutive aircraft flying on the same link at the same flight level and which depends on their wake turbulence categorization as defined by ICAO.

3.2 Network Modeling

The network of routes is modeled as an oriented graph with nodes and oriented links.

Nodes A node represents any point of interest on a route. Most of the time, it will be where two routes are crossing. We can define a separation constraint on them (distance or time separation). A node n is characterized by its cartesian coordinates $(x, y),\ x,y \in \mathbb {R}$, a minimum separation distance $d_{\text {sep}}$, in case of distance separation constraint and a minimum separation time $t_{\text {sep}}$, in case of time separation constraint. The set of nodes will be noted $\mathcal {N}$: $\mathcal {N} = \{n_i\ /\ i \in \mathbb {N},\ i \le nb_{\text {nodes}}\}$ where $nb_{\text {nodes}}$ is the total number of nodes in the network.

Links A link is a portion of route between two nodes. It is oriented from an origin node to a destination node. Each link is characterized by an entry node $n_{\text {ori}}$, an exit node $n_{\text {dest}}$ and a length $d_l = {\text {dist}}(n_{\text {ori}}, n_{\text {dest}})$. The set of links will be noted $\mathcal {L}$: $\mathcal {L} = \{l_i\ /\ i \in \mathbb {N},\ i \le nb_{\text {links}}\}$. $\forall l_i \in \mathcal {L},\ l_i = (n_{ori}, n_{\text {dest}}) \ / \ n_{\text {ori}}$ ,$n_{\text {dest}} \in \mathcal {N},\ n_{\text {ori}} \ne n_{\text {dest}}$ where $nb_{\text {links}}$ is the total number of links in the network.

Routes A route is an ordered list of adjacent links and is characterized by a parity p which can be odd or even: $p \in \{\text {ODD, EVEN}\}$ and a list of available flight levels $fls = \{fl\ /\ fl \in \mathbb {N} \}$. We will use the semi-circular rule to determine those flight levels depending on the parity of the route. The set of routes will be noted $\mathcal {R}$: $\mathcal {R} = \{r_i\ /\ i \in \mathbb {N},\ i \le nb_{\text {routes}}\}$, $\forall r \in \mathcal {R},\ r = \{l_i\ /\ l_i \in \mathcal {L}\}$ where $nb_{\text {routes}}$ is the total number of routes in the network.

3.3 Flights Modeling

A flight f is characterized by a speed $V_f$, a flight level ${FL}_f$, the time of arrival at the first node (entry in the airspace) $t_{f_{\text {init}}}$, a wake turbulence category $wtCat_f$ and a defined route $r_f \in \mathcal {R}$. Apart from those characteristics, a flight is also subject to some constraints: a maximum speed $V^{\max }_f$, a maximum flight level ${FL}^{\max }_f$, a preferred flight level ${FL}^{\text {pref}}_f$ given by the airline and a time constraint ${ttl}_f$ given by the sequencing system (a positive value means a time to gain and a negative value refers to a time to lose both before reaching the final exit node). The set of flights will be noted $\mathcal {F}$. $\mathcal {F} = \{f_i\ /\ i \in \mathbb {N},\ i \le nb_{\text {flights}} \}$ where $nb_{\text {flights}}$ is the total number of flights in the network.

3.4 Decision Variables

During the optimization process, two features of the flights are modified: the speed and the flight level. For that, we are using two decision variables which are the speed delta and the flight level delta.

Speed delta As in the model used by Courchelle et al. [3], we propose to use small speed changes to control flights speed. Each speed delta $\Delta V$ is an integer in the range of $-6$ to +3, expressed in percentage. $\forall f_i \in \mathcal {F},\ \Delta V_i \in \mathbb {Z} \cap [-6, +3]$. The new TAS $V_i$ of flight $f_i$ can be expressed as follow: $V_i = \frac{\Delta V_i}{100} \times V_{0_i}$ where $V_{0_i}$ is the initial TAS.

Flight level delta The second decision variable we are using is the flight level delta. It represents the number of levels an aircraft should climb or descend. It is expressed as an integer varying from $-2$ to 2. A positive value represents a climb whereas a negative value represents a descend.

$$ \forall {f_i} \in \mathcal {F},\,\, \Delta F{L_i} \in \mathbb {Z} \cap \left[ { - 2, + 2} \right] $$

3.5 Uncertainties

In our assumptions, we supposed that the TAS of flights is constant all along its route. However, in the real world, each flight is subject to wind influence in the air which can affect the ground speed. This section presents how we model the wind and how it generates uncertainties in our model.

Wind modeling: we use a simplified model for the wind. The wind vector is characterized by a constant direction all over the airspace (it is represented as an angle $\alpha _w$ relative to the geographical north) and an intensity Ws randomly varying within a range of values, with $Ws \in [Ws_{\min }, Ws_{\max }]$.

Flight uncertainty: the ground speed Gs of the aircraft is the resultant from both the TAS component and the Wind Speed component ($\overrightarrow{Gs} = \overrightarrow{TAS} + \overrightarrow{Ws}$). Let’s assume a flight arriving at the entry node $n_{ori}$ of a link l at $t_{ori}$, its time interval of arrival at the exit node $n_{\text {dest}}$ will be: $[t_{{\text {dest}}_{\min }},t_{{\text {dest}}_{max}}]$,$=[ t_{ori} + \frac{d_l}{V_{f_{\max }}}, t_{ori} + \frac{d_l}{V_{f_{\min }}}]$. This interval is built with the earliest time of arrival at the exit node $t_{{}_{\min }}$ which depends on $V_{f_{max}}$ which is the maximum ground speed of the aircraft and the latest time of arrival at the exit node $t_{{\text {dest}}_{\max }}$ which depends on $V_{f_{min}}$ which is the minimum ground speed of the aircraft.

3.6 Conflicts Identification

We will consider two types of conflicts: node conflicts and link conflicts.

Node conflicts They are detected using the separation constraints. Depending on the type of separation constraint at the node (time or distance separation), the equations to detect node conflicts will differ. To detect a distance separation conflict, a circular protection area with a diameter of $d_{\text {sep}}$ is defined around the node. Each flight arriving at the node will be monitored using four different times: an early time of entry in the protection area $t^{\text {in}}_{\min }$, a late time of entry in the protection area $t^{{\text {in}}}_{\max }$, an early time of exit from the protection area $t^{\text {out}}_{\min }$ and a late time of exit from the protection area $t^{\text {out}}_{\max }$. Two consecutive flights are considered to be in conflict at the node when they are both present within the protection area at the same time. In other words, the trailing flight enters the protection area before the leading flight exits it. Let’s consider two flights f and g with f leading. $\forall f,g \in \mathcal {F},\, cflt(f, g) = 1 \, \text {if } t^{f,{\text {out}}}_{\max } - t^{g,{\text {in}}}_{\min } < 0\,; (0\, \text {otherwise}).$ To detect a time separation conflict, a separation time $t_{{\text {sep}}}$ is defined on the node. Each flight arriving at the node will be monitored using two different times: an early time of arrival at the node $t_{\min }$ and a late time of arrival at the node $t_{\max }$. Two consecutive flights are considered to be in conflict at the node when the time interval between the two of them crossing the node is less than the separation time. Let’s consider two flights f and g with f leading. $\forall f,g \in \mathcal {F},\, cflt(f, g) = 1 \, \text {if} \,|t^{f}_{\max } - t^{g}_{\min }| < t_{\text {sep}}; \,\,(=0 \,\,\text {otherwise}).$

Link conflicts Link conflicts are essentially detected using wake turbulence category separation. Three situations are analyzed to detect those conflicts: at the entry node of the link, at the exit node of the link and catch-ups along the link itself. To detect entry conflicts, two different times are monitored at the entry of the link: an early time of arrival at the entry node $t^{\text {in}}_{\min }$ and a late time of arrival at the entry node $t^{\text {in}}_{\max }$. Two consecutive flights are considered to be in conflict at the entry of a link when the distance between them is less than the required wake turbulence separation distance. Let’s consider two flights f and g with f leading. $\forall f,g \in \mathcal {F},\, cflt(f, g) = 1; \,\, \text {if } {\text {dist}}_{\text {ori}}(f,g) < wTCat_{\text {sep}}(f, g);\,\,(0\,\,\text {otherwise}).$

$$ {\text {dist}}_{\text {ori}}(f,g) = V^{f}_{\min } \times (t^{f,{\text {in}}}_{\max } - t^{g,{\text {in}}}_{\min }) $$

With $wTCat_{\text {sep}}(f, g)$ the wake turbulence separation distance between f and g. To detect exit conflicts, two different times are monitored at the exit of the link: an early time of arrival at the exit node $t^{\text {out}}_{\min }$ and a late time of arrival at the exit node $t^{\text {out}}_{\max }$. Conflicts at the exit of the link are detected the same way as at the entry of the link. The distance between two consecutive flights is computed by using the exit times: $dist_{dest}(f,g) = V^{g}_{\max } \times (t^{g,{\text {out}}}_{\min } - t^{f,{\text {out}}}_{\max })$. Conflict detection at entry and exit only checks if the aircraft are properly separated when entering or exiting the link. However, within the link, faster aircraft can catch-up slower ones and cross them, thus implicating a loss of separation during the crossing. To detect catch-up conflicts, a comparison is made between the entry and the exit sequence of flights. Let’s assume $\mathcal {S}^{l}_{\text {entry}}$ and $\mathcal {S}^{l}_{\text {exit}}$ respectively the sequences of flights at the entry and at the exit of the link l, $pos: (\mathcal {F}, \mathcal {S}) \rightarrow \mathbb {N}$ the function that gives the position of a flight in a sequence. There is a catch-up conflict if: $\exists f \in \mathcal {F}/\ pos(f, \mathcal {S}^{l}_{entry}) \ne pos(f, \mathcal {S}^{l}_{\text {exit}})$.

3.7 Objective Function

The mathematical modeling of the problem leads to a multi-objective optimization problem which aims at minimizing parameters linked to conflict occurrences, flight level modification, speed modification and also flights timing. The main objective is to reduce the global conflict count both on nodes and links. Let’s consider $c_{\text {obj}}$ the total conflict objective value.

$$ c_{\text {obj}} = \sum _{n \in \mathcal {N}} c_n + \sum _{l \in \mathcal {L}} c_l $$

Two values related to flight level modifications are evaluated in the objective function:

$$ fl_{\text {obj}} = fl_{\text {changes}} + fl_{\text {gap}} $$

where $fl_{\text {changes}}$ represents the total number of aircraft which decision implies FL change and $fl_{\text {gap}}$ is the summation of the difference between the final flight level and the preferred flight level of each flight. As for the flight level gap objective, we also want to minimize the gap between the initial speed and the final speed for each flight. For that, the speed objective $s_{\text {obj}}$ is expressed as follows.

$$ s_{\text {obj}} = \sum _{f \in \mathcal {F}} |\Delta V_f| $$

Finally, we also want to make sure that the flights will arrive at their last node at the requested time with a reasonable (minimal) error margin. Thus, the time objective is expressed as follows.

$$ t_{\text {obj}} = \sum _{f \in \mathcal {F}} |t^{f, {\text {last}}\_{\text {node}}}_{\max } - t^{f, {\text {last}}\_{\text {node}}_{\text {planned, max}}}| $$

The global objective function $f$ is the sum of all the objectives listed above.

$$ f = c_{\text {obj}} + fl_{\text {obj}} + s_{\text {obj}} + t_{\text {obj}} $$

The complexity of our model mainly depends on the dimension of the problem (number of flights involved) and the range of the decision variables. If we consider $n_s$ options for the speed changes and $n_{fl}$ options for the FL changes, then for $N_f$ flight the size of the solution space is given by $(n_s \times n_{fl})^{N_f}$. In our model, $\Delta V \in [-6, +3]$ and $\Delta FL \in [-2, +2]$, the size of the solution space can be expressed by $(10 \times 5)^{N_f}$. To address such combinatorial complexity, we have developed a meta-heuristic based on a sliding-window simulated annealing.

4 Simulated Annealing

This method, as described by Soliman et al. [9], is based on the annealing process which is a physical process consisting of heating up a solid until it melts, then cooling it down in order to obtain a perfect crystallized form. During this process, the resulting structural properties depend on the residual energy in the material which is influenced by the rate of cooling. Thus, the cooling phase must be controlled in order not to get trapped in a locally optimal structure with high energy crystals, resulting in imperfections. In combinatorial optimization, the equivalent process is the simulated annealing which aims at finding a solution with minimal cost.

4.1 Principle

Let’s consider the model presented by Henderson et al. [4]. Let $\Omega$ be the solution space (the set of all possible solutions). Let $f: \Omega \rightarrow \mathbb {R}$ be an objective function defined on the solution space. The goal is to find a global minimum, $\omega ^{*}$ ($\omega ^{*} \in \Omega$ such that $f(\omega ) \ge f(\omega ^{*})$ for all $\omega \in \Omega$). The objective function must be bounded to ensure that $\omega ^{*}$ exists. Define $N(\omega )$ to be the neighborhood function for $\omega \in \Omega$. Therefore, associated with every solution, $\omega \in \Omega$, are neighboring solutions, $N(\omega )$, that can be reached in a single iteration of a local search algorithm. Simulated annealing starts with an initial solution $\omega \in \Omega$. A neighboring solution $\omega ^{'} \in N(\omega )$ is then generated. The candidate neighboring solution is accepted as the current solution based on the acceptance probability.

$$ P\{\text {Accept} \,\omega ^{'}\text {as next solution}\} = $$

$$ {\left\{ \begin{array}{ll} {\text {exp}}[-(f(\omega ^{'}) - f(\omega )) / T_k)] &{} \text {if}f(\omega ^{'})> f(\omega ) \\ 1 &{} \text {if}f(\omega ^{'}) \le - f(\omega ). \end{array}\right. } $$

where $T_k$ is a parameter which control the probability of accepting a degraded solution. As illustrated in Fig. 3, each solution vector $\vec{X}$ which gather together the decision variables of aircraft is evaluated in a simulator process. This simulation is very powerful in the sense it can take into account many realistic aspects of the operational system. The result of the simulation generates the objective function which will be used by the optimizer (simulated annealing). The initial temperature is essential to define the behavior of the algorithm when it comes to the acceptance of solutions. We have set the initial temperature in order to get 80% of solutions to be initially accepted. We have used a geometric cooling law ($T_{k+1}=\alpha \cdot T_{k}$ with $\alpha$ in the range [0.8, 0.99]. Efficient stopping criterion can prevent the simulated annealing algorithm from performing unnecessary computations [4], thus reducing its global execution time. In our case, three criteria are used to stop the cooling procedure: when the final temperature $T_{\text {final}}$ reaches a defined fraction of the initial temperature $T_{\text {init}}$, when the evaluated criteria reach the value zero, or when the evaluated criteria remain constant over a defined number of iterations.

Fig. 3

Simulated annealing principle

4.2 Neighborhood Function

Small changes on a local solution are performed using a neighborhood function. The efficiency of simulated annealing is highly influenced by the neighborhood function used. In our case, each solution is a set of flight decisions and determining a neighbor solution consists only on randomly modifying a flight decision in our set. The method used to choose the random flight is similar to the roulette wheel selection presented by Ji et al. [8]. On each flight decision, a performance criterion is evaluated, it corresponds to the sum of the total number of conflicts on the flight and the resulting delay. All the decision performances are added up together then a target value is randomly chosen between zero (0) and the total performance sum. Then, the cumulative sum of decision performances is calculated starting from the first decision until the cumulative sum reaches the previously chosen target value. The index at which it stops marks the flight decision on which a change will be done to generate a neighbor solution. Choosing the decision to change with this method guarantees that the selected flight is the one which is most likely to generate more conflicts and a large absolute delay. Given a flight decision, generating a neighbor solution consists in modifying the flight level delta $\Delta FL$ and the speed delta $\Delta V$. Both modifications are done within their respective discrete range of values $[-2, +2]$ and $[-6, +3]$, with the same probability of occurrence $p = 0.5$.

4.3 Sliding Window

The sliding window approach as proposed by Ji et al. [8] is a technique based on the receding horizon control. It consists into dividing the entire time horizon into smaller equal intervals and thus evaluating the state of the network within the small time intervals. The evaluation interval starts from the earliest time and progressively moves forward in time with a defined step until reaching the latest times. With this approach, it is not necessary to evaluate all the flights at once during the optimization since not all flights are involved in each sliding window interval. This method is more convenient in a dynamic environment with uncertainties and improves the computational time of the optimization process. Figure 4 illustrate how the sliding windows are generated all along the global optimization time interval.

Fig. 4

Sliding window principle [8], W: the length of the sliding window, S: time shift of the sliding window

Fig. 5

Routes towards Paris CDG airport

5 Results

This section presents the results of our algorithm on real-life traffic data at Paris CDG. Paris CDG TMA is accessible through four entry points: OKIPA, MOPAR, LORNI and BANOX. Our experimentation airspace is focused on the En-route portion of traffic arriving at CDG airport which corresponds to four areas each having a TMA entry point as last node as we can see in Fig. 5.

All nodes (waypoints) except the four entry points are constrained with a 5NM separation minimum. As for the TMA entry points, the minimum separation between aircraft is 8NM. Concerning the wind data, we considered wind components with an angle of $30^{\circ }$ relative to the geographical north. The wind intensity has been set within the range 25–35 kts all over the test airspace. A simple analysis of the network structure shows 742 different nodes with 817 links. This will contribute to increase the complexity and so the resolution time. In our scenario, we will consider a 24-h traffic data of 690 flights corresponding to the filed flight plans arriving at LFPG on July 28th, 2016. The arrivals are distributed among the four entry points of CDG Terminal Area (TMA) with the majority of flights arriving at LORNI and OKIPA nodes (Table 1). There is also a distribution of medium and heavy wake turbulence category aircraft with a majority of medium aircraft.

Table 1 Flights distribution by TMA entry point

5.1 Statistics

Our algorithm written in Java 8 has been executed on an Ubuntu 18.04 operating system PC equipped with an Intel Core i5-3230M processor (4 $\times$ 2.60 GHz) and 8 GB of memory. The simulated annealing algorithm has been tested with the parameters in Table 2. Given the length of the sliding window (2 hours) and the distribution of flights, each resolution step on a sliding window will handle around 100 flights on average. A first analysis of the flight data detected 407 conflicts.

Table 2 Simulated annealing/sliding window test parameters

Table 3 Optimization results on LFPG data

The optimization algorithm analyzed the 690 flights and has solved the sequencing and the conflicts within a computation time of 11 min and 23 s. It solved all the 407 initially identified potential conflicts, which gives an efficiency rate of 100%. It changed flight levels on a total of 127 flights: 67 climbs and 66 descents. As for the speed, 4 flights have been accelerated and 4 slowed down which make a total of 8 speed changes. At the end, a total absolute delays value of approximately 611 s has been generated for the flights with speed changes which gives an average of approximately 1 min per modified flight (the 8 flights with speed modification). Very few flights have been affected by speed variations, also, the generated absolute delays, an average of 76 s per modified flight is still acceptable. Table 3 summarizes all those changes.

6 Conclusion

This paper introduced the work done on the sequencing of the air traffic in En-route segments influenced by constraint points. We saw that En-route controllers are getting more involved in the pre-sequencing of arriving flows when they are still in the cruising phase which causes an increase of their workload. On the other hand, airlines wish to have efficient flights with few flight level changes around a certain preferred vertical profile and also less maneuverings due to conflict avoidance. To solve those issues, we have developed a decision support tool which can assist controllers in their tasks for sequencing traffic and solving conflicts in En-route airspace. After reviewing the concepts and previous works related to our subject, we based our study on a mathematical modeling of the problem followed by an optimization algorithm in order to extract traffic sequences. Using the simulated annealing algorithm for optimizing flights decisions appeared to be a good choice given its efficiency and adaptability properties. A first trial of our solution on real traffic data over Paris airspace displayed a resolution ratio of 100% for conflict solving and an acceptable level of speed and flight level changes. Also, the generated delays due to the compliance with sequencing constraints and conflict resolution appeared within an acceptable range. Moreover, a preliminary version of the algorithm was able to generate flights instructions that can be directly applicable by controllers. Apart from this first test scenario, the solution as it has been designed is able to simultaneously provide En-route sequencing for several airports arrival flows. Even if it has not been used in the Paris CDG case, the algorithm can also manage time constraints for some points in the airspace (points connecting countries with letter of agreement). On the other hand, it can also be helpful for airports not yet equipped with an arrival management system as long as the constraints at TMA entry points are well defined. As another advantage, our solution will facilitate novel arrival techniques and procedures such as Continuous Descent Operation (CDO) and Point Merge System (PMS).