CASSOS : Computer-assisted sectors opening schedules
La page d'acceuil de CASSOS est également disponible en
français.
Summary
- Acronym: CASSOS
- Project name: Computer-assisted sectors opening schedules
- Start date: 1999
- End date: -
Description
The aim is to find optimal combinations of air traffic sectors, taking the traffic flows as input, and considering the airspace capacity constraints, and also the maximum number of control positions that can be manned at each time of the day.
In this problem, the traffic is not considered as a variable, but as input data.
So we will not use a departure slots allocation to adapt the traffic to the available capacity, but instead, we shall recombine elementary sectors in order to offer a maximum capacity to the existing trafic demand.
In what follows, the term sector shall either apply to an elementary sector, or to a group of elementary sectors assigned to a controller's working position.
Beyond the main objective, there are in fact several sub-objectives, which may be conflicting. For each time step, we are looking for a combination for which:
- the traffic does not exceed, or the least possible, the capacity of each sector,
- the traffic load is well balanced between the sectors assigned to the controller's working positions,
- the number of armed controller's positions is minimum,
- and this number does not exceed the number of available positions (this is an option).
In fact, we shall minimize a cost related to, by order of importance, the excessive traffic over-loads, the number of armed working positions, the excessive under-loads, and, at last, the acceptable over-loads and under-loads.
Some tolerance margins are defined around the nominal capacity values.
The adjective acceptable applies when the traffic load stays between these margins.
Several methods are used:
-
classical tree search methods (A*, Branch & Bound), which explore the tree of all possible sectors combinations,
-
and an evolutionary algorithm, applied to a population of sectors combinations.
The workload indicators and thresholds used by these algorithms are the ones used in the operational field:
-
the flows of aircraft entering a sector during a chosen period of time (one hour for example) starting at a given time t ,
- the sector capacities , which are threshold values of the entering flows, beyond which the sector is considered as being overloaded.
Progress
The difficulty of the problem have been assessed.
The number of sectors combinations highly increases with the number of sectors, in such a way that the use of an evolutionary algorithm is justified.
However, the number of combinations obtained with the subset of pre-defined operational groups of sectors described in the french airspace databases is small enough for classical tree search methods.
As a first step, the evolutionary algorithm was applied to a test-case, with no pre-defined groups.
Then the tree search algorithms and the evolutionary algorithm were applied to real data, recorded in the five french Air Traffic Control Centers.
A specific graphic interface have been implemented, with the following input parameters:
- the date,
- the chosen control center,
- the type of traffic (initial or final demand, real past traffic),
- the tolerance margins,
- the maximum number of available positions at each time of the day
- the time step,
- the time window used to compute the entering flows.
The program's output is an optimized sectors opening schedule (as shown in the next examples).
For now, the real opening schedules are produced manually in the air traffic centers by the FMP (Flow Management Position) operators, using a pre-defined, and small, subset of all the possible sectors combinations.
The proposed algorithms search among all the possible combinations.
The potential profits provided by the optimized schedule have been assessed by simulating a departure slots allocations, over France only, in two situations:
- on the one hand, the traffic regulation takes as input the opening schedule really deposited by the FMP on that day,
- and, on the other hand, the traffic is first smoothed, considering that all elementary sectors are armed, and then an optimized opening schedule is processed with this smoothed traffic as input.
The comparison of these two strategies on one day of traffic shows a decrease of 69% of the cumulated delays, while using 20% less ressources (the ressources are represented by the cumulated time during which the control positions are armed).
However, these good results are only an indication of the algorithms efficiency, but one must not expect such profits in case of a future use of these algorithms in the operationnal field.
In fact, we have so far made the implicit hypothesis that the indicators used in the operationnal field (namely the entering flows), are related to the controllers workload.
But this is not the case , as many people in the ATC and ATM community know.
This statement has been confirmed by a short statistical study, on year 1999, of the indicators values around the moments when armed sectors were split into smaller sectors.
In conclusion, the proposed algorithms are quite efficient to solve our problem, but there still remains to find out some indicators and thresholds, more related to the controllers workload than the entering flows and the sector capacities.
This last point is the subject of the S2D2 project, in collaboration with the LEEA.
Example
The following figure shows the opening schedule computed for Bordeaux Air Traffic Control Center, on one day of traffic, with a time step and a time horizon of one hour, and tolerance margins of 10% on the nominal capacities.
In this example, there is no constraint on the maximum number of available controller's working positions.
The color code is the following:
- green, when the traffic load is below the nominal capacity minus the lower tolerance margin,
- yellow, when the load is between the tolerance margins,
- red, when the load is higher than the nominal capacity plus the upper tolerance margin.
In this schedule, each column is a sectors configuration, computed for a one hour time window.
The number of controller's working positions is written on top of each column.
Each box represents a sector (i.e. an elementary sector or a group of sectors) of the configuration, with the sector's name, the traffic load, and the nominal capacity.
The values displayed under the time axis are the values of an indicator allowing to compare different configurations.
There are four sectors excessively overloaded (in red).
These are elementary sectors, and therefore it is not possible to split them into smaller sectors.
The only possible way to avoid these overloads would be to smooth the traffic.
Example with constraints
Here is an example of an optimal schedule, computed with the same input parameters, but with constraints on the maximum number of available working positions.
These constraints are issued from the opening schedule that was actually deposited by the Bordeaux center on this day.
This deposited schedule is a prediction made by the FMP operators, two days before D-day.
The number of available positions depends on the number of controllers on the site at each time of the day.
The constraints are displayed as black horizontal bars, or blue bars when the number of sectors of the configuration equals the constraint.
There are two other excessive overloads (in red), between 4 an 5 a.m. (UTC), in addition to the four overloads that concern elementary sectors (see the previous example).
The reason of these two overloads is that there are not enough working positions to split the overloaded sectors.
Another example, with constraints
In this example, we consider the number of working positions that were actually armed in Bordeaux center, on the considered day.
The optimal schedule is highly constrained, and shows several excessive overloads.
This confirms that the chosen indicators (entering flows and capacities) are not realistic, and not related to the actual controllers workload.
Software
CASSOS is written in Objective Caml, and the graphic interface in OcamlTk.
The code is not public domain.
Links
Main publications
Recherche d'un optimum dans la configuration des regroupements de secteurs d'une salle de contrôle. Premiers résultats. David Gianazza .
Note STNA 99.0177
(1999/03/19)
All publications of the lab may be found in
here.