Hybrid Evolutionary Algorithms for Trajectory Separation in 3 Dimensions

bar Image europe
  • Start date: 2001
  • End date: 2005


HEATS-3D started in 2001, as a part of a thesis dealing with the optimization of air traffic flows.

The aim is to assign optimal conflict-free 3D-trajectories to the main origin-destination flows. Two strategies were used: sequential or global.

The route from origin to destination may be chosen either among three parallel direct routes, or among several paths in the standard routes network. Several detection modes and several 3D-flows models have been implemented, corresponding to various degrees of realism. The three modes allowing to detect interferences between trajectories are the following:

With the different 3D-flows models, we may assign:


Both strategies, global and sequentital, have been tried first on test-cases, with a basic trajectory model, and with the most simple detection.

The algorithms have then been adapted to french and european traffic data samples, using realistic aircraft performances models, and considering the disparity of aircraft types within each origin-destination flow.

The 3D-separation concept have been assessed, only with french data so far, through CATS simulations, considering a reference traffic, and a modified traffic where aircraft belonging to the main flows follow their assigned 3D-trajectories. The number of conflicts detected in both situations is used to assess the profit of the 3D-separation, supposing that aircraft following the same 3D-trajectory have been separated by the departure manager, through time sequencing .

The simulations use the whole traffic of a chosen day as input. But the 3D-separation applies only to a part of this whole traffic. The proportion of traffic handled on the 3D-trajectories network depends on the chosen 3D-flows model, and on the initial selection of flows. The following table summarizes the main results on the concept assessment, with, on the left column, the percentage of traffic handled on the 3D-network, and on the right column the decrease in the number of detected conflicts.

% traffic



10 à 15 %


20 à 30 %


35 à 40 %

Click here to see the presentation of the concept assessment, made at the 6th USA/Europe ATM 2005 R&D Seminar.

Further work may deal with the definition, in the european context, of TMA-to-TMA flows instead of airport-to-airport flows, and also with the application of a parallel evolutionnary algorithm to disconnected sub-problems.

Example with a test-case

The following figure shows the trajectories computed by the evolutionary algorithm for a configuration of 10 flows, with origins and destinations located on a circle, and with two-ways flows.

This example shows lateral deviations, for face-to-face flows, and vertical deviations, at the crossing point at the circle's center.

[Circle problem]

Example with french traffic

This example deals with flows of at least 20 flights on the 21st june of 2002, above France, with flights requesting a cruise flight level higher than FL145 (14500 feet above 1013.25 hPa isobar).

The 71 trajectories of this configuration, with a unique trajectory assigned to each origin-destination flow, represent 39.6% of the overall traffic.


Example with european traffic

This example illustrates the 3D-flows model assigning several trajectories per flow, with flows of at least 10 flights, over Europe, on the 21 june of 2002.

The 235 trajectories represent 12% of the overall traffic, which is relatively less than for the french traffic. Designing TMA-to-TMA flows instead of airport-to-airport flows would allow to handle more traffic.



HEATS-3D is written in Objective Caml. The code is not public domain.

Main publications

Last Update: