CASSOS : Computer-assisted sectors opening schedules
CASSOS homepage is also available in
english.
Résumé
- Acronyme: CASSOS
- Nom du projet: Computer-assisted sectors opening schedules
- Date de début: 1999
- Date de fin: -
Description
Il s'agit de construire des configurations optimales de secteurs aériens, en fonction des flux de trafic, des contraintes de capacité des secteurs, et éventuellement du nombre maximum de positions de contrôle qu'il est possible d'armer à chaque instant de la journée.
Dans ce problème, le trafic n'est pas une variable d'ajustement, mais est considéré comme une donnée d'entrée.
On ne régule donc pas le trafic, et on joue simplement sur la manière de regrouper les secteurs élémentaires.
Dans ce qui suit, le terme secteur s'entend comme un secteur élémentaire ou comme regroupement de secteurs, affecté(s) à une position.
L'objectif général recouvre en fait plusieurs objectifs qui peuvent être contradictoires.
On cherche, pour chaque pas de temps, une configuration pour laquelle :
- le trafic ne dépasse pas, ou le moins possible, la capacité de chaque secteur armé,
- la charge de trafic soit la plus équilibrée possible entre les différents secteurs armés,
- tout en armant le moins possible de positions de contrôle, dans un souci d'efficacité,
- en respectant éventuellement (c'est une option) un nombre maximum de positions disponibles.
En pratique on cherche à minimiser un coût prenant en compte, par ordre d'importance, les dépassements excessifs de capacité, le nombre de positions ouvertes, les sous charges excessives, et en dernier lieu les dépassements et sous-charges acceptables.
On définit donc des marges de tolérances, inférieure et supérieure, autour des valeurs de capacité, entre lesquelles les dépassements ou les sous-charges seront considérées comme acceptables, et plus faiblement pénalisées.
Plusieurs types de méthodes sont utilisées :
-
des méthodes classiques de parcours d'arbres (A*, Branch & Bound), qui explorent l'arbre des configurations possibles,
-
un algorithme évolutionnaire, opérant sur une population de configurations.
Les algorithmes opèrent sur les indicateurs et les seuils actuellement utilisés dans le milieu opérationnel, à savoir :
-
les flux entrants , c'est-à-dire le nombre d'avions entrant dans le secteur considéré, à partir d'un instant t , dans une fenêtre temporelle fixée,
- les capacités , qui sont des seuils au-delà desquels les secteurs sont considérés comme surchargés.
Etat d'avancement
La première étape a consisté à estimer la difficulté du problème.
Le nombre de configurations possibles augmente de façon fortement combinatoire en fonction du nombre de secteurs.
Cela justifie l'utilisation d'une méthode adaptée aux problèmes difficiles.
Cependant, en se restreignant aux regroupements définis dans les données opérationnelles des centres de contrôle français, le nombre de combinaisons possibles reste accessible à des méthodes d'exploration d'arbres.
Dans un premier temps, l'algorithme évolutionnaire a été testé sur un cas théorique.
Puis, les algorithmes d'exploration d'arbre et l'algorithme évolutionnaire ont été appliqués aux données réelles archivées, pour les cinq centres de contrôle aérien français.
Une interface spécifique a été développée, dont les paramètres d'entrée sont :
- la date,
- le centre de contrôle choisi,
- le type de trafic (demande initiale, finale, ou trafic réalisé),
- les tolérances sur les capacités,
- le nombre maximum de positions de contrôle disponibles à chaque instant de la journée,
- le pas de calcul,
- l'horizon temporel pour le calcul des flux à travers les secteurs (qui peut être différent du pas de calcul).
Le programme produit des schémas prévisionnels d'ouverture des secteurs de contrôle (illustrés ci-dessous), optimaux en fonction des critères choisis.
Dans l'opérationnel, ces schémas sont actuellement élaborés manuellement, à partir d'un jeu réduit de configurations de secteurs, par les opérateurs FMP (Flow Management Position) des centres de contrôle.
Les algorithmes que nous proposons explorent l'ensemble de l'espace des configurations possibles.
Une estimation des gains potentiels apportés par le schéma optimisé a été réalisée, en simulant une régulation du trafic, sur la France uniquement, selon deux stratégies :
- d'une part, une régulation du trafic en fonction du schéma réellement déposé,
- et, d'autre part, une régulation avec tous les secteurs élémentaires armés, suivie d'une optimisation du schéma de regroupement avec le trafic lissé.
La comparaison des deux stratégies sur une journée de trafic montre, pour le schéma optimisé, un gain de 69% sur le cumul des délais au décollage, en utilisant 20% de ressources en moins (celles-ci étant décomptées en temps d'activité cumulé des positions de contrôle).
Ces excellents résultats ne sont toutefois qu'une indication de l'efficacité des algorithmes, mais il ne faut en aucun cas espérer de tels gains de productivité lors d'une éventuelle mise en place opérationnelle .
En effet, nous avons jusqu'ici implicitement considéré que les indicateurs utilisés en opérationnel (les flux entrants) étaient représentatifs de la charge de travail du contrôleur sur sa position de contrôle.
Or, ce n'est pas le cas , comme le savent bon nombre de professionnels de l'ATC et de l'ATFM.
Cette constatation a été confirmée par une étude statistique sommaire, sur l'année 1999, des valeurs des indicateurs de flux entrants autour des instants de dégroupements des secteurs.
Nous disposons donc d'algorithmes efficaces pour la résolution de notre problème, mais il reste à définir des indicateurs et des seuils plus pertinents que les flux entrants et les capacités.
Ce dernier point est le sujet du projet S2D2, mené en collaboration avec le LEEA.
Exemple sans contraintes
La figure suivante montre le schéma prévisionnel d'ouverture des secteurs calculé pour le centre de Bordeaux, sur une journée de trafic, avec un pas de temps d'une heure, un horizon temporel d'une heure, et des tolérances de 10% par rapport aux capacités nominales.
Dans cet exemple, aucune contrainte n'est fixée sur le nombre maximum de positions de contrôle disponibles.
Le codage des couleurs est le suivant:
- vert quand la charge est inférieure à la capacité nominale moins la tolérance inférieure,
- jaune quand la charge est à l'intérieur des tolérances,
- rouge quand la charge est supérieure à la capacité nominale plus la tolérance supérieure.
Sur ce schéma, chaque colonne représente une configuration de regroupements de secteurs, calculée pour une tranche horaire.
Le nombre de positions ouvertes est reporté en haut de la colonne.
Chaque case représente un secteur armé (soit un secteur élémentaire, ou un groupe de secteurs élémentaires), avec le nom du secteur, la valeur du flux traversant le secteur, et la capacité nominale.
Les valeurs présentée sous l'axe des temps représentent un critère d'évaluation permettant de comparer différentes configurations.
On constate qu'il reste quatre surcharges excessives, en rouge.
Elles concernent quatre secteurs élémentaires, qu'il est donc impossible de "dégrouper" (traduire : couper en deux autres secteurs plus petits), et pour lesquels la recombinaison des secteurs élémentaires n'apporte aucun gain.
La seule possibilité pour éviter ces surcharges consisterait à réguler le trafic.
Exemple avec contraintes
Cet exemple illustre le calcul d'un schéma prévisionnel optimal, dans la même configuration que précedemment, mais en imposant une contrainte sur le nombre de positions de contrôle disponibles.
Ici, les contraintes sont issues du schéma prévisionnel réellement déposé par le centre de Bordeaux ce jour-là.
Ce schéma est une prédiction faite par les opérateurs FMP, deux jours avant le jour J.
Le nombre de positions qu'il est possible d'ouvrir est fonction du tour de service, et donc des personnels présents sur le site.
La courbe du nombre de positions disponibles est représentée par les traits noirs ou bleus, cette dernière couleur traduisant une saturation de la contrainte en nombre de positions.
On constate deux dépassements excessifs de capacité (en rouge) supplémentaires, par rapport à ceux de l'exemple précédent, entre 4h et 5h du matin (heure UTC).
Ces surcharges sont dues au fait qu'il n'y a pas suffisamment de positions disponibles pour "dégrouper" les secteurs surchargés.
Un deuxième exemple avec contraintes
Dans cette exemple, nous avons pris comme contraintes le nombre de positions effectivement armées à Bordeaux, le même jour.
On constate un nombre important de dépassements excessifs des capacités des secteurs, ce qui confirme encore, s'il en était besoin, que les flux entants horaires ne sont pas des indicateurs réalistes de la charge de travail.
Logiciel
CASSOS est écrit en Objective Caml, et l'interface graphique en OcamlTk.
Le code n'est pas dans le domaine public.
Liens utiles
Principales 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)
Toutes les publications du LOG sont disponibles
ici.