HEATS-3D

Hybrid Evolutionary Algorithms for Trajectory Separation in 3 Dimensions

Start date: 2001
End date: 2005

Description

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 first one uses an A* algorithm to compute each trajectory in turn, minimizing an individual cost (related to horizontal and vertical deviations) while avoiding the other previously computed trajectories.
The second method uses an evolutionary algorithm, hybridized with an A*, to minimize a global cost associated to the whole set of trajectories, while satisfying the separation constraints.

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:

detection with a distance criterion, with a unique aircraft type. The distance is defined between line segments, taking into account the standard vertical and horizontal separations,
detection of secant tubes, defined around the 3D-line segments of the trajectories, still with a unique aircraft type,
detection of secant uncertainty zones, taking into account the various aircraft types.

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

a single trajectory per origin-destination flow,
one main trajectory per flow, plus some additionnal trajectories for departures from -- and arrivals to -- airports located nearby the airspace border, in the case of entering or exiting flows,
several trajectories per flow, according to the entry, cruise, and exit flight levels. A k-means method allows to classify the flights, according to these levels.

Progress

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	Profit
30.00%	10 à 15 %
40.00%	20 à 30 %
50.00%	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.

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.

Software

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

Main publications

Last Update: