FR 3049743 A1 20171006 FR 1652780 A 20160331 1 DOMAINE TECHNIQUE La présente invention appartient au domaine de la gestion de mouvements d'aéronefs en l'air et au sol dans un espace géographique limité. Elle concerne plus particulièrement un procédé de gestion optimisée du trafic aérien d'un aéroport. L'invention trouve une application particulièrement avantageuse, bien que nullement limitative, dans le cas d'aéroports à forte fréquentation. ÉTAT DE LA TECHNIQUE Actuellement, si la grande majorité des moyens de transport de personnes connaissent un essor important, la croissance du trafic aérien est celle qui connait l'évolution la plus forte. Ainsi, on estime qu'au cours des vingt prochaines années, le taux de croissance annuel du trafic aérien mondial sera proche de 5%, si bien que d'ici à 2030 ce trafic aura doublé en Europe et aux Etats-Unis, ainsi que triplé en Asie. Par « trafic aérien », on fait référence ici aux mouvements en l'air et au sol d'avions dans un espace géographique associé à un aéroport. Plus précisément, par « mouvements en l'air », on entend des vols à l'approche de l'aéroport, et par « mouvements au sol », on entend des déplacements sur l'aérodrome de l'aéroport. De manière conventionnelle, une fois leurs vols respectifs effectués, ces avions roulent au sol sur des voies de circulation qui relient des pistes d'atterrissage/décollage à des parkings dans lesquels lesdits avions stationnent. On comprend donc que l'augmentation du trafic aérien dans les années à venir va nécessairement accroitre la complexité de la gestion dudit trafic, eu égard notamment aux nombreuses contraintes auxquelles il est soumis : contraintes de sécurité pour éviter toute collision d'avions en l'air et au sol, contraintes de minimisation des retards à l'arrivée et au décollage pour éviter une congestion du trafic, contraintes de minimisation de la durée de roulage afin d'économiser du carburant et réduire la pollution, etc. Si la hausse de la circulation aérienne pourrait être théoriquement absorbée par l'extension des infrastructures desdits aéroports, cette solution n'est finalement pas envisageable car elle nécessiterait des investissements 3049743 2 financiers trop importants pour la construction de nouvelles infrastructures, et se heurterait à des problèmes environnementaux (pollution au CO2), sociétaux (nuisances sonores), et finalement aussi d'aménagement en raison de l'urbanisation grandissante aux alentours desdits aéroports. 5 Plus récemment, les progrès en électronique et informatique ont permis d'automatiser une partie du travail des contrôleurs aériens grâce à de nouveaux procédés, mis en oeuvre par des moyens informatiques, et reposant sur des métaheuristiques d'optimisation, les contrôleurs pouvant dès lors prendre en charge davantage de vols. Il convient en effet de noter qu'encore 10 actuellement, dans beaucoup d'aéroports de grande taille, la gestion de la circulation aérienne est effectuée de manière complètement manuelle et limitée, par des contrôleurs aériens maniant de simples bandes de papier (dites « flight strip » dans la littérature anglo-saxonne). Toutefois, ces procédés se contentent de fournir une visualisation 15 partielle de l'état du trafic soit uniquement au sol, soit uniquement en vol, sans apport d'une gestion optimisée qui permettrait d'accroitre le nombre de départs/arrivées à niveau de sécurité constant, en particulier au moyen d'une aide à l'anticipation et à la décision. Ces procédés représentent donc des solutions hétérogènes et non interconnectées, et par conséquent non 20 représentatives de la complexité générée par l'ensemble des déplacements en l'air et au sol des avions. Par conséquent, ces procédés ne permettront pas de tenir compte de l'évolution croissante du trafic aérien dans les années à venir, et des contraintes inhérentes à cette évolution. 25 EXPOSÉ DE L'INVENTION La présente invention a pour objectif de remédier à tout ou partie des inconvénients de l'art antérieur, notamment ceux exposés ci-avant, en proposant une solution qui permette d'avoir un procédé de gestion optimisée du trafic aérien d'un aéroport, afin de maximiser le nombre d'arrivées et de 30 départs que l'aéroport peut absorber, ainsi que de réduire le temps de roulage d'avions au sol. A cet effet, l'invention concerne un procédé de gestion optimisée du trafic aérien d'un aéroport comportant des pistes d'atterrissage/décollage, des 3049743 3 zones de stationnement, et des voies de circulation reliant les pistes auxdites zones de stationnement, ledit trafic aérien comportant une pluralité d'avions respectivement associés à des contraintes de séparation amont/avale, à des pistes d'atterrissage/décollage et à des zones de stationnement, ainsi que 5 destinés à rouler sans conflit sur lesdites voies de circulation. En outre, ledit procédé comporte les étapes successives suivantes : - une étape d'identification dans un horizon temporel prédéterminé Fit d'un nombre A d'avions constitué de N avions en cours de vol, dits à l'arrivée, et de M avions parqués, dits au départ, où I\1 0, 10 M>_0 et A>0, - une étape de détermination pour chacun desdits M avions au départ d'une durée théorique de roulage sans conflit, - une étape de détermination d'une séquence optimale d'heures d'atterrissage/décollage desdits A avions, au cours de laquelle la 15 durée de roulage sans conflit d'un avion au départ est fixée égale à sa durée théorique de roulage sans conflit, ladite séquence minimisant le retard au décollage et à l'atterrissage respectivement des M avions au départ et des N avions à l'arrivée, - une étape de détermination de durées minimales de roulage sans 20 conflit respectifs desdits A avions, sous contrainte de respect des heures d'atterrissage/décollage de ladite séquence optimale. Dans des modes particuliers de mise en oeuvre, le procédé de gestion optimisée du trafic aérien comporte l'une ou plusieurs des caractéristiques suivantes, prises isolément ou selon toutes les combinaisons techniquement 25 possibles. Dans un mode particulier de mise en oeuvre, la durée théorique de roulage sans conflit d'un avion au départ est fonction d'une durée de roulage dudit avion au départ considéré comme seul dans l'aéroport, ainsi que d'un paramètre représentatif du trafic aérien nominal dudit aéroport. 30 Dans un mode particulier de mise en oeuvre, la durée de roulage dudit avion au départ considéré comme seul dans l'aéroport est déterminé au moyen d'un algorithme de type Dijkstra 3049743 4 Dans un mode particulier de mise en oeuvre, l'étape de détermination d'une séquence optimale d'heures d'atterrissage/décollage comporte la minimisation d'une fonction objectif F1 décrite par : M N F1 =1(STOT (i) - TTOT (i)) +I(STA(i) - ETA(0) 5 STOT et STA étant des inconnues correspondant à des heures optimales respectivement de décollage des avions au départ et d'atterrissage des avions à l'arrivée, TTOT et ETA correspondant respectivement à des heures de décollage au plus tôt des avions au départ et des heures 10 d'atterrissage au plus tôt des avions à l'arrivée, TTOT et ETA étant déterminées à partir respectivement des durées théoriques de roulage sans conflit et d'un algorithme de prédiction de trajectoire, les heures ETA respectives des avions à l'arrivée étant des contraintes prioritaires lors de la minimisation de la fonction objectif 15 F1. Dans un mode particulier de mise en oeuvre, la fonction objectif F1 est minimisée au moyen d'un premier algorithme de colonies de fourmis, chaque fourmi pouvant déposer des phéromones attractives. Dans un mode particulier de mis en oeuvre, ledit premier algorithme 20 comporte 10000 colonies de fourmis, chaque colonie comportant 100 fourmis. Dans un mode particulier de mise en oeuvre, le procédé comporte une étape de prise en compte d'une congestion locale du trafic aérien sur l'aéroport, consécutive à l'étape de détermination d'une séquence optimale d'heures d'atterrissage/décollage et antérieure à l'étape de détermination de 25 temps minimaux de roulage sans conflit, dans laquelle l'heure ETA d'au moins un avion à l'arrivée est mise à jour de manière forcée. Dans un mode particulier de mise en oeuvre, l'étape de détermination de temps minimaux de roulage sans conflit comporte la minimisation d'une fonction objectif F2 décrite par : M N 30 F2- (STOT (i) - SOBT (i)) +1(SIBT (i) - STA(0) 3049743 5 - SOBT et SIBT étant des inconnues correspondant à des heures optimales respectivement de départ de parking des avions au départ et d'arrivée au parking des avions à l'arrivée. Dans un mode particulier de mise en oeuvre, la fonction objectif F2 est 5 minimisée au moyen d'un deuxième algorithme de colonies de fourmis, chacun desdits A avions étant associés à un nombre prédéterminé C de colonies, et chaque fourmi pouvant déposer des phéromones attractives et des phéromones répulsives. Dans un mode particulier de mise en oeuvre, le nombre C de colonies 10 de fourmis est égal à 1000, chaque colonie comportant 100 fourmis. Dans un mode particulier de mise en oeuvre, l'influence respective des phéromones attractives et des phéromones répulsives sur le déplacement d'une fourmi est une fonction dudit nombre prédéterminé C. Dans un mode particulier de mis en oeuvre, les étapes précédentes 15 sont exécutées de manière itérative selon un pas de temps prédéterminé, ou de manière asservie. Procédé selon l'une des revendications précédentes, dans lequel l'horizon temporel Ht est de 90 minutes. 20 PRÉSENTATION DES FIGURES L'invention sera mieux comprise à la lecture de la description suivante, donnée à titre d'exemple nullement limitatif, et faite en se référant aux figurent qui représentent : - Figure 1 : un exemple d'un virage impossible ou transition interdite 25 dans le graphe du réseau de taxiway. - Figure 2 : un exemple d'arbre des solutions pour le problème de détermination d'une séquence optimale d'heures d'atterrissage de trois avions sur une même piste. - Figure 3 : un exemple d'évolution du déplacement des fourmis au 30 fil de l'algorithme de colonie de fourmis. 3049743 6 - Figure 4: un exemple des deux transformations permettant d'obtenir le graphe nécessaire à l'optimisation depuis le graphe original de modélisation de l'aéroport. - Figure 5 : un exemple d'un choix entre trois noeuds (A,B,C) avec 5 les taux de phéromones attractives et répulsives pour chacun d'entre eux. - Figures 6a à 6f : des exemples d'évolution d'un tirage aléatoire dépendant des taux d'attraction et de répulsion des phéromones. - Figures 7a et 7b : des exemples de positionnement de 10 phéromones attractives et répulsives. - Figure 8 : un diagramme récapitulatif des étapes du procédé. DESCRIPTION DÉTAILLÉE D'UN MODE DE RÉALISATION DE L'INVENTION 15 LEXIQUE : - Taxiway : Voie de circulation utilisée par les avions afin d'effectuer les déplacements au sein de l'aéroport. - Roulage : Mouvement d'un avion sur les taxiways de l'aéroport, essentiellement pour rejoindre une piste ou un parking. 20 - ETA : heure d'atterrissage au plus tôt d'un avion à l'arrivée (acronyme de l'expression anglaise "Estimated Time of Arrivai"). - TOBT : heure souhaitée de début de roulage d'un avion au départ, à valeur tactique (acronyme de l'expression anglaise "Target Off-Block Time"). 25 - SOBT : heure optimale de départ de parking d'un avion au départ, ou encore de début de roulage (acronyme de l'expression anglaise "Scheduled Off-Block Time"). - SIBT : heure optimale d'arrivée au parking d'un avion à l'arrivée (acronyme de l'expression anglaise "Scheduled In-Block Time"). 30 - TTOT : heure de décollage au plus tôt d'un avion au départ (acronyme de l'expression anglaise "Target Take-Off Time"). 3049743 7 - STOT: heure optimale de décollage d'un avion au départ (acronyme de l'expression anglaise "Scheduled Take-Off Time"). STA: heure optimale d'atterrissage d'un avion à l'arrivée (acronyme de l'expression anglaise " Scheduled Time of Arrivai "). 5 Le procédé de gestion optimisée du trafic aérien vise à optimiser l'utilisation de l'ensemble des ressources d'un aéroport afin de maximiser le nombre d'arrivées et de départs que l'aéroport peut absorber. Les pistes de décollage et d'atterrissage sont identifiées comme étant les ressources les plus 10 contraignantes par leur capacité à absorber leur mouvement mais aussi par le coût très élevé qu'engendre leur construction. Cependant, leur utilisation est dépendante de celle des taxiways (routes au sol reliant les parkings/gates aux pistes) et la prévision des heures d'arrivées pour les avions en route souhaitant atterrir. 15 Déclenchement de l'optimisation L'optimisation peut être déclenchée par différents types d'évènements : - La détection ou le signalement d'un nouvel avion à l'arrivée. 20 - La mise à jour de la position d'un avion à l'arrivée indiquant une avance ou un retard par rapport à la position précédente. - Le dépôt d'un plan de vol au départ, avec une heure indiquant l'heure souhaitée de départ du parking. - La mise à jour du de l'heure souhaitée de départ de parking pour 25 un plan de vol. - L'évolution des conditions météos, entrainant une/des modification(s) d'ETA. - La modification du réseau de taxiways (travaux, neige...). Il convient de noter que les évènements permettant de déclencher 30 l'optimisation peuvent résulter, d'une part, d'actions manuelles exécutées par exemple par un contrôleur aérien ou bien encore un autre opérateur (situations d'urgence, nécessité d'optimisation locale en temps du trafic en raison d'une 3049743 8 trop forte congestion, etc.), et d'autre part, d'actions automatiques exécutées lors du contrôle de paramètres nécessaires à la gestion du trafic et relevant de l'exploitation nominale de ressources de l'aéroport (détection radar, relevé météo, etc.). 5 Mise à jour d'un plan de vol à l'arrivée L'optimisation peut être déclenchée par le report d'une position 4D (latitude, longitude, altitude à un instant donné) fournie par un vol en route souhaitant atterrir, et initialement associé à une heure d'atterrissage au plus 10 tôt. Le report d'une position 4D d'un avion, au moyen d'un procédé de planification de trajectoire connu en soi, implique que l'avion va être associé à une nouvelle heure d'atterrissage au plus tôt. Déclenchement de l'optimisation par un avion à l'arrivée 15 Deux cas peuvent alors amener à avoir recours à l'optimisation des pistes et taxiways de l'aéroport : - Le vol dont l'heure d'atterrissage vient d'être estimée est nouveau dans le système (c'est donc la première fois que l'ETA est calculé 20 pour ce plan de vol). - Le plan de vol avait déjà été introduit dans le système, mais l'ETA calculé à partir de ce nouveau report de position est différent de l'ETA précédemment calculé. Ces deux configurations entrainent donc un changement des 25 contraintes à prendre en compte pour l'ordre des atterrissages sur les pistes d'atterrissage. L'optimisation des pistes est donc déclenchée. Mise à jour d'un plan de vol au départ 30 Dépôt d'un nouveau plan de vol au départ Lorsqu'une compagnie ou un vol privé souhaite obtenir un créneau de décollage, ceux-ci déposent une heure souhaitée de départ de parking : le 3049743 9 TOBT (Target Off-Block Time). Un parking ou une porte d'embarquement est alors attribué à l'avion. Une piste de décollage lui est attribuée en fonction de sa destination. A partir du couple parking/piste donné, un temps de roulage minimal 5 peut être évalué. Afin de prendre en compte de manière dynamique les modifications pouvant être apportées au réseau de taxiway (neige, travaux...), le temps de roulage minimum est calculé et non simplement fixé en fonction du couple parking/piste. 10 Mise à jour d'un plan d'un TOBT ou modification du réseau de taxiway La mise à jour d'un TOBT pour un plan de vol déjà introduit dans le système amène à réévaluer son temps de roulage minimum et ainsi son heure d'arrivée en piste au plus tôt. 15 L'utilisateur du programme peut également renseigner une modification touchant le réseau de taxiway. La fermeture d'un taxiway ou les conditions météos peuvent modifier le trajet utilisé ou la vitesse au sol des avions. Les plans de vol potentiellement impactés voient ainsi leurs temps de roulage respectifs et leurs heures d'arrivée en bout de piste estimées TTOT 20 recalculées. Calcul de l'heure d'arrivée en bout de piste Afin de fournir une heure d'arrivée en bout de piste au plus tôt, c'est-à25 dire une heure de décollage au plus tôt, ou TTOT (Target Take-Off Time), le parcours de roulage est calculé de manière dynamique. Le réseau de taxiway de l'aéroport est pour cela représenté sous la forme d'un graphe : - Les carrefours, parkings et pistes sont les sommets du graphe. - Les routes reliant carrefours, parkings et pistes sont les arcs du 30 graphe. La longueur des arcs correspond au temps estimé pour parcourir celui-ci selon la vitesse de roulage de l'appareil (dépendante du type d'avion, de la compagnie et des conditions météo). 3049743 10 - Selon les sens de circulation autorisés ou proscrits, les arcs sont orientés. Les virages interdits entre taxiways sont renseignés sur les sommets du graphe. 5 Les virages impossibles correspondent à une transition entre deux arcs qui doit être interdite. Les fermetures temporaires de certains taxiways peuvent donc conduire à éliminer certains arcs du graphe obtenu, comme représenté sur la figure 1. 10 L'heure au plus tôt est ainsi obtenue en ajoutant au TOBT le temps de roulage estimé plus un facteur représentatif du trafic aérien nominal de l'aéroport, ce facteur correspondant à une marge de temps dépendant de la taille de l'aéroport et visant à permettre la résolution de conflits : A. 15 TTOT = TOBT + roulage + A A étant un paramètre fixé selon la taille de l'aéroport et le nombre d'arrivées et départs quotidiens de celui-ci. Ce paramètre vise à permettre l'élimination des conflits au sol entre avions de l'optimisation. 20 Déclenchement de l'optimisation par un avion au départ L'ensemble des mises à jour influant sur les avions au départ vont entrainer des modifications pour la succession des atterrissages et décollages 25 de la piste : - Un nouveau plan de vol entraîne l'ajout d'un nouveau TTOT. - La modification d'un TOBT entraîne la modification d'un TTOT. - Une modification du réseau de taxiway peut entraîner la modification de un ou plusieurs TTOT. 30 Ainsi, les modifications sur les plans de vols au départ entrainent une nouvelle optimisation de la piste et des taxiways. 3049743 11 Optimisation des pistes : Définition du problème L'objectif est de fixer pour l'ensemble des avions à un horizon de 1h30 5 une heure de décollage (STOT : Scheduled Take-Off Time) pour les départs ou d'atterrissage (STA : Scheduled Time of Arrivai) pour les arrivées. Données et contraintes 10 L'optimisation des pistes prend en entrée les temps souhaités de décollages (TTOT) de d'atterrissage (ETA). Ces temps contraignent le problème en minorant l'heure de décollage ou d'atterrissage attribuée à chaque avion. Les avions génèrent des turbulences de sillage lors de leur 15 mouvement. Des temps de séparation minimums amont/avale sont donc à assurer entre chaque décollage/atterrissage. L'intensité des turbulences de sillage est évaluée en fonction de la catégorie de l'avion concerné, dépendante de son poids et son envergure. Les avions sont ainsi classés en 4 catégories : Jumbo, Heavy, Medium et Light (du plus lourd au plus léger). Plus un avion est 20 lourd, plus il provoquera de turbulence et plus un avion est léger, plus il subira les turbulences de l'avion précédent. Ainsi, une matrice de temps de séparation requis peut être construite par paire de catégories d'avions. Si l'aéroport comporte plusieurs pistes et que celles-ci sont proches, il est possible que les mouvements sur l'une provoquent des turbulences influant 25 sur les autres pistes. Dans ce cas, un coefficient compris entre 0 et 1 est attribué pour chaque paire de piste. Plus les pistes sont proches, plus ce coefficient sera proche de 1. Ce coefficient sert à multiplier la matrice des turbulences de sillage évoquée précédemment pour déterminer les temps de séparation minimums requis entre pistes. 30 Exemple : 3049743 12 Soit la matrice de séparation minimum suivante, avec en ligne les avions générant la turbulence de sillage et en colonne l'avion suivant, la subissant : 5 JUMBO HEAVY MEDIUM LIGHT JUMBO 1 2 3 3 HEAVY 1 1 2 2 MEDIUM 1 1 1 2 LIGHT 1 1 1 1 10 Soit deux pistes au sein de l'aéroport dont le coefficient de répercussion des turbulences est de 0.5. Soit un avion de catégorie Jumbo décollant sur la première piste à 12h00 et un avion de type Medium souhaitant décoller sur la seconde piste. 15 L'avion de type Medium devra respecter le temps de séparation suivant : 3x0,5 (temps de séparation fourni par la matrice multiplié par le coefficient). L'avion Medium ne pourra alors pas décoller avant 12h01m30s, soit 12H02 par convention d'arrondi à la minute supérieure. S'il avait voulu décoller sur la même piste, il n'aurait pas pu partir avant 12h03 (coefficient égal 20 à 1 pour une même piste). Variables et fonction objectif L'objectif de l'optimisation étant de fixer les STOT et STA de chacun 25 des avions mis en jeu, ces temps sont les variables du problème. Pour des raisons opérationnelles, ces temps sont arrondis à la minute près. L'objectif de l'optimisation est de minimiser pour l'ensemble des avions les différences entre temps de décollage/atterrissage au plus tôt et le temps finalement attribué. La fonction objectif est donc être écrite de la matière 30 suivante : Minimiser F1 = E(STOT-TTOT) + E(STA-ETA) Soit minimiser la somme des différences entre STOT/TTOT et STA/ETA. 3049743 13 Modélisation du problème : L'ensemble des solutions possible peut être représenté sous la forme 5 d'un arbre. Le premier niveau de l'arbre représente le choix du premier plan de vol à séquencer. Au premier niveau, aucune contrainte de turbulence n'est à prendre en compte, et le premier plan de vol peut donc être séquencé au plus tôt (STOT=TTOT ou STA=ETA). A chaque niveau de l'arbre un plan de vol est choisi et donc séquencé 10 en respectant les contraintes de séparation avec les avions précédemment séquencés (plus haut dans l'arbre). Le nombre de niveaux de l'arbre est donc égal au nombre de plans de vol à séquencer. Un coût est associé à chaque branche de l'arbre. Ce coût correspond au délai attribué au plan de vol choisi (la différence STOT/TTOT ou STA/ETA) 15 pour respecter les contraintes de séparation. Chaque solution possible correspond à une racine de l'arbre, et le coût de cette solution correspond à la somme des branches parcourues pour y parvenir. Exemple particulier : 20 Soit un problème simple dans un aéroport avec une seule piste où 3 avions souhaitent décoller ou atterrir à la même heure. Les turbulences de sillage créaient les contraintes de séparation minimales suivantes : Avion1 Avion2 Avion3 Avionl 0 3 4 Avion2 2 0 3 Avion3 1 2 0 25 30 L'arbre des solutions possible est représenté en figure 2. 3049743 14 Il s'agit de parcourir un arbre, chaque branche de l'arbre comportant des noeuds positionnés à différents niveaux. Chaque noeud de niveau N est affecté d'un poids, ce poids étant une réunion de 2-uplets, chaque 2-uplet correspondant aux contraintes de séparation en amont et en aval imposées par 5 chaque avion positionné dans la branche aux niveaux inférieurs à N, vis-à-vis de l'avion positionné au noeud de niveau N. Du coup, lors du parcours de la branche, on détermine à chaque noeud des intervalles de contrainte en fonction du poids de chaque noeud. Une fois les intervalles de contrainte déterminés pour un noeud, on vérifie en premier que l'ETA ou TTOT du noeud est en 10 dehors des intervalles déterminés. Si oui, STA = ETA ou STOT = TTOT, selon le cas envisagé. Si non, on vérifie ensuite si la réunion des intervalles déterminés forme un intervalle. Si la réunion n'est pas un intervalle mais une réunion d'intervalles, l'heure affectée au noeud est la première heure à laquelle apparaît, dans le sens des temps croissants, la fin d'un premier intervalle. Si 15 par contre la réunion est un intervalle, l'heure affectée au noeud est la limite droite de l'intervalle. Exemple particulier : Soit un problème avec 4 avions Al, A2, A3 et A4 voulant atterrir sur la même piste : 90 Al : ETA = 10h00 A2 : ETA = 09h59 A3 : ETA = 10h02 A4 : ETA = 09h55 A3 est de type Light et les autres Medium. A3 est donc plus léger. 25 Nous avons la matrice des temps de séparation en minutes suivante (1' avion en ligne, deuxième en colonne) Al A2 A3 A4 Al X 2 3 2 A2 2 X 3 2 30 A3 1 1 X 1 A4 2 2 3 X 3049743 15 Soit l'évaluation du coût de la solution A1, A2, A3, A4 (choix dans l'arbre des solutions des branches Al puis A2 puis A3 puis A4) : - On positionne tout d'abord Al sans contraintes selon son ETA 5 (10h00) : Al :STA = 10h00 - On positionne A2 en fonction des avions déjà placés (A1) : A2 doit respecter le temps de séparation avant Al : 10 Al A2 A3 A4 Al X 2 3 2 A2 2 X 3 2 A3 1 1 X 1 A4 2 2 3 X 15 Et après Al : Al A2 A3 A4 Al X 2 3 2 20 A2 2 X 3 2 A3 1 1 X 1 A4 2 2 3 X A2 n'a donc pas le droit de décoller entre 09h58 et 10h02 (10h00 - 2 25 et 10h00 + 2) et pas avant son ETA (09h59) : A2 : STA = 10h02 - On positionne ensuite A3 en respectant les contraintes de séparations avec Al et A2 : 30 Al contraint A3 entre [09h59; 10h03[ (suivant la matrice : 10h00 - 1 et 10h00 + 3). A2 contraint A3 entre [10h01; 10h05[ (suivant la matrice : 10h02 - 1 et 10h02 + 3). 3049743 16 A3 doit aussi respecter son ETA 10h02 A3 : STA = 10h05 - Enfin on positionne A4 en prenant en compte A1, A2 et A3 : 5 Al contraint A4 entre [09h58; I 0h02[ A2 contraint A4 entre [10h00; 10h04[ A3 contraint A4 entre [10h02; 10h06[ ETA de A4 : 09h55 A4 : STA = 09h55 10 Séquence obtenue : A4(09h55), Al (10h00), A2(10h02), A3(10h05). Coût de la solution : Al (+0), A2(+3), A3(+3), A4(+0) = 6min. Résolution du problème 15 Le nombre de solutions potentielles au problème est la factorielle du nombre de plans de vol mis en jeu. Ce problème est dit NP-Difficile et ne peut donc être résolu de manière efficace avec des algorithmes classiques de recherche de solution optimale. En effet la recherche de la solution optimale 20 peut alors prendre un temps très grand lorsque le nombre de plans de vol devient conséquent. L'algorithme de colonie de fourmis est utilisé pour contourner ce problème. Avantages de l'algorithme de colonie de fourmis : L'algorithme s'applique à des problèmes représentés sous forme de 25 graphe (un arbre étant un type particulier de graphe). L'algorithme tend vers une solution optimale. Le temps d'exécution de l'algorithme peut facilement être maîtrisé en paramétrant le nombre d'itération de celui-ci. 30 Rappel sur l'algorithme de colonie de fourmis L'algorithme vise à imiter le comportement des fourmis dans la nature. Comme illustré en figure 3, l'algorithme se déroule de la manière suivante : 3049743 17 - Les fourmis commencent à procéder à la recherche de nourriture et partent dans toutes les directions de manière « aléatoire ». - Sur leur chemin, les fourmis déposent des phéromones afin de marquer le chemin qu'elles utilisent. 5 - Une fois la nourriture trouvée, une fourmi revient vers sa colonie. - Les fourmis suivantes sont influencées par les phéromones déposées par leurs prédécesseurs, les aidant ainsi à retrouver plus rapidement la nourriture. - Soit deux chemins menant à un point de nourriture, si l'un est plus 10 court que l'autre, les fourmis employant ce chemin feront davantage d'aller-retour sur celui-ci que les fourmis employant le chemin le plus long. - Le marquage des chemins les plus courts à donc tendance à être de plus en plus fort par rapport aux autres. 15 - Les phéromones déposées s'évaporent avec le temps, effaçant ainsi avec le temps le marquage des chemins les plus longs. - Après un certains nombres d'aller-retour, seul(s) le/les chemin(s) les plus courts sont empruntés par les fourmis, dégageant ainsi une solution optimale. 20 Marco Dorigo par sa publication « Ant Algorithms for discrete optimization » en collaboration avec Gianni Di Caro est considéré comme l'un des créateurs de l'algorithme et est à l'origine de sa popularisation. L'algorithme s'applique à un problème représenté sous la forme d'un graphe où l'on cherche à minimiser un chemin entre un point de départ et une 25 arrivée. Le comportement des fourmis est simulé informatiquement dans ce graphe afin de trouver une solution optimale. Les premières « fourmis » choisissent des arcs aléatoires pour tenter de trouver une solution. Si l'une d'entre elles y parvient, on dépose alors un marquage (phéromones) sur les 30 arcs utilisés pour parvenir à cette solution. 3049743 18 Le même phénomène qu'avec une vraie colonie de fourmis est alors reproduit : les fourmis vont peu à peu utiliser de plus en plus le chemin optimal pour finalement converger vers celui-ci (voir figure suivante). 5 Application et évaluation L'algorithme de colonie de fourmis est applicable très simplement à partir de la modélisation du problème réalisée. Lorsqu'une fourmi atteint une des racines de l'arbre correspondant à une solution, elle dépose des 10 phéromones en fonction de la qualité de cette solution, la qualité de la solution étant quantifiée par la valeur de F1. Ainsi les meilleures branches, c'est-à-dire celles pour lesquelles les valeurs respectives de F1 sont les plus petites, seront les plus marquées et les fourmis convergeront vers l'une des meilleures solutions. Chaque fourmi est en outre adaptée à déposer sur les noeuds d'une 15 branche solution une quantité de phéromones égale à 10001(F1)2, F1 étant ici la qualité de ladite solution. Les fourmis sont créées par groupes d'une centaine d'individus. Une fois que le groupe a atteint les racines de l'arbre, les phéromones sont déposées et un nouveau groupe de fourmis est créé pour parcourir l'arbre à 20 son tour (prenant en compte les phéromones). Exemple d'une optimisation commune: Pour un horizon de 1h30, une cinquantaine de mouvements sont à 25 envisager en cas de trafic important au sein d'un aéroport. Si l'on considère un arbre de solutions formé par 50 avions, l'ordre de grandeur du nombre de groupe de fourmis à créer est de 10 000 pour obtenir une convergence vers une solution de qualité. Si nous prenons le déplacement d'une fourmi ou le dépôt d'une 30 phéromone comme étant des calculs primaires, l'évaluation du temps de résolution est possible. Pour une longueur d'arbre de 50, des groupes de fourmis de 100 individus et un algorithme de 10 000 itérations (10 000 groupes de fourmis), 3049743 19 nous obtenons 50 millions de déplacements et 50 millions dépôt de phéromones soit 100 millions de calcul. Les processeurs standards actuels sont capables de réaliser plusieurs milliards de calculs à la seconde. Ainsi, même si cette évaluation du nombre de 5 calculs nécessaires est sous-évaluée, l'ordre de grandeur de cette évaluation démontre bien que l'optimisation ne nécessite qu'une fraction de seconde. L'utilisation de l'algorithme de fourmis dans ce problème permet donc de fournir une solution proche ou égale à l'optimum global recherché en un 10 temps tout à fait satisfaisant pour une utilisation opérationnelle. Optimisation du réseau de taxiways 15 Définition du problème : Après une mise à jour d'une séquence de décollages/atterrissages en piste ou une modification apportée au réseau de taxiways, les chemins au sol à emprunter par les avions sont à recalculer. L'objectif est de minimiser les 20 temps de roulage de l'ensemble des plans de vol tout en évitant les conflits entre les avions (ne pas utiliser le même taxiway au même moment). Nous allons donc chercher un chemin permettant aux avions à l'arrivée de rejoindre au plus tôt leur parking après l'atterrissage et un chemin permettant de quitter au plus tard son parking pour un avion au départ, tout en étant en seuil de piste 25 pour son horaire de décollage. Pour chaque avion à l'arrivée pris en compte dans ce problème, un STA a précédemment été calculé et un parking attribué. L'objectif est donc de rejoindre au plus tôt ce parking depuis la piste au STA, tout en prenant en 30 compte les autres avions présents sur l'aéroport. Pour un avion au départ, un STOT et un TOBT ont précédemment été calculés et son parking attribué. L'objectif est donc de retarder au maximum le départ du block (avec un départ au plus tôt au TOBT) et de trouver un chemin 3049743 20 jusqu'à la piste en prenant en compte les autres avions tout en arrivant au plus tard une minute avant le STOT pour ne pas rater le créneau de décollage. L'heure optimale d'entrée au parking recherché pour les avions à 5 l'arrivée est appelé SIBT (Scheduled In-Block Time) et l'heure optimale de départ du parking recherchée pour les avions au départ SOBT (Scheduled Off-Block Time). L'objectif de l'optimisation est donc de trouver les chemins permettant de répondre à la fonction objectif suivante : Minimiser F2 = E (STOT-SOBT) + E(SIBT-STA) 10 Cette fonction représente la minimisation de la somme des temps de roulages pour l'ensemble des avions pris en compte. Modélisation du problème 15 Les taxiways de l'aéroport sont tout d'abord modélisés sous forme de graphe. De manière évidente, ledit graphe des taxiways correspond au graphe déjà modélisé pour le calcul du TTOT des avions au départ (estimation de disponibilité au plus tôt en seuil de piste pour décollage) : - Chaque carrefour (croisement de deux ou plus taxiways), est 20 modélisé par un sommet. Chaque partie de taxiway entre deux carrefours est représenté par un arc. - Selon les sens de circulation autorisés ou proscrits, les arcs sont orientés. 25 Certaines transitions entre taxiways doivent être interdites. Cependant ce graphe ne suffit pas pour gérer les conflits entre avions utilisant la même portion de taxiway et ne permet pas d'interdire des virages entre taxiways impossibles à réaliser. Le graphe utilisé pour l'algorithme de fourmis, dans le cadre de 30 l'optimisation des taxiways utilisés par les avions, résulte de deux transformations du graphe original représentant l'aéroport : 3049743 21 Les arcs du graphe initial deviennent donc les sommets et ceux-ci sont reliés deux à deux s'ils possèdent un carrefour en commun et que la transition de l'un à l'autre n'est pas interdite. Afin de pouvoir résoudre les problèmes de conflits entre avions, le 5 temps doit être intégré au problème. Chaque sommet du nouveau est donc séparé en plusieurs sommets selon une unité de temps : pour chaque unité de temps, un nouveau sommet est créé pour chaque arc de l'aéroport comme représenté en figure 4. 10 Extension de l'algorithme de colonie de fourmis, avec la présence de plusieurs colonies et le dépôt de phéromones répulsives Modélisation d'un problème de réseau de transport 15 Soit un réseau dans lequel transitent plusieurs véhicules. Chacun des véhicules doit accomplir un trajet entre un point de départ à une heure donnée jusqu'à un point d'arrivée (avec un horaire d'arrivée qui peut également être borné). L'objectif de l'optimisation est de trouver la somme minimale des distances à parcourir par l'ensemble des véhicules. Une contrainte majeure est 20 introduite : les véhicules ne peuvent utiliser un même noeud ou arc au même moment afin d'éviter les collisions. La modélisation du problème s'effectue ainsi : Le réseau est représenté par un graphe, où les carrefours sont représentés par des noeuds et les routes qui les relient sont représentées par 25 des arcs orientés. A chaque véhicule circulant est associé une colonie de fourmis utilisant le système de dépôt de phéromones afin de trouver le chemin le plus court possible pour réaliser le trajet demandé. 30 Phéromones attractives et répulsives Comme pour un algorithme de colonie de fourmis classique, lorsqu'une fourmi trouve un chemin solution, elle dépose une quantité de 3049743 22 phéromone sur celui-ci proportionnellement inverse à sa longueur. Ainsi les fourmis de la même colonie pourront utiliser ces phéromones comme point de repère et auront tendance à suivre le même chemin. Plus le chemin est de bonne qualité, plus le taux de phéromone présent sur celui-ci sera élevé au fil 5 du temps, de façon à converger vers un chemin optimal. Lorsque des phéromones sont positionnées sur un sommet du graphe, une date leur est associée, correspondant à la date de passage de la fourmi dépositaire sur ce sommet. Ainsi, seules les fourmis utilisant le sommet à la même date de passage prendront en compte ces phéromones. 10 Afin d'éviter les conflits entre les chemins trouvés par chacune des colonies, les phéromones déposées par les colonies concurrentes sont également prises en compte par les fourmis. Afin d'éviter la confusion, les phéromones perçues par une fourmi garderont le nom de « phéromone » si elles ont été déposées par une fourmi de la même colonie, sinon nous les 15 désignerons en tant que « répulsif » ou « phéromone répulsive ». Déroulement de l'algorithme Les fourmis de l'ensemble des colonies sont lancées de manière 20 simultanée et se déplacent aléatoirement dans le graphe. Après quelques lancés, le pouvoir d'attraction des phéromones va être augmenté afin que les fourmis puissent commencer à converger sur des chemins correspondant à des solutions de « qualité ». Après plusieurs augmentations de l'attraction des phéromones, 25 chacune des colonies devrait avoir convergé vers un ou quelques chemins optimaux. C'est alors que la détection de répulsifs va entrer en jeu. En augmentant le pouvoir des phéromones répulsives, les chemins marqués par les colonies vont petit à petit dévier des solutions optimales précédemment trouvées afin de résoudre les conflits. Ainsi les nouveaux 30 chemins dessinés resteront proches des optimums, tout en ne s'enchevêtrant plus. 3049743 23 Une fois l'ensemble des conflits résolus, les sommets et horaires où ont été déposé les phéromones permettent de définir les mouvements à réaliser par chaque aéronef. 5 Exemple particulier de mise en oeuvre : Marquage d'une solution La fin de vie d'une fourmi peut être engendrée par trois évènements : ter cas : la fourmi n'a plus de mouvements possibles. La fourmi se retrouve dans une impasse et ne peut donc plus se déplacer dans 10 le graphe, elle est alors « tuée ». 2è" cas : le temps de parcours de la fourmi est supérieur à 15min. Chaque arc emprunté par la fourmi a un coût en temps. Lorsque la somme des coûts d'arc qu'elle a parcouru est supérieure à 15min, la fourmi est alors « tuée ». 15 3ème cas : la fourmi parvient à atteindre son but. Chaque noeud du graphe correspondant à la position géographique visée par la fourmi est potentiellement un noeud d'arrivée. Dès lors qu'un noeud d'arrivée est atteint, la fourmi a alors trouvé une solution possible. 20 Après avoir atteint une solution, la fourmi doit évaluer la qualité de la solution pour déposer des phéromones. La qualité de la solution est évaluée par rapport à un temps de roulage maximal toléré de 15min, et correspond à la valeur de F2 pour ladite solution. Soit 1000 le nombre maximal de phéromones qu'une fourmi peut 25 déposer sur chaque noeud d'une solution. Alors, Q est la quantité de phéromones déposée sur chaque noeud du chemin solution avec Q = 1000/F2. Déplacement dans le graphe en fonction des phéromones 30 Lorsqu'une fourmi se déplace, celle-ci doit souvent faire un choix entre plusieurs noeuds potentiels. Pour cela, son choix peut être fait de 3 manières différentes : 3049743 24 - Tirage totalement aléatoire. Chaque noeud potentiel a autant de chance d'être choisi. - Tirage aléatoire influé par les taux de phéromones attractives. La fourmi consulte le nombre de phéromones de sa colonie présentes 5 sur chacun des noeuds. Plus ce nombre de phéromones est élevé, plus la fourmi aura de chance de choisir ce noeud. - Tirage aléatoire influé par les taux de phéromones répulsives. La fourmi consulte le nombre de phéromones répulsives des autres colonies présentes sur chacun des noeuds. Plus ce nombre de 10 phéromones est élevé, moins la fourmi aura de chance de choisir ce noeud. La figure 5 est un exemple d'un choix entre trois noeuds (A,B,C) avec les taux de phéromones attractives et répulsives pour chacun d'entre eux. 15 - Pour un choix aléatoire, nous avons équiprobabilité des choix : P(A) = P(B) = P(C) = 1/3 - Pour un choix en fonction des phéromones attractives : 20 Total de phéromones attractives : 10 + 5 + 5 = 20 P(A) = 10/20 P(B) = 5/20 P(C) = 5/20 - Pour un choix en fonction des phéromones répulsives : Pour chacun des noeuds, la somme des répulsifs des autres noeuds 25 est calculée : A: 20+5 = 25, B : 15+5 = 20 et C : 20+15 = 35 Afin d'augmenter l'importance de ces phéromones répulsives dans le tirage aléatoire du noeud choisi, ces taux sont mis au carré. (625, 400 et 1225) P(A) = 625/2250, P(B) = 400/2250 et P(C) = 1125/2250 (2250 = 625 + 30 400 +1225) 3049743 25 Le choix du type de tirage se fait par un autre tirage aléatoire préalable dépendant des taux courants d'attraction et de répulsion des phéromones : 5 Comme représenté figure 6a, soit donc un segment représentatif du type de tirage. Lors des premiers lancements de fourmis, les déplacements sont toujours aléatoires. Autrement dit, le type de tirage a 100% de chance d'être un tirage totalement aléatoire. Au bout de quelques lancers, l'influence des phéromones attractives 10 va être introduite. Ainsi, et comme représenté figure 6b, les chances d'avoir un tirage en fonction des phéromones attractives ne seront plus nulles. L'influence des phéromones attractives va être augmentée peu à peu. Comme représenté figure 6c, ceci se traduit par l'augmentation des chances de s'orienter vers un choix en fonction des phéromones attractives lors du premier 15 tirage. Comme représenté figure 6d, cette influence va être augmentée jusqu'à ce que 100% des tirages soient fait selon les phéromones attractives. Puis, comme représenté figure 6e, après quelques lancés de fourmis supplémentaires, l'influence des phéromones répulsives va à son tour être 20 mise en jeu. Les chances de s'orienter vers un tirage en fonction des répulsifs vont être augmentées, jusqu'à ce que leurs probabilités soient au moins supérieur à un tirage en fonction des phéromones attractives comme représenté figure 6f. 25 Exemple d'évolution des taux d'influences des phéromones attractives et répulsives Soit l'algorithme paramétré avec un nombre de colonies de fourmis maximal égal à 1000 par avions, chaque colonie comportant 100 fourmis. Les colonies associées à un avion sont lancées de manière successive dès qu'une 30 colonie a convergé vers une solution ou bien a vu l'ensemble de ses membres tués. 3049743 26 Nous noterons P(Rand) la probabilité de faire un choix de manière entièrement aléatoire, P(Atr) la probabilité de faire un choix sous influence des phéromones attractives et P(Rep) sous influence des phéromones répulsives. 5 50 premiers lancers : P(Rand) = 1 , P(Atr) = 0 P(Rep) = 0 Lancers 50-100: P(Rand) = 0,8 , P(Atr) = 0,2 , P(Rep) = 0 Lancers 100-200: P(Rand) = 0,6 , P(Atr) = 0,4 P(Rep) = 0 Lancers 200-300: P(Rand) = 0,4 , P(Atr) = 0,6 P(Rep) = 0 Lancers 300-400: P(Rand) = 0,2 , P(Atr) = 0,8 P(Rep) = 0 10 Lancers 400-500: P(Rand) = 0, P(Atr) = 1 , P(Rep) = 0 Lancers 500-600: P(Rand) = 0, P(Atr) = 0,8 , P(Rep) = 0,2 Lancers 600-700: P(Rand) = 0, P(Atr) = 0,7 , P(Rep) = 0,3 Lancers 700-800: P(Rand) = 0, P(Atr) = 0,6 , P(Rep) = 0,4 Lancers 800-900: P(Rand) = 0, P(Atr) = 0,5 , P(Rep) = 0,5 15 Lancers 900-1000: P(Rand) = 0, P(Atr) = 0,4 , P(Rep) = 0,6 A partir de l'introduction des phéromones répulsives, les chemins les plus marqués par l'ensemble des colonies sont régulièrement vérifiés (tous les 50 lancers). Ainsi, si aucun conflit ne se présente entre les chemins trouvés, 20 l'algorithme est arrêté et les solutions récupérées, car il n'est alors pas nécessaire de continuer à augmenter l'influence des phéromones répulsives. Exemple de choix de mouvements pour une fourmi (récapitulatif) A chaque mouvement, une fourmi doit donc procéder à deux tirages 25 aléatoires pour choisir son mouvement (premier tirage pour choisir le type du second tirage, second tirage pour choisir le prochain noeud). Soit par exemple une fourmi se déplaçant dans le graphe, avec un taux d'attraction et de répulsion des phéromones de respectivement 0,5 et 0,5. Si nous reprenons le choix de mouvement précédent. En fonction du 30 premier tirage, la fourmi a donc 50% de faire son choix en fonction des phéromones attractives et 50% de chance de faire son choix en fonction des phéromones répulsives (P(Atr)=0,5 et P(Rep)=0,5). Avec les probabilités précédemment présentées : 3049743 27 Probabilités en fonction des attractions : P(A)=10/20, P(B)=5/20, P(C)=5/20 En fonction des répulsifs: P(A)=625/2250, P(B)=400/2250, P(C)=1125/2250 5 Soit au total : P(A) = (10/20)*0,5+(625/2250)*0,5 P(B) = (5/20)*0,5+(400/2250)*0,5 et P(C) (5/20)*0,5+(1125/2250)*0,5 Application au problème 10 Dans un exemple de mise en oeuvre, le procédé d'optimisation du réseau de taxiway est utilisé dans le graphe obtenu par la transformation du réseau de taxiway sur une durée de 30 minutes. Les avions pris en compte sont les suivants : - Les avions à l'arrivée dont le STA a été fixé dans les 15 prochaines 15 minutes. - Les avions au départ dont le STOT a été fixé entre 15 et 30 minutes de l'heure actuelle. Ainsi chaque avion a au minimum 15 minutes disponibles pour réaliser son roulage dans cette optimisation (une durée très rarement dépassée, même 20 les aéroports les plus étendus). Une colonie de fourmis est attribuée à chaque avion afin de trouver son chemin. Les fourmis des colonies trouvent un chemin à partir des critères suivants, avec T représentant le temps : Pour un avion à l'arrivée, les fourmis partent du sommet 25 représentant la sortie de piste pour T=STA. Elles ont pour but de joindre un sommet représentant le parking attribué, pour tout T. - Pour un avion au départ, les fourmis partent du sommet représentant l'entrée de piste pour T=STOT. Elles se déplacent en remontant le temps afin de rejoindre un sommet représentant le 30 parking attribué pour n'importe quel T supérieur au TOBT. Afin d'assurer des temps de séparations satisfaisants, les phéromones répulsives peuvent être positionnées sur des sommets adjacents aux sommets du chemin trouvé. 3049743 28 Les phéromones attractives sont positionnées sur les sommets utilisés comme représenté figure 7a. Les phéromones répulsives peuvent être positionnées sur les 5 sommets utilisés mais aussi les sommets adjacents pour obtenir une séparation plus grande comme représenté figure 7b. Le choix de faire partir les colonies de fourmis de la piste plutôt que des parkings est dû au fait que l'heure en piste est une donnée du problème contrairement à l'heure d'entrée ou de sortie de block qui est une variable du 10 problème. Ainsi, toutes les fourmis partent d'un sommet précis du graphe, mais ont plusieurs sommets d'arrivée possibles. L'optimisation permet donc d'obtenir les trajets échantillonnés en temps pour chacun des avions, en assurant des temps de séparations entre 15 ceux-ci et donc de fournir les SOBT et SIBT. Récapitulatif L'optimisation vise à augmenter de manière globale le nombre d'atterrissages et de décollages qu'un aéroport peut accepter. Pour cela, 20 l'ensemble des contraintes de pistes et de taxiways sont prises en compte. A partir de la dernière position renseignée par les avions à l'arrivée et l'heure de départ de parking souhaitée par les avions au départ, l'optimisation permet donc de fournir l'ensemble des résultats suivants comme représenté en figure 8 : 25 Calculer les ETA et TTOT nécessaires à l'optimisation des pistes, avec une grande précision. Calculer les STA et STOT en minimisant leurs différences avec ETA et TTOT précédemment renseignés. Calculer les SIBT et SOBT ainsi que les chemins au sol à utiliser 30 pour l'ensemble des plans de vol afin de répondre aux horaires de la piste, tout en optimisant les temps de roulage. L'optimisation repose au final principalement sur 3 critères : 3049743 29 - L'inclusion de paramètres précis permettant d'améliorer la fiabilité des résultats fournis (données météorologique, différences entre compagnies aériennes, représentation graphique de l'aéroport...). - L'utilisation et le développement d'algorithmes dédiés à des 5 problèmes difficiles. Ces algorithmes permettent de tendre vers des optimums globaux tout en gardant des temps de calcul inférieurs à la seconde. La communication entre les différentes briques de l'optimisation. En séparant le problème en plusieurs parties, l'optimisation est elle 10 aussi découpée en plusieurs phases. Ainsi les solutions obtenus sur l'un des sous-problèmes permet de paramétré les sous-problèmes suivants et faciliter leur résolution. Exemple de mise en oeuvre lorsque la contrainte de respect d'ETA 15 est libérée de sorte que I'ETA est modifiable manuellement : Il est 10:00 à l'aéroport de Genève, ce dernier comportant une unique piste utilisée à la fois pour les décollages et les atterrissages. Le vol AF7681 en provenance de Jakarta est détecté par les radars dans un horizon de 90 min, dès sa phase de croisière. 20 La trajectoire avion 4D de ce vol est déterminée au moyen d'un procédé de détermination de trajectoire connu en soi, et on en déduit son heure précise d'arrivée: 11h05. Le procédé selon l'invention compare cette heure aux différentes autres heures d'arrivées et de départs, calculées pour tous les avions 25 atterrissant et décollant dans un horizon de 90 min. Un conflit est détecté: le vol LH3228 veut décoller à 11h04, et les types des deux avions concernés imposent 3 minutes de séparations entre les deux vols. Le procédé selon l'invention détermine alors une séquence optimale 30 (la meilleure combinaison) des vols à l'arrivée et au départ, en prenant en compte tous les vols dans le même horizon temporel, et en déduit une heure optimale d'arrivée pour le vol AF7681 : 11h02, et une heure optimale de décollage pour le vol LH3228: 11h05, et une heure optimale de repoussage de 3049743 30 son point de parking du vol LH3228, en prenant en compte tous les autres vols utilisant les parkings et les bretelles d'accès au même horizon temporel. Les informations communiquées au contrôleur aérien se présentent dès lors de la façon suivante : Temps à gagner : 3 min Ordre à communiquer au pilote : Augmenter la vitesse de 500km/h à 550km/h pendant 10 minutes puis retour à 500km/h Temps à perdre: 1 min Ordre à communiquer au pilote : Heure de décollage : 11h05, Heure de repoussage 10h56, chemin vers la piste : B1 - B34 - B45 H3228 5 Le contrôleur aérien communique alors ces informations aux pilotes ou décide de faire autrement, auquel cas il renseigne le système avec sa décision, le système prendra en compte cette décision manuelle pour les prochains calculs. 10 Pour une aviation civile et un aéroport donné, le procédé selon l'invention garantit : - une utilisation optimale des pistes (un taux d'utilisation maximale en fonction des contraintes de sécurité et d'environnement), 15 - la réduction des retards au départ et à l'arrivée et une ponctualité du calendrier opérationnel, - une réduction de la charge de travail des contrôleurs, - un équilibre entre les arrivées et les départs au travers d'une bonne gestion des priorités entre les vols, 20 - la réduction des couts d'exploitation (parkings, carburants, etc.), - la réduction de la pollution (atmosphérique et sonore) autour des aéroports. 25 REVENDICATIONS1. Procédé de gestion du trafic aérien d'un aéroport comportant des pistes d'atterrissage/décollage, des zones de stationnement, et des voies de circulation reliant les pistes auxdites zones de stationnement, ledit trafic aérien étant relatif à une pluralité d'avions respectivement associés à des contraintes de séparation amont/avale, à des pistes d'atterrissage/décollage et à des zones de stationnement, ainsi que destinés à rouler sans conflit sur lesdites voies de circulation, caractérisé en ce qu'il comporte les étapes successives suivantes : - une étape (100) d'identification dans un horizon temporel prédéterminé Fit d'un nombre A d'avions constitué de N avions en cours de vol, dits à l'arrivée, et de M avions parqués, dits au départ, où N 0, M 0 et A>0, - une étape (200) de détermination pour chacun desdits M avions au départ d'une durée théorique de roulage sans conflit, - une étape (300) de détermination d'une séquence optimale d'heures d'atterrissage/décollage desdits A avions, au cours de laquelle une durée de roulage sans conflit d'un avion au départ est fixée égale à sa durée théorique de roulage sans conflit, ladite séquence minimisant le retard au décollage et à l'atterrissage respectivement des M avions au départ et des N avions à l'arrivée, - une étape (400) de détermination de durées minimales de roulage sans conflit respectifs desdits A avions, sous contrainte de respect des heures d'atterrissage/décollage de ladite séquence optimale. 2. Procédé selon la revendication 1, dans lequel la durée théorique de roulage sans conflit d'un avion au départ est fonction d'une durée de roulage dudit avion au départ considéré comme seul dans l'aéroport, ainsi que d'un paramètre représentatif du trafic aérien nominal dudit aéroport. 3. Procédé selon la revendication 2, dans lequel la durée de roulage 30 dudit avion au départ considéré comme seul dans l'aéroport est déterminée au moyen d'un algorithme de type Dijkstra. 3049743 36 4. Procédé selon l'une des revendications 1 à 3, dans lequel l'étape (300) de détermination d'une séquence optimale d'heures d'atterrissage/décollage comporte la minimisation d'une fonction objectif F1 décrite par : M N 5 F1 = / (STOT (i) - TTOT (i))+I(STA(i) - ETA(0) -i i-i STOT et STA étant des inconnues correspondant à des heures optimales respectivement de décollage des avions au départ et d'atterrissage des avions à l'arrivée, TTOT et ETA correspondant respectivement à des heures de 10 décollage au plus tôt des avions au départ et des heures d'atterrissage au plus tôt des avions à l'arrivée, TTOT et ETA étant déterminées à partir respectivement des durées théoriques de roulage sans conflit et d'un algorithme de prédiction de trajectoire, les heures ETA respectives des avions à l'arrivée étant des 15 contraintes prioritaires lors de la minimisation de la fonction objectif F1. 5. Procédé selon la revendication 4, dans lequel la fonction objectif F1 est minimisée au moyen d'un premier algorithme de colonies de fourmis, chaque fourmi pouvant déposer des phéromones attractives. 20 6. Procédé selon l'une des revendications 4 à 5, comportant une étape (350) de prise en compte d'une congestion locale du trafic aérien sur l'aéroport, consécutive à l'étape (300) de détermination d'une séquence optimale d'heures d'atterrissage/décollage et antérieure à l'étape (400) de détermination de durées minimales de roulage sans conflit, dans laquelle 25 l'heure ETA d'au moins un avion à l'arrivée est mise à jour de manière forcée. 7. Procédé selon l'une des revendications 4 à 6, dans lequel l'étape (400) de détermination de durées minimales de roulage sans conflit comporte la minimisation d'une fonction objectif F2 décrite par : M N F2 = 1 (STOT (i)- SOBT (i))+I(SIBT (0- STA(0) i=1 i=1 3049743 37 - SOBT et SIBT étant des inconnues correspondant à des heures optimales respectivement de départ de parking des avions au départ et d'arrivée au parking des avions à l'arrivée. 8. Procédé selon la revendication 7, dans lequel la fonction objectif F2 5 est minimisée au moyen d'un deuxième algorithme de colonies de fourmis, chacun desdits A avions étant associés à un nombre prédéterminé C de colonies, et chaque fourmi pouvant déposer des phéromones attractives et des phéromones répulsives. 9. Procédé selon la revendication 8, dans lequel l'influence respective 10 des phéromones attractives et des phéromones répulsives sur le déplacement d'une fourmi est une fonction dudit nombre prédéterminé C. 10. Procédé selon l'une des revendications 1 à 9, dans lequel les étapes 100 à 400 sont exécutées de manière itérative selon un pas de temps prédéterminé, ou de manière asservie.