David Gianazza
email: gianazza@recherche.enac.fr

Nicolas Durand
email: durand@recherche.enac.fr

Assessment of the 3D-separation of Air Traffic Flows

, where two algorithms were introduced, allocating optimal separated 3D-trajectories to the main traffic flows. The reader may also refer to [3] (PhD thesis, in french) for more details. In [1], these algorithms -an A * algorithm for the sequential strategy, and an evolutionary algorithm for the global optimization -were tried on a toy problem, and the two strategies were compared. In [2], the algorithms were again briefly introduced and illustrated on the same toy problem, and then applied to real traffic data, using operational aircraft performances, but with only one 3D-trajectory per flow. In this paper, we present more realistic models of 3D-flows, with several trajectories per origin-destination link. The 3D-separation concept is then assessed by comparing the conflicts detected in a traffic of reference, with the conflicts detected when the aircraft belonging to the main traffic flows follow separated 3D-trajectories.

I. Introduction

The Air Traffic Services are facing a critical problem of airspace congestion, which is becoming more and more difficult to handle. In the past, the solutions to this reccurent problem were relatively simple: re-design the airspace routes network, split the airspace in smaller sectors and enlist more controllers, improve the technology (radar, automated flight plan coordination, and so on), and thus increase the controllers productivity, or regulate the traffic demand by allocating costly ground delays.

This system is now reaching its limits: on the one hand, a small amount of additionnal traffic generates a great increase in the cumulated delays (c.f. Eurocontrol report [4]), and, on the other hand, the integration of technological improvements into the system becomes more and more complex, and slow.

Several alternative operational concepts appeared in the last yearsfree-flight ([5], [START_REF]Free flight case study[END_REF]), free-route ( [START_REF]The eight-states free route airspace project: Free route airspace concept[END_REF], [START_REF]Eight-states free route airspace project: Feasibility assessment report[END_REF]), and, more recently, sector-less ( [START_REF] Duong | Sectorless air traffic management[END_REF]), or super-sector ( [START_REF] Gawinowski | Operational concepts for supersector[END_REF]) -proposing radical changes in the way to handle air traffic. The pure free-flight -as a distributed system where each aircraft would choose its own trajectory and avoid nearby traffic, using the appropriate on-board equipment -is less performant than a centralized system ( [START_REF] Granger | Détection et résolution de conflits aériens : modélisations et analyse[END_REF]). It could however be applied within low-density areas, with efficient distributed algorithms ( [START_REF] Alliot | Faces: a free flight autonomous and coordinated embarked solver[END_REF]). The freeroute concept, promoted by eight european countries, proposes the establishment of a specific airspace within which users shall freely plan their routes between an entry point and an exit point. Ground-based controllers would remain responsible for traffic separation, in a sectorized airspace, with the help of specific conflict detection and resolution tools. In the sector-less or supersector concepts, the idea is to get rid of the airspace sectorization: the controller's tasks would focus on a mission -safely route a group of aircraft from one point to another -and not on a sector of airspace. The detailed implementation and the expected benefits of these concepts are not well-established yet.

Another interesting concept is the "TMA to TMA1 " hand-over, where direct routes would link the main european terminal areas. The traffic on these routes would have priority on the rest of the traffic, and would be handled by specific departure and arrival management systems, ensuring the along-track separation. The TOSCA2 study ( [START_REF] Maugis | TOSCA-II -WP3: Assessment of the TMA to TMA hand-over concept[END_REF]), assessing this concept, shows potential benefits in terms of cumulated delays, but underlines the difficulty to build a network with no intersecting routes while taking into account a significant amount of traffic. However, only 2D-routes are considered in this concept.

In this paper, we propose to reduce congestion by assigning static 3D-trajectories to the traffic flows between the main airports, using two alternative methods. The first one is an iterative 1 vs. n strategy where flows are considered in a chosen order (for example in decreasing order of size), and the second is a stochastic approach with a global strategy. With the first method, trajectories are sequentially computed, so that the first flows will have the most direct (closest to default) 3D-trajectories. The second method searches a global optimum by applying an evolutionary algorithm to populations of trajectories sets. The full description of these algorithms can be found in [START_REF] Gianazza | Allocating 3dtrajectories to air traffic flows, using a * and genetic algorithms[END_REF], where they were tried on a toy problem with a simplified model, and also in [START_REF] Gianazza | Separating air traffic flows by allocating 3d-trajectories[END_REF], where the two algorithms were applied to real traffic samples (France and Europe), with realistic aircraft performance models (the ones currently used in the operational system). The work presented here is a continuation of these two papers, and presents more realistic models of 3D-flows, before focusing on the validation of the 3D-separation concept.

Following this introduction, the second section of this paper gives a short overview of other works related to our subject. The third section describes the trajectory model, the detection modes, the different models of 3D-flows, and the algorithms are shortly described in the third section. Only the main features, useful to the understanding of the rest of the paper, are presented. The fourth section analyses the flows over France and Europe, on one day of traffic. The next two sections present some results on the 3D-separation over France and Europe. The seventh section is dedicated to the validation of the results. The conclusion summarizes the main results and gives an overview of the future work on the subject.

II. Other related works

In parallel to the operational concepts discussed in the introduction, several research issues related to Air Traffic Management are being explored, many of them dealing with capacity problems ( [START_REF] Bertsimas | The traffic flow management rerouting problem in air traffic control: A dynamic network flow approach[END_REF], [START_REF] Delahaye | Airspace congestion smoothing by stochastic optimization[END_REF], [START_REF] Barnier | Slot allocation with constraint programming: Models and results[END_REF]) or with dynamic flight planning through a congested airspace ( [START_REF] Jardin | Real-time conflict-free trajectory optimization[END_REF], [START_REF] Van Kemenade | Evolutionnary computation in air traffic control planning[END_REF]), using a variety of deterministic or stochastic methods. Solving these problems is not in the scope of this paper, which deals with static 3D-trajectory design. The routes network design is adressed in [START_REF] Mehadhebi | A methodology for the design of a route network[END_REF], using Voronoï diagrams and clustering methods which iteratively move and merge the crossing points of the network. Although quite interesting, this approach is mainly bi-dimensionnal and does not take into account the vertical evolutions of aircraft. In [START_REF] Letrouit | Optimisation du réseau des routes aériennes en Europe[END_REF] and [START_REF] Barnier | Graph coloring for air traffic flow management[END_REF], Graph Colouring techniques are used to assign cruising flight levels to aircraft flying on direct routes, in order to ensure vertical separation during the cruise. The climbing or descending trajectory segments are not considered.

