Computational Intelligence - November 2014 - 60

In order to measure the interaction
between trajectories, we developed a gridbased interaction-detection method. To
reduce the number of sampling points
needed while minimizing further the computation time, this interaction-detection
method interpolates the aircraft position
between two suspected sampling points
instead of refining the sampling-time step.
To find an optimal route and a departure time for each
flight, we rely on a hybrid-metaheuristic optimization algorithm that combines the advantages of simulated annealing
and of hill-climbing local search methods. The simulated
annealing ensures diversity of the candidate solutions considered, while the local-search methods intensify the search in
promising regions of the feasible domain in order to accelerate convergence.
The proposed algorithm was first tested with en-route airtraffic data over the European airspace. Two different local
search strategies were investigated and compared. The first strategy concentrates on improving the current solution by modifying one single trajectory at a time. The second strategy aims
at improving solutions by modifying all neighboring flights
interacting with a given flight. Numerical results show that it is
more efficient to employ both strategies sequentially to converge to interaction-free solutions, since it requires . 40% less
computation time than using each strategy separately.
The impact of the number of virtual waypoints on the
resolution time was studied. Despite the increasing of the
richness of the solution space, using more virtual waypoints
induces more combinatorics to the search space leading to a
longer computation time. Moreover, the resulting trajectories
involve undesirable zig-zags.
The impact of augmenting the number of degrees of freedom in the search space on the quality of the results
obtained wby our methodology was also studied and

This enlargement of the protection volume allows
an aircraft to follow its 4D trajectory plan with some
margin. It can arrive at a given point with some
deviation while the minimum interaction condition
is still satisfied.
waypoints, M, and the coefficients a i and b i are set as in the
previous subsection. The initial total interaction U tot,init of both
traffic scenarios with and without consideration of uncertainty
are compared in Figure 20 (left). The simulation was carried
out 10 times. The proposed algorithm is able to separate all trajectories ^U tot,final = 0h for both traffic scenarios, taking into
account uncertainties of aircraft positions in the horizontal
plane. The computation times to reach the interaction-free solutions for both traffic scenarios with and without consideration of uncertainty are compared in Figure 20 (right).
The required computation time is significantly longer
when the uncertainty is considered. It is, however, still viable
for a strategic planning phase. This can be improved by introducing more degrees of freedom to the solution space, e.g.,
alternative flight levels, or speed regulation in the TMA.
VII. Conclusions

We introduced an efficient methodology to address strategic
planning of aircraft trajectories in the framework of future
trajectory-based ATM operation involving large scale traffic
such as that at the European-continent scale. The aim of the
proposed method is to minimize interaction between trajectories, so as to minimize the air-traffic controller's workload.
The proposed method relies on a route/departure-time
allocation technique to modify the initial trajectory plan.
The problem was modeled mathematically under the form
of an optimization problem aiming at minimizing interaction between trajectories.

# 105

3000
Renroute = 0
Renroute = 3

4.5
Initial Interaction Utot

4
3.5
3
2.5
2
1.5
1
0.5
0

En-Route

En-Route + TMA
(a)

Computation Time (minutes)

2500

Renroute = 0
Renroute = 3

2000
1500
1000
500
0

En-Route

En-Route + TMA
(b)

Figure 20 (a) Initial interaction between trajectories with and without consideration of uncertainty. (b) Comparison of computation time with
and without consideration of uncertainty.

IEEE ComputatIonal IntEllIgEnCE magazInE | novEmbEr 2014

Table of Contents for the Digital Edition of Computational Intelligence - November 2014