In the TOSCA study ( [START_REF] Maugis | TOSCA-II -WP3: Assessment of the TMA to TMA hand-over concept[END_REF]), already evoked in the introduction, the idea is to remove a percentage of the traffic from the current ATC system -and from the slot allocation process -by defining conflict-free routes between the main terminal areas. Aircraft flying on these routes would have priority over the rest of the traffic and would be handled by specific departure and arrival management tools. According to this study, removing even only a small percentage of traffic may drastically reduce delays, as long as the impact on the overall system capacity is limited. However, only horizontal separation between routes is discussed: crossing routes are either forbidden or allowed in a very limited way. So only a few traffic flows could be considered, without significant profit in terms of conflict reduction. In addition, it is not specified how aircraft would be sequenced on each route, nor how the separation of traffic flows would be achieved, otherwise than by choosing non-intersecting 2D-routes.

To conclude this section, we may say that the 3Dseparation of air traffic flows is still an open research issue. We will now briefly present two algorithms achieving this goal, and then assess the concept through fast time simulations.

III. Models and algorithms

A. Trajectory model

In the rest of the paper, the term flow refers to a set of flights between a departure airport and an arrival airport. Note that this definition is more restrictive than the informal definitions usually found in the ATM 3 community, where traffic may flow from one geographic area to another, or through a given sector, or over a chosen point or route segment.

In order to simplify our problem, the airspace is considered as an Euclidean space, where all airports are at altitude 0. Latitudes and longitudes on the ellipsoïd earth surface are converted into (x, y) coordinates by a stereographic projection, and the altitude in feet shall be our z coordinate 4 .

The early implementations of our algorithms were founded on a simplified model, where all aircraft flew with identical performances. A trajectory was simply a sequence of 3D line segments, and interfering trajectories were detected according to a new distance criterion, which included both vertical and horizontal standard separations. All aircraft belonging to a given flow flew with identical performances, requested a same cruise flight level RF L i 5 , and followed by default a direct route between departure and arrival. This allowed to define only one 3D-trajectory per flow.

In reality, there is a great disparity of aircraft performances. Various types of aircraft may operate the same origin-destination link, with different flight profiles for a same sequence of cleared flight levels. This is illustrated on figure 1 which shows such profiles (for the following aircraft types: A340, B742, B743, B744, B762, B763, B772, DC10, L101, MD11). Furthermore, for a given aircraft type, the climb or descent rates may depend on the aircraft load or on the airline's procedures.

There are several consequences to this disparity. Instead of a single requested flight level, we have several peaks of requested levels per flow. So we may need to define several 3D-trajectories for each origin-destination 3 Air Traffic Management 4 These approximations are possible only as long as we stay in an area around the projection center which is not too large. Some errors are introduced in the computation of distances between trajectories : aircraft usually follow orthodromic routes over the earth surface, which will not be projected as straight lines on our stereographic plane. These errors can be balanced in our problem by increasing the separation minima between trajectories.

5 Requested Flight Level flows, each trajectory corresponding to a preferential cruise flight level.

Another consequence is that a 3D-trajectory model must include some uncertainty, at least in the vertical dimension. The vertical uncertainty zone is defined for each 3D-trajectory as the hull of all possible flight profiles for all types of aircraft of the flow. In order to avoid the computation of all these profiles at each step of the algorithms, the upper and lower hulls of the climb and descent profiles are pre-computed for each flow, and then used by the algorithms to compute the uncertainty zone when necessary.

B. Detection modes

With the uncertainty zones described above, it is no longer possible to detect interferences6 between 3D-line segments with a distance criterion. To avoid this problem, a new type of detection is introduced. A tube is defined around each trajectory segment, taking into account the separation standards N h and N v and also the vertical uncertainties, when needed. The new detection uses the following criterion: two trajectories are interfering when their 3D-tubes are intersecting.

With these two types of detection -distance between lines, or intersection of tubes -we define three possible modes of detection :

DIST: between 3D-line segments, with the distance d, ITUBES: between 3D-line segments, with the intersection of tubes of height N v , and of width N h , IZONES: between uncertainty zones, with the intersection of tubes defined around these zones. In addition, a no-detection zone is defined around each airport. The radius of the zone is an input parameter of the program (15 NM as default). The interference detection is also turned off when considering two initial climbs from a same airport, or two final descent downto a same airport.

Let us note that the two first detection modes cannot be used when they are several types of aircraft in a given flow. We have to consider that there is only one type of aircraft per flow. The Airbus A320 was chosen for these detection modes, in the rest of this paper. The third mode is the most realistic, and takes into account the variety of aircraft types and performances within each origindestination flow.

C. Models of 3D-flows

Knowing the origin and destination points is not enough to compute a 3D-trajectory. We also need a default -or preferential, both terms may be used in the rest of the paper -cruise level, and preferential entry and exit flight levels, when the origin or destination are not airports but entry/exit points.

Three different models of 3D-flows are proposed, with different degrees of realism:

UNIC , with only one 3D-trajectory per origindestination flow. The default cruise level is then the most demanded cruise level. The default entry (resp. exit) level is 0 if the origin (resp. destination) is an airport, or the default cruise level if it is an entry (resp. exit) point; PROX , where additionnal trajectories may be computed for flights climbing from -or descending to -airports which are near the airspace frontier. MULTI , with several possible 3D-trajectories for each origin-destination flow. A k-means method is used to classify the flight plans, according to the entry, cruise, and exit levels filed in the database. A 3D-trajectory will be assigned to each class, using the entry, cruise, and exit levels of the class centre as default values (the flight levels may be modified by the algorithms).

D. Lateral and vertical deviations

In order to avoid trajectory interferences, some lateral or vertical deviations to the default trajectory may be introduced.

The proposed algorithms allow two possibilities when choosing the preferential route between origin and destination: it may be either the direct route, or the shortest standard route on the actual operational network. In the first case, we may allow lateral deviations, following parallel routes either on the left or on the right of the direct route. In the second case, a set of alternative routes is computed for each origin-destination flow. At the time being, this set is obtained by considering all routes filed in the flight plan database. The algorithm will then choose among these possible routes.

The default vertical evolutions, for a given origindestination flow and a preferential cruise flight level, are an initial climb from the departure airport, followed by a cruise at the default flight level, and then a final descent downto the arrival airport. The vertical deviations will then be represented by a sequence of instructions of the following type: at distance d j along the route, climb or descend to flight level CF L j . Each of the intermediate flight levels CF L j shall be comprised between a minimum flight level and the preferential flight level RF L.

E. Cost of a trajectory

We are now able to define a cost related to the lateral and vertical deviations for a trajectory i. The cost of a vertical deviation depends on the surface between the effective vertical profile and the cruise level :

l i × RF L i -surf ace(prof ile)
where l i is the length of the chosen route. This cost should not depend on the distance between origin and destination (otherwise small deviations on long flights may cost as much as big deviations on short flights), so we shall divide this expression by the route length l i . The cost of a lateral deviation depends on the route elongation (li-lrefi)

lrefi

, where lref i is the length of the direct route.

Finally, the total cost of a trajectory is a combination of the two, with K a chosen factor : :

cost(i) = RF L i - surf ace(prof ile i ) l i +K× (l i -lref i ) lref i

F. The A * algorithm

The A * algorithm is applied iteratively to each flow. Its aim is to find the shortest trajectory from departure to arrival, while avoiding the already computed trajectories.

The idea of the A * algorithm (cf. [START_REF] Pearl | Heuristics[END_REF]) is to search the best path through a tree of possibilities, restarting at each step from the best possible node encountered so far during the search. To do this, we need a cost function for the transitions between states (tree nodes), and a heuristic function which shall estimate the cumulated cost of the transitions remaining between the current state and a possible solution. In our problem, the states shall represent choices in the possible deviations (horizontal or vertical), made at each step of the trajectory. The cost and heuristic functions depend on the extent of the trajectory deviations, and are detailed in [START_REF] Gianazza | Allocating 3dtrajectories to air traffic flows, using a * and genetic algorithms[END_REF].

In order to search among the tree of all possible nodes, we need to define rules that generate new nodes : the sons of the current father node. In our case, the sons are the possible alternatives for the next trajectory step. If an interference is detected between the next step and previous trajectories, the corresponding son is discarded (see [START_REF] Gianazza | Allocating 3dtrajectories to air traffic flows, using a * and genetic algorithms[END_REF] for details). The search ends when the arrival airport -or the exit point -is reached. The trajectory built by the A * is then the one closest to the default trajectory that does not interfere with the other trajectories.

G. The evolutionary algorithm

Evolutionary algorithms are based on the paradigm of natural evolution. Optima are reached through a process of crossing, mutation and selection of the fittest individuals. This process is applied to a population of chromosomes. The reader may refer to [START_REF] Eiben | Introduction to Evolutionary Computing[END_REF] for an overview of the latest algorithms based on the evolutionnary paradigm, or to [START_REF] Holland | Adaptation in Natural and Artificial Systems[END_REF] and [START_REF] Goldberg | Genetic Algorithms[END_REF], [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF] for more details on genetic algorithms. A good state of the art of optimization using genetic algorithm may also be found in [START_REF] Fablec | Optimisation par algorithmes génétiques parallèles et multi-objectifs[END_REF] and [START_REF] Durand | Optimisation de trajectoires pour la résolution de conflits aériens en route[END_REF], with a practical application to the Air Traffic Control domain (specifically to conflict solving) in the latter. In our problem, a chromosome will be a set of n trajectories. Each chromosome of the initial population is generated by randomly choosing its n trajectories, within given bounds.

The fitness criterion allowing to select the best individuals at each step is directly related to the cumulated cost of trajectory deviations. However, the fitness function also takes into account the interferences between trajectories : chromosomes with interfering trajectories shall be penalized. Fitness values shall be less than 1 for chromosomes with interfering trajectories, and above 1 for chromosomes with separated trajectories. In this last case, the smaller the trajectory deviations will be, the greater the fitness will be. The fitness function, as well as the crossover and mutation operators are detailed in [START_REF] Gianazza | Allocating 3dtrajectories to air traffic flows, using a * and genetic algorithms[END_REF].

IV. Traffic flows analysis

Before presenting the results, let us briefly report some previous work on the nature of traffic flows over France and Europe. A short traffic analysis on a single day of traffic (21st june 2002), presented in [START_REF] Gianazza | Separating air traffic flows by allocating 3d-trajectories[END_REF], shows that the traffic over Europe7 is mainly intra-european: more than 85 percent of the flights on the considered day take-off and land within the considered airspace. When focusing on the smaller part of airspace (France), we see that more than a half of the origin-destination flows begin and/or end at the border of the french airspace, and more than 75 percent of the traffic comes from or goes to a foreign airport.

This brief study shows that considering the whole european airspace or only a part of it (namely the french airspace) leads to completely different flows configurations. The origin and destination points for flows over Europe will be airports in most cases, whereas many flows over France may begin at an entry waypoint and/or end at an exit waypoint.

Another interesting statement is that a fairly big number of european flows must be considered if we want to apply our 3D-separation to a significant amount of traffic: the 75 biggest flows represent about 7 percent of the whole traffic. However, more than a half of the 11313 european flows on the chosen day -most of them being "airport to airport" flows -comprise only one flight. It makes no sense to assign permanent, static 3Dtrajectories to such small flows.. The reader may also refer to the TOSCA study ( [START_REF] Maugis | TOSCA-II -WP3: Assessment of the TMA to TMA hand-over concept[END_REF]) for more exhaustive statistics, over several months, showing similar results.

In the french airspace, a smaller number of flows allows to handle a bigger amount of traffic: the 75 biggest flows represent about 40 percent of the traffic. The reason for this is most probably that, when computing the origin-destination flows, the entry and exit waypoints are issued from actual flight plans, where the traffic is already concentrated on pre-defined routes. If the entry and exit waypoints where re-computed as the intersections of direct routes with the french border, the results would most probably be similar to the european configuration.

Several conclusions may be drawn from these statements. First, there is little sense in trying to apply the PROX model (see section III-C) to flows over Europe, as there are very little flights taking off from -or landing at -airports close to the airspace frontier. So only the UNIC or MULTI models are useful when considering european traffic. As the origin and destination are airports in most cases, the entry and exit levels should not be significant inputs of the MULTI model, for most european flows. However, we may still need several 3D-trajectories per link, corresponding to several peak demands for the cruise levels. In the french airspace, different configurations of entry, cruise, and exit may lead to several different 3D-trajectories for a given origin-destination link.

Another conclusion is that the 3D-separation of the main "airport to airport" flows over Europe may not provide a huge reduction in the overall number of conflicts, considering the small amount of traffic that these flows represent. This gives support to the alternative proposed in [START_REF] Maugis | TOSCA-II -WP3: Assessment of the TMA to TMA hand-over concept[END_REF], which consists in grouping the airports in large terminal areas. This would allow to handle a larger amount of traffic with a smaller number of "TMA to TMA" flows, but it implies to organize the traffic within each TMA, and between adjacent TMAs. This is not in the scope of this paper.

Both the A * and evolutionary algorithms were successfully applied to real traffic data (refer to [START_REF] Gianazza | Separating air traffic flows by allocating 3d-trajectories[END_REF]) over France or Europe, but with only one 3D-trajectory per origin-destination link, and with direct routes. We will now present some results on the 3D-separation of traffic flows on a standard routes network, and compare the different models of 3D-flows. at least 20 flights, on the 21st june of 2002. The test configuration is the following:

V. 3D-separation over France

A. 3D-separation on standard routes

• flights follow standard routes, • UNIC model, with one 3D-trajectory per origindestination flow,

• the chosen standard separations are 6 nautical miles horizontally, and 1000 feet vertically.

• the maximum number of different cruise levels per 3D-trajectory is set to 3,

• the floor level if FL145 8 , which means that the first usable cruise level is FL150,

• the first level, as well as the last one, may be lower than the usual minimum value -floor level FL60, instead of FL150 -but on a maximum distance of two tenth of the route length. Table I details the solutions found by the A * algorithm, with the three detection modes. The first line shows the values of the fitness criterion F for each detection mode. Although is is normally used only in the evolutionary algorithm, it was also computed for the A * solutions, because it is a good indicator of the number of interferences and of the trajectory deviations cost.

We see, on the second line, that for the first two detection modes, the algorithm found no solution for one of the trajectories. This is not due to the chosen mode : for other samples on other days, the A * may find a solution for each mode, or fail with another mode. The reason is simply that there is no solution when optimizing each trajectory in turn, with the chosen sequence of flows.

The other lines of the table give the computation time (on a Pentium IV 2.8 GHz), the cost of the trajectory deviations (see III-E), the number of assigned flight levels, and the route elongation.

Let us compare the results on standard routes to previous results on a similar configuration, but with parallel routes ( [START_REF] Gianazza | Separating air traffic flows by allocating 3d-trajectories[END_REF]). With parallel routes, the algorithm assigned between 18 and 20 flight levels, with a route elongation between 0.4% and 0.8%. With standard routes, this route elongation is close to zero, and there are between 19 and 24 assigned flight levels. In this case, the algorithm obviously favors the vertical dimension when solving trajectory interferences. One of the reasons is simply that the alternative routes for a given origin-destination link -issued from all the routes filed in the flight plan -are quite similar. In fact, airlines operators always choose routes of minimum cost across the network, and there are only slight differences between the alternative routes (one or two waypoints, at most).

So, in order to provide more alternatives when using standard routes, we would have to pre-compute, for each origin-destination link, a set of routes among the network which are really different one from another. Figure 3 shows a side view of the 3D-trajectories, for the configuration with standard routes, and the most realistic detection mode (IZONES). The trajectories are viewed from a point located at the west of the french airspace, looking towards the east. This view gives an indication of how the 19 different cruise levels assigned by the algorithm are distributed: the airspace is relatively congested between FL260 and FL290, and also between FL320 and FL370, and less at other levels.

This distribution is highly realistic, compared to other cruise level allocations ( [START_REF] Letrouit | Optimisation du réseau des routes aériennes en Europe[END_REF], [START_REF] Barnier | Graph coloring for air traffic flow management[END_REF]). It shows an efficient use of the available airspace, in the vertical dimension, and brings few constraints on aircraft operations. For each trajectory, the assigned flight levels are as close as possible to the most requested flight level, and it is not allowed to change the cruise level more than twice.

Another general conclusion can be drawn, considering the top and side views of the trajectories accross the french airspace. The trajectories are interwined, and there is little use in trying to split the overall problem into several independant sub-problems.

B. Models comparison

The previous test configuration used the UNIC model of 3D-flows, with one 3D-trajectory per origindestination link. The 72 flows represented slightly more than 40% of the total traffic. Let us now consider more realistic models, with several 3D-trajectories per link. The MULTI model with several flight levels per origin-destination links -depending on the entry, cruise, and exit levels -is illustrated on figure 5. In this configuration, 139 trajectories allow to handle one third of the overall traffic.

The comparison of the three figures 3, 4, and 5, shows that models closer to reality need much more trajectories to handle a same amount of traffic, because of the great variety of entry, cruise, and exit flight levels actually requested when crossing the french airspace.

We have seen, in section IV, that a chosen number of 2D origin-destination links in the french airspace holds more traffic than the same number of links in the european airspace (which are mostly "airport to airport" links). When considering the vertical dimension, this relative advantage is somehow attenuated by the variety of vertical evolutions at the entry or exit points.

VI. 3D-separation over Europe

In [START_REF] Gianazza | Separating air traffic flows by allocating 3d-trajectories[END_REF], the algorithms were applied to the european traffic, with direct routes, on flows holding 10 flights at least, on the 21st june of 2002.

Figures 6, and7 show the top, 3D, and side views of the trajectories found by the A * algorithm for flows holding at least 10 flights, on the same day. The MULTI model is applied, where several 3D-trajectories may be assigned to each origin-destination link. The most realistic detection mode is used, considering the intersections between 3D-tubes defined with uncertainty zones, with real aircraft types.

This flow configuration allows to handle about 12% of the overall traffic with 235 trajectories. The algorithm was unable to find non-interfering trajectory for 18 trajectories. The computation took 4 hours and 38 minutes, on a Pentium IV 3.2 GHz. The evolutionary algorithm is not able to handle so many trajectories yet, at least with reasonable computation times. However, the origin-destination network in Europe is more star-shaped than for the french airspace, so there is good hope that splitting the global problem (the whole set of flows) into several sub-problems (flows interfering one with each other) may lead to good results in the future.

VII. Validation

This section focuses on the validation of the 3Dseparation concept, using fast time simulations.

A. Validation method

The validation has two aims:

• make sure that the 3D-separation is effective,

• and estimate the potential benefits of the 3Dseparation concept. The first point can be checked by considering the conflicts detected between flights following separated 3D-trajectories. No conflict should occur outside the nodetection zones, or except in the specific cases described in III-B.

The potential benefits of the concept could be assessed by several means, including real-time simulations with air traffic controllers. However, it is possible to start with simpler methods, for example by considering the impact on the delay allocation process, or by analysing the number and nature of the remaining conflicts. The reader may refer to the TOSCA study ( [START_REF] Maugis | TOSCA-II -WP3: Assessment of the TMA to TMA hand-over concept[END_REF]) for the first method. The fact that this study considers only 2Dseparation does not significantly affect these results.

The second validation method, which was retained here, consists in running fast-time traffic simulations, first with a reference traffic, and second with a modified traffic, where flights belonging to the main flows follow the computed 3D-trajectories.

The number of detected conflicts allows to compare the two traffic situations, considering that aircraft following a same 3D-trajectories should be sequenced by the departure manager, and should be able to maintain their separation with other along-track traffic.

The reference traffic is not the same when considering either only one aircraft type, or all the aircraft types actually filed in the flight plans. For the DIST-A320 and ITUBES-A320 a single aircraft type (Airbus A320) is considered, disregarding the real aircraft type. For the most realistic detection mode (IZONES), the deposited flight plans are considered as they were.

In the modified traffic, the flights belonging to the main flows follow their assigned 3D-trajectory (direct or standard). The other flights follow their standard route, as declared in their flight plan.

The validation was made only on french traffic, so far. The CATS/OPAS simulations used standard separations of 5 nautical miles horizontally, and 1000 feet vertically.

B. Effectiveness of the 3D-separation

Figures 8 and9 show respectively a top view and a 3D-view of the detected conflicts occurring between flights following different 3D-trajectories. The test configuration is the same as in [START_REF] Gianazza | Separating air traffic flows by allocating 3d-trajectories[END_REF], with flows of at least 20 flights on direct routes, and with a detection using the distance between 3D-segments criterion. The A * algorithm assigned one 3D-trajectory per origin-destination link (UNIC model).

The fast-time simulation detected a total of 1446 conflicts, considering the whole traffic, with flights belonging to the main flows following their assigned 3Dtrajectory, and the other flights following their planned 3D-view of the remaining conflicts between flights on separated 3D-trajectories. route, on the standard network. Only 18 conflicts out of this total occurred between flights following different 3D-trajectories. The figures 8 and 9 show that they involve couples of flights climbing from -or descending to -a same airport, when the detection is inhibited. The only exceptions are at the airspace border, and involve simulated aircraft starting a final descent towards a foreign airport. The fact that the simulator uses latlon coordinates, whereas our algorithms operate with a stereographic projection, introduces some bias in the trajectory computation.

NATURE OF THE DETECTED CONFLICTS

There also remains some along-track conflicts, occurring between aircraft following the same 3D-trajectory, and conflicts involving the rest of the traffic. These results are summarized in table II. In theory, the "alongtrack" conflicts should be solved by each departure manager, through time sequencing.

C. Concept validation

Let us now assess the 3D-separation concept by comparing the number of conflicts occurring in a situation of reference (REF), with the number of conflicts when aircraft belonging to the main flows follow the optimized separated 3D-trajectory (OPT).

ROUTES

Table III shows the results for the three detection modes, and for several values of the floor level in the CATS/OPAS simulator, when separating 71 flows of at least 20 flights, on the 21st june of 2002, with direct routes.

The profit of the 3D-separation is computed by comparing the number of conflict detected in the REF traffic, to the number of conflicts in the OPT traffic, removing the conflicts occurring between aircraft following the same 3D-trajectory (line "same flow" in the table). These conflicts are supposed to be solved by departure managers, through time sequencing. Further validations could focus on this point, by modifying the simulator in order to achieve this time-sequencing.

Anyway, the simulations already show good results, with up to 28% decrease in the number of conflicts, while handling 39% of the traffic on 3D-separated trajectories. The fact that the profit is about the same -or slightly increases -when the floor level becomes higher shows that most of the benefits of the 3D-separation are in the upper airspace.

The validation with the most realistic detection mode (IZONES) shows better results than with the two others. One may have expected the opposite, considering that the detection modes with no uncertainty, and with a single aircraft type, produce thinner trajectories. The route lengthening is smaller in the IZONES case, so it seems that the 3D-separation algorithm favoured vertical deviations when solving the trajectory interferences with this detection mode. This cannot be generalized, but the fact that less additionnal parallel routes spread over the network may explain the better results concerning the number of conflicts. Table V shows the validation results -only above flight level FL195 -for the same day and the same configuration, but with a 3D-network computed by the evolutionary algorithm. Table IV shows similar results, using the A * algorithm but with standard routes. The results are quite similar to those presented in table III. The percentage of traffic handled on the 3D-network was about the same in the three cases.

Several other simulations were made, with the other models of 3D-flows. The detailed results can be found in [START_REF] Gianazza | Optimisation des flux de trafic aérien[END_REF]. They can be summarized as follows, considering (on the first column) the percentage of traffic handled on the 3D-separated network: % traffic Profit 30% 10 to 15% 40% 20 to 30% 50% 35 to 40%

VIII. Conclusion and further work

We have seen that the 3D-separation algorithms could be successfully applied to real traffic data. Previous papers were dedicated to the comparison of the two algorithms proposed to achieve this 3D-separation, first on a toy problem ( [START_REF] Gianazza | Allocating 3dtrajectories to air traffic flows, using a * and genetic algorithms[END_REF]), and second on real traffic ( [START_REF] Gianazza | Separating air traffic flows by allocating 3d-trajectories[END_REF]), with a simplified model assigning only one 3Dtrajectory per origin-destination link. These works show that the global strategy, using the evolutionary algorithm, generally finds better results than the sequential strategy with the A * , but with longer computation times.

In this paper, the first aim was to make one more step towards real life, and propose realistic models of 3Dflows, applied to quite different traffic situations: over France, with a majority of international flights entering or exiting at various flight levels, and over Europe, with most flights taking-off and landing within the airspace boundaries. These models of 3D-flows assign one or several 3D-trajectories per link, depending on the requested entry, cruise, and exit flight levels. The variety of aircraft types and performances is taken into account in the most realistic detection mode, which detects the intersection of 3D-tubes with uncertainty zones.

A full 3D-separation could be achieved for 72 trajectories over France, following standard routes, and using the most realistic detection mode. These trajectories allow to handle about 40% of the traffic, assigning only one trajectory per link. The proposed methods allow an efficient use of the available airspace -the flight levels distribution is highly realistic, when compared to other cruise level allocation methods ( [START_REF] Letrouit | Optimisation du réseau des routes aériennes en Europe[END_REF], [START_REF] Barnier | Graph coloring for air traffic flow management[END_REF]) -, and they bring very few constraints on airlines operations, with only three different cruise levels per trajectory, at most.

We have also underlined the difficulty to handle big amounts of traffic on the 3D-network, especially when using a realistic model of 3D-flows. When considering the whole european airspace, the difficulty lies in the high number of "airport to airport" links, holding each a relatively small amount of traffic: 235 trajectories are needed to handle only 12% of the european traffic. When focusing on a smaller airspace (namely France), a greater number of 3D-trajectories per origin-destination must be computed, due to the variety of entry and exit flight levels: 139 trajectories were needed to handle one third of the french traffic, with the most realistic model of 3D-flows.

The ultimate aim of this paper was to assess the 3D-separation concept itself. The fast-time simulations, using CATS/OPAS on french traffic, show several significant results. The first one is that most benefits of the 3D-separation are in the upper airspace. This was demonstrated by considering three different floor flight levels in the simulations.

A second result is that the benefit of the 3D-separation is closely related to the amount of traffic handled on the 3D-network, and not to the method used to produce this network. Several runs with different configurations -with the A * or the evolutionary algorithm, on direct or standard routes -show a similar decrease in the number of detected conflicts, when considering a same amount of traffic.

The main result is that the potential benefit of the 3D-separation is high, provided along-track conflicts are solved by departure managers. The simulations show up to 40% decrease in the number of conflicts when handling half of the traffic on the 3D-trajectories network. These good results must be mitigated by the difficulty to handle such amounts of traffic with a reasonable number of trajectories, especially when using realistic models, and when considering the "airport to airport" flows over Europe.

However, as shown in the TOSCA study ( [START_REF] Maugis | TOSCA-II -WP3: Assessment of the TMA to TMA hand-over concept[END_REF]), the number of conflicts is not the only criterion that must be considered. According to this study, removing even a small amount of traffic from the slot allocation process may lead to significant reductions in the cumulated ground delays, provided there is no significant impact on the sector capacity. So assigning separated 3Dtrajectories to about 10% of the overall european traffic may not lead to a significant reduction in the number of conflicts, but it may well reduce the cumulated delays.

Further work may deal with the improvement of the evolutionary algorithm, by splitting each problem (a set of flows) into several sub-problems (flows interfering one with each other). Other improvements may be the definition of large TMAs, in order to handle more traffic with less flows, in the European context. A last developpement, which is already under course, consists in introducing the time dimension in the algorithms, in order to make some pre-tactical 4D-trajectory planning for trains of aircraft having similar performances.

Key words

Fig. 1 .

 1 Fig. 1. Example of several flight profiles on a same flow.

Figure 2 Fig. 2 .

 22 Figure2shows a top view of the 3D-trajectories found by the A * algorithm in the french airspace, with the most realistic detection mode (IZONES detection, with 3Dtubes and uncertainty zones), for the 72 flows comprising

Fig. 3 .

 3 Fig. 3. Side view (from the west) of the A * 3D-trajectories for the FR-JUNE21-UNIC-A*-20-IZONES-STD configuration (altitudes in feet).

Fig. 4 .

 4 Fig. 4. Side view (from the west) of the A * 3D-trajectories for the FR-JUNE21-PROX-A*-15-IZONES-PAR (altitudes in feet).

Figure 4 Fig. 5 .

 45 Figure4illustrates the PROX model, with additionnal 3D-trajectories assigned to flights taking off from -or landing at -nearby foreign airports. This configuration holds 95 3D-trajectories, and represents about 42% of the traffic. The distance criterion used to select nearby airports is 70 nautical miles from the border.

Fig. 6 .Fig. 7 .

 67 Fig. 6. Top view of the A * 3D-trajectories for the EU-JUNE21-MULTI-ASTAR-10-IZONES-PAR (distances in NM).

Fig. 8 .

 8 Fig. 8.Top view of the remaining conflicts between flights on separated 3D-trajectories.

  Fig. 9.3D-view of the remaining conflicts between flights on separated 3D-trajectories.

TABLE I 3D

 I

-SEPARATION RESULTS, USING THE A * ALGORITHMS ON FLOWS OF 20 FLIGHTS AT LEAST, OVER FRANCE, ON STANDARD ROUTES (21ST JUNE 2002, ONE TRAJECTORY PER FLOW).

  Air traffic flows optimization, 3D-separation, Evolutionary algorithms, A * Biographies David Gianazza graduated from the Ecole Nationale de l'Aviation Civile (ENAC) in 1989 as an engineer. After beginning his career in the operational field in Brest ATC center, he obtained a master degree in computer science in 1996, and became deputy head of the division "Computerassisted control tools" of the technical service STNA. He is currently working at the Global Optimization Laboratory (LOG), a laboratory supported by CENA and ENAC, and holds a Ph.D. in computer science (2004). Nicolas Durand graduated from the Ecole Polytechnique de Paris in 1990 and from the Ecole Nationale de l'Aviation Civile (ENAC) in 1992. He has been a design engineer at the Centre d Etudes de la Navigation Aérienne (CENA) since 1992 and holds a Ph.D. in computer Science (1996).

TMA: Terminal Area

Testing Operational Scenarios for Concepts in ATM

We will deliberately avoid to use the term conflict, which, in the aviation community, refers to the fact that two aircraft are (or will be) closer than the allowed separation minima. A conflict is detected by considering the horizontal and vertical distances between points, whereas our trajectories are sequences of 3D-line segments, or 3Dtubes.

"Europe" refers here to the airspace described in the Eurocontrol database

14500 feet above isobar 1013.25 hPa


Charles-Edmond Bichot

Nicolas Durand

Airspace block organization with metaheurisitics and partitioning packages

In this paper, different metaheuristics applied on an air traffic control problem. This problem is a graph partitioning problem. It can be solved by classical methods which are spectral and multilevel methods. State-of-the-art public-domain graph partitioning packages, CHACO and METIS are used to resolve it. A comparison between results return by these packages and metaheuristics implementations is made for different objective functions of the literature. Metaheuristics used are simulated annealing, ant colony and a new one called fusion fission developed in the LOG laboratory. Experimental results show that metaheuristics find better results than classical packages.

I. Introduction

In this paper, different metaheuristics applied on an air traffic control problem are presented. This problem is a graph partitioning problem. It can be solved by classical methods which are spectral and multilevel methods. State-of-the-art publicdomain graph partitioning packages, CHACO [START_REF] Hendrickson | The Chaco user's guide[END_REF] and METIS [START_REF] Karypis | MeTis: A software package for partitioning[END_REF] are used to resolve this problem. A comparison between results return by these packages and metaheuristics implementations is made for different objective functions. However, whereas classical methods are designed for particular objective function, that can hardly be modified, metaheuristics can easily be changed of objective function, which is an advantage for this problem.

The air traffic control problem is presented in section II. Different objective functions already used to solve partitioning problems are described in section III. In section IV are shortly presented three metaheuristics, which are simulated annealing, ant colonies and a new one developed in the LOG laboratory, fusion fission. The comparison between results of metaheuristics and classical libraries is presented in section V.

II. An Air Traffic Control problem

"The primary purpose of the Air Traffic Control (ATC) system is to prevent a collision between aircraft operating in the system and to organize and expedite the flow of traffic" [START_REF]Air Traffic ControL[END_REF]. The first objective of ATC is safety, the second is efficiency.

The Functional Airspace Block Optimized Process (FABOP) project consists in dividing the European airspace into blocks. Let us explain some air traffic control mechanisms. An air traffic controller supervises the traffic in an limited area, called air traffic sector. Controllers are qualified for working on a set of sectors, which is called a functional airspace block. The FABOP project consists to partition the European airspace into functional airspace blocks. Actually, just a few blocks are crossing countries' frontiers. In this paper we study a new organization of blocks based on flows of aircraft and not on countries' frontiers.

Controllers only know air traffic sectors on which they are qualified, and rarely other sectors. Because "controller-controller coordination is easier and more effective inside an ATC unit (a block) than between ATC units" [START_REF] Hallgren | Restructuring european airspace: functional airspace blocks[END_REF], we try to maximize flow of aircraft inside blocks and to minimize flow of aircraft between blocks. For human factors, each block must have the same "size". This is the aim of the objective function to minimize.

Let us describe more formerly the problem. We compare each air traffic sector to a vertex and each flow of aircraft between sectors to an edge. We have a graph G = (V, E) with a vertex set V and edge set E.

Each edge e = (v 1 , v 2 ) has a weight w(e) which is the flow of aircraft which fly from v 1 to v 2 and vice versa. Each vertex v i has a weight, which is the sum of the weights of connected edges plus aircraft departures and landings if the sector is connected with an air-port. A partition of G into k distinct partitions must respect the following constraints :

P k (G) must be a partition of G into k non-empty subgraphs V 1 , . . . , V k with ∀ i, j included in 1 . . . k, i = j, V i ∩ V j = ∅ and k i=1 V i = V .
The problem is to partition the vertices of the graph G into k roughly equal parts (or blocks), such that a certain objective function is optimized. Intuitively, equal parts are parts with the same number of vertices, ie. blocks should have the same number of sectors. Because the number (flow) of aircraft which go through a sector is very different for each sector, we can not use this equality between parts. More probably, comparing the amount of flows of aircraft between the sectors of a block with the same amount of flows with another block is better. The number of conflicts or potential conflicts in a sector increases considerably the difficulty for a controller to coordinate aircraft. Thus, the computation of the equality should take into account the number of conflicts or potential conflicts. The size and the design of a sector influence the number of coordinations, maybe the computation of the equality should take into account this too. Other operationals constraints can be easily find. As we can see, finding what is the equality criteria between parts is difficult.

In the experimental tests, the number of vertices is |V | = 759 and the number of edges is |E| = 3, 165. This number of vertices is the number of air traffic sectors of the European countries core area defined in [START_REF] Bichot | A theoretical approach to defining the european core area[END_REF]. This area is the set of countries which have the highest flows of traffic in Europe. The countries core area is composed of Germany, France, United Kingdom, Switzerland, Belgium, Netherlands, Austria, Spain, Denmark, Luxembourg and Italy.

We have seen that finding equal parts for this problem is difficult. Indeed, like image segmentation, we should use objective functions which itself equalize the different parts of the partition.

III. Objective functions

In this section we present objective functions used for partitioning problems. The simplest and the oldest of them is the Cut function, which is the sum of edges' weight between partitions. This objective function is designed for spectral graph partitioning.

Let A ∈ P k (G), V -A = {u ∈ V, u / ∈ A}, we define cut(A, V -A) = u∈A,v∈V -A w(u, v) (1)
and

W (A) = u∈A,v∈A w(u, v) (2)
Thus,

Cut(P k (G)) = A∈Pk(G) cut(A, V -A) (3)
Hagen and Kahng [START_REF] Hagen | New spectral methods for ratio cut partitioning and clustering[END_REF] defined the ratio cut :

Rcut(P k (G)) = A∈Pk(G)   B∈Pk(G)-{A} cut(A, B) |A|   (4
) which removes the requirement |A| = |B| and minimizes cut(A, V -A) when the number of vertices in each part is roughly equal.

Shi and Malik [START_REF] Shi | Normalized cuts and image segmentation[END_REF] propose the normalized cut :

N cut(P k (G)) = A∈Pk(G) cut(A, V -A) cut(A, V -A) + W (A) (5)
which minimizes cut(A, V -A) while maximizing

Assoc(A, V ) = cut(A, V -A) + W (A)
, the sum of the weights of each partition. And the min-max cut function was introduced in [START_REF] Chris | A min-max cut algorithm for graph partitioning and data clustering[END_REF] :

M cut(P k (G)) = A∈Pk(G) cut(A, V -A) W (A) (6)
which minimizes cut(A, V -A) while maximizing W (A) which is the sum of the weights of edges between vertices of the same partition.

The M cut objective function seems the most appropriate of the objective functions presented, regards to the objective presented in section II : maximizing flows of aircraft (edges weight) inside blocks (partitions) and minimizing flow of aircraft between blocks.

IV. Metaheuristics

The three metaheuristics described in this section are more precisely explained in [START_REF] Bichot | Optimisation par fusion et fission. application au problème du découpage aérien européen[END_REF]. More information about a new method called fusion fission can be found in [START_REF] Bichot | A metaheuristic based on fusion and fission for partitioning problems[END_REF].

A. Simulated annealing

This metaheuristic was first introduced in [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF]. Let us present very shortly the simulated annealing method. The fundamental idea is to allow moves resulting in solutions of worse quality than the current solution in order to escape from local minima.

The probability of doing such a move is decreased during the search. In metallurgy, a very hot metal is cooled very slowly to increase its solidity. In the same way, vertex are moved among partitions, one by step. The temperature T is decreased when moves are increasing the objective function (T tmax-tmin tmax with t max (t min ), maximal (minimal) temperature). The objective function e gives the "energy" of the solution. The result of a move of a vertex which changes of partition, builds a new move s ′ . s ′ is kept if exp e(s)-e(s ′ ) T is upper a random number in [0, 1] or if the objective function is increasing. Else, the old state s is kept. The algorithm stops when T ≤ t min .

B. Ant colony

Ant colony optimization is inspired by the foraging behavior of real ants. This metaheuristic proposed by Dorigo is explained in [START_REF] Dorigo | The ant system: Optimization by a colony of cooperating agents[END_REF]. The algorithm uses the ability of ants to find the shortest path between food source and their nest. While walking from food sources to the nest and vice versa, ants deposit a substance called pheromone on the ground. When they decide a direction to go, they choose with a higher probability paths that are marked by stronger pheromone concentrations.

The ant colony algorithm is based on three (one optional) steps. While a termination condition is not satisfied, the three steps are executed, but not necessarily in the following order :

• The first step is the ants motion. Ants are moving through nodes of the graph G by applying a stochastic local decision policy which uses pheromone values and a local heuristic. While moving, the ant keeps memory of the path it was walking on the graph. • The second step consists in updating pheromones. Ants always update the pheromone trails they are using. But if a path lead to "food" (a local solution), the ant can update backward the path it used by using its memory. Finally, like real pheromones, pheromone trail intensity decreases over the time (to avoid convergence into a sub-optimal region). • The last step is optional. It is used to implement centralized actions which cannot be performed by single ants. The adaptation of ant colony to the partitioning problem uses k colonies, one for each partition of the graph. These colonies are competing for food. It is important to notice that an ant can only distinguish pheromones of its colony. The weights of vertices correspond to ants food. Ants put down pheromones on edges. A vertex is owned by a colony if the sum of his pheromones on adjacent edges is greater than for other colonies. A local heuristic forces ants to explore edges which have no pheromone. Ants can go where they want, so ants from different colonies can be in the same vertex at the same step. Thus, the connectivity of sets is not forced. As connected sets often produces best results, we do not need to force this connectivity.

To conclude, the approach of k-partitioning with ant colony algorithm is very different than precedent works [START_REF] Kuntz | A colony of ant-like agents for partitioning in vlsi technology[END_REF], [START_REF] Langham | A multilevel k-way partitioning algorithm for finite element meshes using competing ant colonies[END_REF].

C. Fusion fission

The fusion fission method is a new method developed at the LOG laboratory. Its aim is graph partitioning. The fusion fission method is inspired by nuclear fusion and fission. The organization of a molecule can be compared to a k-partition. The molecule is the graph G, nucleons are vertices and atoms are partitions. Fusion and fission are two processes which organize atoms. Fusion is the process which assembles two atoms in one. On the contrary, fission is the process which breaks atoms into two parts. The fusion fission method consists in assembling and breaking atoms successively. Like in the natural process, fusion and fission can eject alone vertices (atoms) from a partition. Such vertices can be added to a different partition, or cut another partition in two (chained fission).

Because the number of partitions continuously change, the energy (returned by the objective function) is smaller for a small number of partitions. Thus we use a function to increase the value of the objective function if the number of partitions is not k.

The fusion fission algorithm is presented figure 1. cpart is the partition of G into sets of vertices. cpart is initialized with a near k-partition of G. t is the temperature. The higher the temperature, the easier the fusion of big atoms and the easier the fission of small atoms. part i is a partition of cpart. part i is randomly chosen between all partitions of cpart. A new partition npart of G is made by f usion or f ission. The laws correspond to probability lists, which are probabilities to eject zero, one, two or three nucleons as described upper. Then nucleons (in ln, a list of nucleons) are added to another partition, or, in the fission case, if the temperature is high (high energy function), these nucleons can cut partitions. The laws are updated if the result of the objective function is lower than the preceding partition. The function which decreases temperature is decrease(t) = t tmax-tmin nbt where nbt is the number of steps of the temperature decrease. The best result is memorized in best part. If the temperature is lower than a minimal temperature, the algorithm is run with the best partition best part and the upper temperature. Else, it is run with the partition npart find and the new temperature new t. The process of choice between fusion and fission is function of the number of nucleons x of the atom choose :

choice(x) =      1 if x > n + 1 2α(t) 0 if x < n -1 2α(t) (x -n)α(t) + 1 2 else
where n = nbv k , nbv is the number of vertices of the graph, k is the number of partitions, and α(t) = q tmax-t tmax-tmin + r where q, r are adjusted by the user.

V. Results

Classical partitioning methods were first used to solve the air traffic control problem. Kenighan and Lin [START_REF] Kernighan | An efficient heuristic procedure for partitioning graphs[END_REF] have created a very efficient algorithm, which uses a local optimization strategy. Spectral methods have been popularized by the work of Pothen, Simon and Liu [START_REF] Pothen | Partitioning sparse matrices with eigenvectors of graphs[END_REF]. Multilevel methods have been developed by Hendrickson and Leland [START_REF] Hendrickson | A multi-level algorithm for partitioning graphs[END_REF] and by Karypis and Kumar [START_REF] Karypis | A fast and high quality multilevel scheme for partitioning irregular graphs[END_REF]. In this example, the CHACO [START_REF] Hendrickson | The Chaco user's guide[END_REF] library was used. This library includes Kernighan-Lin algorithm, a spectral method and the multilevel method of Hendrickson and Leland. The METIS [START_REF] Karypis | MeTis: A software package for partitioning[END_REF] library was also used. This library includes the multilevel method of Karypis and Kumar.

CHACO's objective is to minimize the Cut objective function, and minimize the difference between the number of vertices in each partition. METIS's objective is to partition the vertices into k disjoint subsets such that the sum of the vertex weights in each subset is the same, and to minimize the Cut objective function. The metaheuristics algorithms use the M cut objective function which is the most appropriate for the air traffic problem (see section III). In table I the best results of the different methods are presented. These results are computed for a partition into 32 sets, on a 3 GHz Intel Pentium 4 running with Linux. The objective function of the three metaheuristics is M cut. CHACO spectral method uses RQI/Symmlq eigen solver, with the octasection partitioning method and multiple Kernighan-Lin refinement. CHACO multilevel method uses the bisection partitioning method. METIS multilevel method uses pmetis with default parameters. kmetis was also tested but without better results. Note that, if spectral and multilevel algorithms use local refinement (Kernighan-Lin), metaheuristics do not. The best results for each objective functions are strewn in bold. 5 have disproportionate shapes and sizes. Especially, the block in the center of France, which has a lot of sectors (88, compared to an expected value which is around 23.8). This result is irrelevant for air traffic control, because no controller can be qualified for so many sectors.

Table II presents the variance σ(spb) of the number of sectors per block, the variance σ(vw) of the sum of vertex weights W (A), per block, and the variance σ(ewbb) of the sum of edges weights between blocks cut(A, V -A), per block. Expected values corresponding to these variances are: E(spb) = 23.8, E(vw) ≃ 2700, and E(ewbb) ≃ 3500. Because of its goal, the CHACO software produces the smallest variance of the number of sectors per block. But with 1,446 aircraft to control for the lowest block and 10,346 aircraft for the highest, it seems that this result is irrelevant for air traffic control too. METIS multilevel partitioning methods have the lowest variance of W (A) and cut(A, V -A). These results correspond to METIS goal. Considering METIS results, the maximal number of sectors in a block is 48, which makes these results more relevant.

Thus, a new approach of the problem is necessary. Future work on the air traffic problem will deal with minimizing the M cut objective function, but with the following constraints :

1) σ(spb) < 6 2) σ(vw) < 500 3) σ(ewbb) < 500 This defines a multi-objective problem.

VI. Conclusion

An application of three metaheuristics (simulated annealing, ant colony and fusion fission) to an air traffic control problem was presented in this paper. This air traffic control problem is a k-partitioning problem. These metaheuristics were compared to the CHACO and the METIS libraries which are classical methods to solve partitioning problems (Kernighan-Lin, spectral and multilevel methods). We compare results of these methods to results of metaheuristics with the M cut function. Compared to all of the objectives functions, metaheuristics return better results, especially the fusion fission algorithm. But the best result found with fusion fission is irrelevant for air traffic control. The analysis of CHACO and METIS partitioning results showed that these results are not relevant either. Consequently, to be applied, a solution of the air traffic control problem must respect some constraints, while minimizing the M cut objective function.

Fig. 1 .Fig. 2 .Fig. 3 .Fig. 5 .Fig. 6 .Fig. 7 .

 123567 Fig. 1. Partitioning result of fusion fission (FL240)

  In the same way, figure 2, 6 and 3, 7 present the partitioning results of the CHACO spectral algorithm and the METIS multilevel algorithm. Figure 4 and 8 present real partitions of the European airspace on February 2002. The three are vertical cuts of the European countries core are, at flight level 380 (11,000 m). Regarding to blocks of other figures, blocks of figure

		TABLE II
		Variances
		σ(spb) σ(vw) σ(ewbb)
	CHACO Spectral	0.4	1448	1680
	CHACO Multi.	0.4	1573	1685
	METIS Multi.	8.5	384	779
	S. annealing	11.4	1392	1778
	Ant colony	12.8	1500	1901
	Fusion Fission	15.7	2620	2567
	Regards to this results, the fusion fission is the best
	algorithm (with Rcut nearest the multilevel method).
	If METIS and CHACO software are extremely fast (a
	few seconds to compute), metaheuristics are running
	30 minutes to give these results.
	Figure 1 and 5 details the map of the partitioning
	result of the fusion fission algorithm corresponding
	to table I result.