Chapter 4 Sectorisation de l'espace et répartition des flux

4.1 Introduction

Le contrôle ¹ de la circulation aérienne organise les flux aériens afin d'assurer la sécurité des vols (en terme de risque de collision) et d'améliorer la capacité du réseau de routes sur lequel les avions se déplacent. Suivant la nature du trafic, on distingue les trois types de contrôle suivants :

contrôle d'aérodrome : gestion des phases de roulage, de décollage et d'atterrissage;
contrôle d'approche : gestion du trafic en étape préparatoire à l'atterrissage ou post-décollage dans une zone proche d'un aérodrome;
contrôle en route : il concerne essentiellement le trafic en croisière entre les aérodromes.

Dans le cadre de ce travail, on s'est plus particulièrement intéressé aux problèmes du contrôle en route.

Actuellement on enregistre sur le territoire français environ 4000 mouvements par jour, ce qui représente une charge de contrôle impossible à gérer par un seul contrôleur. On répartit alors cette charge de travail en divisant l'espace aérien en plusieurs secteurs pour chacun desquels on affecte une équipe de contrôleurs. Le nombre de secteurs est alors déterminé par la capacité d'un contrôleur à gérer N avions simultanément (dans la pratique la moyenne semble être de 10 à 15 avions; lorsque cette limite est atteinte on dit que le secteur est saturé). Un des objectifs principaux de la sectorisation est de fournir des secteurs équilibrés en terme de charge de contrôle afin que chaque équipe de contrôleurs travaille de la même façon.

Au cours de ces dernières décennies, au fur et à mesure de l'augmentation du trafic, l'espace aérien a été divisé en secteurs de plus en plus petits afin d'éviter la saturation de ces derniers. Malheureusement, ce principe de resectorisation présente une limite dans la mesure où l'on doit ménager un temps suffisant au contrôleur pour gérer son trafic (élaboration des stratégies de résolution des conflits entre aéronefs) et donc générer des secteurs dont la taille permet de satisfaire cette contrainte. De plus, le contrôleur ne connaît que le trafic lié à son secteur et lorsqu'un avion passe d'un secteur à un autre, il s'opère un dialogue entre les contrôleurs et le pilote afin d'assurer la sécurité du vol lorsqu'il pénètre dans le nouveau secteur (ce dialogue induit une charge de travail supplémentaire pour les contrôleurs appelée charge de coordination). Ainsi, en augmentant le nombre des secteurs, on augmente aussi les coordinations et donc la charge de contrôle globale.

Dans le cadre opérationnel, le principe de resectorisation d'un domaine d'espace aérien est le suivant. Lorsque l'on détecte un secteur qui se trouve souvent en limite de saturation, une équipe d'experts se réunit et propose une nouvelle sectorisation de la zone incriminée. Pour valider cette proposition on procède à deux types de simulations : simulation arithmétique et simulation temps réel. La première consiste à évaluer la sectorisation à l'aide de logiciels de simulation sur trafic enregistré (ou simulé). Si les résultats de ces premières évaluations sont satisfaisants, la sectorisation est ensuite testée en temps réel à l'aide d'un environnement de contrôle simulé faisant intervenir des contrôleurs et des pseudo-pilotes (sur poste de pilotage reconstitué en salle (version simplifiée)). Après cette dernière étape, on modifie les frontières des secteurs sur site et on contrôle que ces changements permettent effectivement de résoudre les problèmes initiaux. On gardera cette sectorisation jusqu'à ce que de nouveaux problèmes apparaissent, liés principalement à la croissance du trafic.

Cette approche est essentiellement locale et aboutit à une sectorisation globale qui est la juxtaposition de régions de contrôle optimisées individuellement. Pour mieux comprendre les méthodes utilisées dans le contrôle du trafic aérien, on pourra consulter les références [Mai91, Vil84, CDV92].

Le travail de Daniel Delahaye se décomposait en trois parties principales :

Sectorisation d'un réseau à flux affectés :: il s'agit de réaliser une sectorisation équilibrée de l'espace en fonction des flux affectés sur le réseau de routes.
Affectation des flux sur un réseau sectorisé :: résolution du problème dual : l'affectation des avions sur les routes aériennes, la sectorisation étant fixée.
Optimisation simultanée de la sectorisation et de l'affectation de trafic :: Partant simplement des demandes de trafic entre les paires Origine-Destination, il s'agit de construire simultanément une sectorisation et une affectation des avions sur les routes.

4.2 Modélisation

4.2.1 Routes aériennes

Lorsqu'un avion relie deux villes du continent européen, on pourrait s'attendre à ce que la route directe soit utilisée systématiquement pour des questions d'économie de carburant. En réalité, les avions suivent des routes aériennes constituées d'une succession de tronçons orientés différemment dont les extrémités correspondent à des balises qui matérialisent souvent les croisements de routes. En préparant sa navigation, le pilote jalonne sa route de points de report (balises) sur lesquels il devra faire un passage à la verticale afin de confirmer sa position. Le nombre de balises au sol étant limité, la route réellement suivie s'écartera plus ou moins de la route idéale en fonction de la disposition locale de ces dernières.

Ce principe de navigation par jalonnement sur balises est pénalisant en terme de consommation car il induit des rallongements de route systématiques ; actuellement en Europe, le réseau de routes aériennes provoque des rallongements moyens de 9 %, soit 420000 heures de vol supplémentaires par an ou 1.2 million de tonnes de kérosène. Les avions modernes sont maintenant équipés de calculateur de bord qui, lorsqu'ils sont couplés au pilote automatique, sont capables de suivre avec une grande précision n'importe quelle route définie par un point origine et un point destination, dont les coordonnées sont introduites par l'équipage ou sont extraites d'une base de données du calculateur de bord. Malheureusement, ce système de progression de point à point n'est pas encore possible pour deux raisons. D'une part, il existe dans beaucoup de pays un assez grand nombre de zones réservées aux militaires qui doivent être contournées par les routes aériennes civiles, d'autre part, le contrôle de la circulation aérienne n'est pas capable d'assurer un écoulement sûr et ordonné du trafic lorsque chacun va directement de son point de départ à son point de destination. L'aiguilleur du ciel a besoin pour travailler de points de report par rapport auxquels il peut situer son trafic.

Une route aérienne pouvant être utilisée dans les deux sens, il a été élaboré une règle de séparation verticale (règle semi-circulaire) imposant des altitudes de vol aux aéronefs afin d'assurer des croisements en toute sécurité. Dans un soucis de simplicité, une route aérienne sera donc simplement modélisé par un arc bidirectionnel joignant deux balises.

Le réseau aérien sera donc modélisé par un réseau de transport qui aura les propriétés suivantes :

Il est pilotable car il nous est possible d'imposer des routes aux avions par l'intermédiaire des contrôleurs
Les coûts d'arcs sont non séparables : en effet, le nombre moyen de conflits entre aéronefs à la verticale d'une balise est proportionnel aux flux sur les deux routes aériennes. Il faut bien se rappeler que la résolution d'un conflit induit une charge de contrôle importante et provoque parfois des modifications de navigation pénalisant la consommation. Le coût sur un arc dépend donc des coûts sur les autres arcs, d'où la non-séparabilité.
Les coûts d'arcs sont asymétriques : en effet, si l'on route des avions vers des secteurs déjà chargés, on peut provoquer la saturation du secteur et donc le refus du contrôleur en charge de ce secteur d'accepter ces nouveaux avions et donc des coûts de déroutement assez élevés quand bien même il n'y a pas beaucoup de trafic (donc de congestion) sur la route initialement choisie.

Les demandes de trafic des usagers sont ensuite distribuées sur le réseau (à l'initiative des utilisateurs ou par l'intermédiaire d'un processus d'affectation de trafic ou les deux). En supposant que les avions se déplacent à des vitesses moyennes quasi-identiques (homogénéité du trafic), la répartition de flux induite fait apparaître une charge de contrôle répartie dans l'espace que nous nous proposons maintenant de modéliser avant de décrire les problèmes qu'il nous faut résoudre.

4.2.2 Charge de contrôle dans un secteur

Introduction

Un secteur de contrôle est un domaine limité de l'espace traversé par des routes aériennes, pour lequel une équipe de contrôleurs assure la sécurité des vols qui y transitent en séparant les aéronefs entre eux. Plus le nombre d'avions dans un secteur est important, plus la charge de contrôle induite augmente (de façon non linéaire). Il existe une limite au delà de laquelle le contrôleur en charge du secteur ne peut plus accepter de nouveaux avions et oblige ces derniers à contourner le secteur en traversant des secteurs voisins moins chargés. On dit alors que le secteur est saturé. Cet état critique doit être évité car il provoque un phénomène cumulatif de surcharge sur les secteurs amonts pouvant remonter jusqu'aux aéroports de départ. En effet, lorsque le trafic ne peut être dévié, il est mis en attente dans les secteurs amonts faisant augmenter progressivement la charge de contrôle de ces derniers jusqu'à ce qu'ils soient saturés. Le seuil au delà duquel le secteur est saturé est très difficile à estimer car il dépend de la géométrie des routes qui le traversent, de la géométrie du secteur lui-même, de la répartition des avions sur les routes, des performances de l'équipe de contrôle etc. Un seuil généralement admis est de 3 conflits et 15 avions dans un secteur donné. Cette charge maximum ne doit pas perdurer plus de 10 minutes car elle provoque un fort stress des contrôleurs qui risquent alors de ne plus pouvoir assurer la gestion du trafic dans des conditions optimales de sécurité.

Après une enquête auprès des contrôleurs on remarque que la charge de travail dans un secteur dépend des critères qualitatifs et quantitatifs. Les critères qualitatifs regroupent essentiellement les facteurs humains dont le principal est le stress. Tous les contrôleurs ne réagissent pas de la même façon face à une situation de trafic difficile et il est donc délicat de fournir un modèle ``mathématique'' de stress applicable à tous les contrôleurs. On peut seulement préciser que le stress est directement lié aux critères quantitatifs suivants :

charge de conflit;
charge de coordination;
charge de monitoring.

Il existe d'autres charges de contrôle [TPC76] facilement quantifiables mais leur impact sur l'ensemble de la charge secteur est négligeable par rapport aux trois précédentes.

Nous allons dans un premier temps, préciser et quantifier chacune de ces trois charges de contrôle avant de fournir un modèle mathématique de la charge globale dans un secteur.

Charge de résolution des conflits

On dit que deux avions sont en conflit lorsque la distance qui les sépare risque de devenir inférieure à une valeur particulière appelée norme de séparation. Lorsque deux avions sont en conflit, le contrôleur doit modifier la route des avions afin d'assurer le respect des normes de séparation.

Suivant l'angle de croisement des routes aériennes les conflits sont plus ou moins faciles à résoudre car les avions sont plus ou moins longtemps en situation conflictuelle.

En supposant que la charge de contrôle à la verticale du croisement est proportionnelle au nombre de conflits générés, on a C_re=a(q_ijl)f_ijf_lj dans le cas d'un croisement à deux routes, où a(q_ijl) est un coefficient de proportionnalité dépendant de l'angle de croisement entre les routes, et f_ij et f_lj les flux sur les arcs (i,j) et (l,j). Lorsque le croisement comporte plus de deux routes incidentes, la charge de conflit est la somme des charges induites par les arcs pris deux à deux. La charge de conflit dans un secteur S est alors la somme des charges de conflits sur chacun des noeuds contenus dans ce secteur.

Charge de coordination

Tous les avions qui sont dans un même secteur communiquent au moyen de la même fréquence avec le contrôleur en charge du secteur. Lorsqu'ils changent de secteur, ils doivent changer de fréquence et il s'opère alors un transfert de contrôle. Ce transfert doit avoir fait l'objet au préalable d'une négociation entre le contrôleur qui transfère et le contrôleur qui reçoit, pour assurer que celui-ci peut accepter l'avion et pour définir les modalités (niveau de vol, etc) selon lesquelles l'opération a lieu. Un transfert nécessite un travail relativement important de la part des deux contrôleurs; de plus c'est une opération au cours de laquelle des incompréhensions ou des erreurs peuvent se produire causant des pertes accidentelles de séparation. Les charges de contrôle induites par ces transferts sont regroupées dans une charge unique appelée coordination. Dans un réseau de transport sectorisé la charge de coordination est proportionnelle aux flux coupés par les frontières des secteurs. En étudiant la charge de coordination générée par un arc (i,j) de route aérienne dont une partie ou la totalité appartient à un secteur S_k, on peut identifier trois cas de figure :

Les deux extrémités de l'arc appartiennent au secteur S_k auquel cas la charge de coordination est nulle.
Une seule extrémité de l'arc appartient au secteur S_k Il existe donc une intersection entre l'arc (i,j) et la frontière du secteur S_k. On peut alors représenter la charge de coordination par : C_co=b_ijf_ij où b_ij est un coefficient de proportionnalité permettant de pondérer l'influence de la coordination par rapport aux autres charges de contrôle.
Les deux extrémités de l'arc sont extérieures au secteur S_k ; dans ce cas le flux est coupé deux fois. On peut alors modéliser la charge par : C_co=2b_ijf_ij

Charge de monitoring

Dans un secteur de contrôle les avions qui ne sont pas en conflit ou en transfert nécessitent une surveillance de la part du contrôleur qui vérifie le bon déroulement des plans de vol sur l'image radar et qui essaye de déterminer les risques potentiels de conflits futurs induits par ces avions. Le monitoring est en fait la tâche de fond du contrôleur et représente une source importante de stress pour ce dernier. Cette charge de contrôle est directement liée au nombre d'avions présents dans le secteur de contrôle. Pour un secteur S_k on peut la modéliser par : C_mo(S_k)=hS_{(i,j) Î L_k}p_ij(k)f_ij; avec :

p_ij(k) proportion de l'arc (i,j) contenue dans le secteur S_k;
h : coefficient de proportionnalité.

La charge de contrôle dans un secteur est donc la somme de la charge de conflit, de la charge de coordination et de la charge de monitoring.

Disposant maintenant d'un modèle mathématique du réseau aérien ainsi que de la charge de contrôle (qu'il nous faudra confronter à la réalité), nous pouvons formaliser la description des deux problèmes que nous nous sommes attachés à résoudre.

4.3 Problèmes à résoudre

4.3.1 Problème de sectorisation

A partir de la connaissance de la répartition surfacique (réseau à deux dimensions) de la charge de contrôle, on se propose de trouver une sectorisation équilibrée aboutissant à un rendement homogène des équipes de contrôle en charge de l'ensemble de l'espace aérien. En examinant cette charge de contrôle et en faisant abstraction, dans un premier temps, de la charge de coordination, on remarque qu'elle comporte deux composantes spatiales distinctes :

une composante discrète localisée au niveau des noeuds (conflits);
une composante continue répartie sur les arcs (monitoring).

Lorsque l'on met en place des frontières de secteur, ces dernières coupent des arcs de routes aériennes générant a posteriori une nouvelle charge de contrôle (coordination) pouvant remettre en cause l'équilibre obtenu pour les deux critères précédents (conflit et monitoring). Un petit exemple simple nous permet de mieux comprendre ce problème. Sur la figure 4.1 la sectorisation est initialement équilibrée (à 50) pour les charges de conflit et de monitoring. Si l'on tient compte des coordinations dans l'équilibrage, on constate un déséquilibre net des nouvelles charges de contrôle dans les secteurs. De fait, ce n'est qu'après avoir pris la décision de sectoriser que l'on sait a posteriori si les secteurs sont équilibrés ou non. Une analogie avec la mécanique nous permet de mieux sentir ce problème. Si l'on assimile la charge de contrôle à une masse, notre réseau de transport peut être modélisé par un ensemble de boules denses réparties aux noeuds, reliées entre elles par des barres pesantes. Notre objectif initial est donc de rechercher une sectorisation pour laquelle chaque secteur a la même masse. Le problème est que l'on ajoute des ``masses de coordination'' lorsque l'on coupe des barres modifiant ainsi l'équilibre calculé. Ce premier objectif d'équilibrage est important mais doit être complété par un objectif connexe de minimisation des coordinations. En effet, si l'on se contente seulement de rechercher l'équilibrage, on risque d'obtenir des aberrations en terme de contrôle dont un exemple extrême est donné figure 4.2. On remarque sans difficulté que le cas 2 est nettement meilleur en terme de contrôle quand bien même il est moins équilibré.

Figure 4.1: Influence de la coordination sur l'équilibrage a posteriori

Figure 4.2: Importance de la minimisation des coordinations

Enfin, la sectorisation construire doit prendre en compte certaines contraintes :

Convexité de routes :: Lorsque l'on examine la sectorisation actuelle ainsi que le réseau de routes associé, on remarque que pour chacun des trajets possibles reliant une paire Origine-Destination, les secteurs rencontrés ne sont traversés qu'une seule fois. Ainsi un pilote ne contacte qu'une seule fois le contrôleur en charge du secteur qu'il traverse.
Temps minimal de résolution :: Lorsqu'un contrôleur détecte un conflit entre deux avions, il doit se ménager un délai suffisant afin d'élaborer un processus de résolution adapté. Or, comme nous l'avons vu précédemment, les conflits entre aéronefs sont localisés aux croisements des routes aériennes et donc sur les noeuds du réseau de transport. De plus, le trafic géré par un contrôleur est limité au secteur dont il a la charge et il ne dispose pas d'informations sur le trafic présent dans les secteurs voisins. Si au moment où un avion lui est transféré ce dernier se trouve en conflit, le contrôleur n'a pas le temps de construire un processus de résolution. Pour éviter ce problème, il faut éloigner suffisamment les frontières des secteurs des points de croisement afin de ménager un temps minimum de résolution au contrôleur recevant les avions. Ceci induit une seconde contrainte, dite contrainte de sécurité : la distance entre un noeud et une frontière de secteur sera au moins égale à une distance de sécurité de l'ordre de 50NM.
Temps minimal de séjour :: pour qu'un contrôleur puisse agir facilement sur les vols présents dans son secteur, ces derniers doivent y séjourner un temps suffisant égal au temps de sécurité. Un avion devra rester un temps minimum dans chacun des secteurs qu'il traverse.

Le problème de sectorisation peut donc se formuler de la façon suivante : Soit un réseau de transport dans un espace à deux dimensions sur lequel une répartition de flux produit une charge de contrôle répartie dans l'ensemble de l'espace aérien. On se propose de sectoriser cet espace en K secteurs équilibrés (en terme de charge de contrôle) en minimisant les coordinations. Cette sectorisation devra respecter les contraintes de convexité de route, de sécurité aux balises et de temps de séjour minimum.

4.3.2 Problème d'affectation

L'affectation de trafic a pour but de définir les routes des flux aériens afin de réduire la charge de contrôle et donc d'augmenter la capacité du système même si cela doit se faire au détriment des performances individuelles. L'amplitude de ces modifications de route doit être suffisamment faible pour que la pénalisation sur les coûts de transport soit comparable au gain apporté sur les performances ATC. Il y a donc un compromis à trouver entre performances ATC et pénalisation des routes, sachant qu'il existe des intérêts communs au système ATC et aux compagnies aériennes. Pour des raisons d'équité, on ne peut faire suivre des routes différentes à des avions joignant la même paire Origine-Destination. En effet, l'avion qui serait routé sur une route plus longue en distance, trouverait ce choix injuste, même s'il permet de diminuer fortement le coût global de transport. Ainsi, si l'on veut que la libre concurrence s'exerce entre les compagnies, sans pour autant laisser toute la liberté à ces dernières pour choisir leurs routes, provoquant des surcharges secteurs anarchiques, il faut nous astreindre à placer les avions sur la même route. Dans la suite de ce rapport cette contrainte sera appelée : contrainte d'équité. Notre objectif final étant l'optimisation de la sectorisation (dont les modifications se font à longue échéance), on ne prendra pas en compte l'aspect dynamique du trafic et nous nous attacherons à travailler sur des flux d'avions macroscopiques. De plus, on se placera dans le cas le plus défavorable consistant à prendre les demandes de trafic maximum entre chaque paire Origine-Destination.

Le problème d'affectation peut donc s'énoncer ainsi : Soit un réseau de transport dans un espace à deux dimensions, divisé en K secteurs. On désire affecter le trafic entre chaque paire Origine-Destination, en respectant la contrainte d'équité, afin de minimiser la charge de contrôle tout en réduisant les rallongements induits.

4.4 Complexité associée

4.4.1 Problème de sectorisation

Le problème de sectorisation peut être décomposé en deux sous-problèmes presque indépendants, correspondant aux deux objectifs fixés :

équilibrage des charges secteur;
minimisation des coordinations.

Le premier sous-problème est discret-continu NP_complet (discret : équilibrage des charges de conflit et de coordination; continu : équilibrage des charges de monitoring). En effet, en ne considérant que la partie discrète liée aux charges de conflit et de coordination, le problème est équivalent à un K_Partitionnement de graphe en composantes connexes qui est connu pour être NP_complet [Che92]. Le sous-problème de minimisation des coordinations est aussi un K_partitionnement de graphe à minimisation de flux coupés et est donc NP_complet. On peut donc raisonnablement penser que la combinaison de ces deux problèmes est aussi NP_complet.

4.4.2 Problème d'affectation

En considérant, le réseau sans trafic, notre problème consiste à affecter les demandes de chaque paire Origine-Destination sur le chemin qui minimise le critère global C_s. Ainsi pour chaque paire Origine-Destination, on associera un chemin d'affectation de la demande qui produira globalement une répartition de flux sur chacun des arcs du réseau. Les points de notre espace d'état sont donc constitués de l'ensemble des paires Origine-Destination auxquelles on associe la liste des noeuds constituant le chemin d'affectation.

La complexité de notre problème est liée à la non séparabilité des coûts qui rend l'affectation dépendante de l'ordre dans lequel on traite les diverses paires Origine-Destination. Ainsi, s'il n'existe pas d'autre principe de résolution que l'algorithme trivial d'énumération des points de l'espace d'état, on peut supposer que notre problème est NP_complet.

4.5 Sectorisation d'un réseau à flux affectés

4.5.1 Introduction

Nous allons ici résoudre le problème de sectorisation d'espace en secteurs convexes équilibrés ² . Pour cela on considère un réseau de transport à deux dimensions sur lequel sont affectées des demandes de trafic (Origine-Destination) entre les divers centroïdes induisant une répartition spatiale des flux. Cette répartition de flux génère une charge de contrôle dans l'espace qu'il nous faut maintenant sectoriser. Chacun des secteurs ainsi créés sera ensuite attribué à une équipe de contrôleurs qui aura la responsabilité du trafic qui y transitera.

Lorsqu'un contrôleur arrive sur une nouvelle position de contrôle, il lui faut entre trois et quatre mois d'apprentissage pour acquérir les réflexes de gestion du trafic associés à ce nouveau secteur. Ce long délai de formation impose une certaine stabilité de la sectorisation dans un centre de contrôle quand bien même une sectorisation dynamique serait parfois plus adaptée. En effet, pour chaque répartition de trafic sur le réseau, il existe une sectorisation optimale. Mais celle-ci serait inefficace si elle est changée toutes les heures car aucune équipe de contrôleurs ne peut la gérer. La sectorisation résulte donc d'un compromis. Elle est calculée pour accepter la charge de contrôle maximale aux heures de pointe mais elle devient sous-optimale pendant les heures creuses. Les flux sur le réseau qui sont considérés pour la sectorisation sont des flux moyennés correspondant aux périodes de fort trafic.

4.5.2 Modélisation

Charge de contrôle

Comme nous l'avons vu au chapitre 2 la charge de contrôle est la somme de trois termes :

la charge de conflit C_cf(S_k) ;
la charge de coordination C_co(S_k) ;
la charge de monitoring C_mo(S_k) ;

Þ C(S_k) = C_cf(S_k) + C_co(S_k) + C_mo(S_k).

Si l'on considère la charge globale de contrôle C_gl, la répartition optimale de charge dans une sectorisation à K secteurs est donnée par :

C(S_k)_Opt =

C_gl

A partir de cet optimal, on peut élaborer un critère d'équilibrage relatif C_E :

C_E =

k=1

|C(S_k) -

C_gl

0 £ C_E £ (2 K - 1)

Si l'on veut se rapprocher d'un équilibre sur chacune des charges de contrôle, il faut appliquer cette formule aux conflits, à la coordination ainsi qu'au monitoring et le critère d'équilibrage relatif devient :

C_E =

k=1

(cf)(S_k)

C_gl(cf)

k=1

(co)(S_k)

C_gl(co)

k=1

(mo)(S_k)

C_gl(mo)

Avec cette deuxième forme, on conçoit très bien qu'il sera plus difficile et même parfois impossible d'annuler le critère car certains réseaux ne peuvent pas être équilibrés pour les trois types de charges.

La minimisation de la coordination sera établie en réduisant la part relative de coordination par rapport aux charges globales de conflit et de monitoring :

C_C =

k=1

C_co(S_k)

C_gl(cf) + C_gl(mo)

On voit bien ici que notre problème est un problème multi-objectifs mais dans un premier temps et dans un souci de simplification nous nous ramenons à un problème mono-objectif en élaborant un critère global C_G qui est une pondération des deux précédents : C_G= a C_E + (1-a) C_C; avec 0 £ a £ 1.

Principe de construction des secteurs

Il nous faut tout d'abord une méthode permettant de générer des populations d'individus dans l'espace d'état. Pour atteindre cet objectif, on utilise le principe d'agrégation de Forgy [Sap90] utilisé dans les nuées dynamiques en statistique exploratoire et qui permet d'extraire des clusters d'un ensemble de points répartis dans un espace muni d'une distance.

Une méthode simple pour obtenir un K-partitionnement d'un domaine D consiste à ``jeter'' aléatoirement dans le domaine D un ensemble de K points (appelés centres de classe) et de regrouper chacun des points contenus dans D à son centre de classe le plus proche (principe d'agrégation). Pour éviter d'avoir des secteurs vides, il faut interdire à deux centres de classes d'occuper la même position dans D. Il est facile de prouver que les secteurs ainsi générés sont géométriquement convexes. Cette propriété de convexité géométrique est plus forte que la convexité de route et permet donc de respecter la contrainte associée (pour un arc de route aérienne)³ . On peut également aisément vérifier qu'à chaque ensemble de centres de classe C correspond une sectorisation unique en K secteurs convexes du domaine D (la réciproque est fausse).

Ce principe de synthèse de sectorisation est simple à mettre en oeuvre car il nécessite peu d'informations (les positions géographiques des centres de classe) pour définir complètement l'ensemble des secteurs et satisfait la contrainte de convexité.

Prise en compte des autres contraintes

Les contraintes de sécurité et de temps de séjour minimum sont prises en compte à l'aide d'un coefficient de pénalité qui majore artificiellement la coordination sur les arcs qui violent les contraintes. La nouvelle charge de coordination sera exprimée de la façon suivante :

C_co(S_k)=

i Î N_k

Å j Î N_k

d b_ijf_ij +

i Ï N_k

j Ï N_k

(i,j) Î L_k

2 d b_ijf_ij

Å : ou exclusif ; le coefficient de pénalité d modélisant le dépassement des contraintes est calculé de la façon suivante ; Soit p_ij^k la longueur relative du segment de l'arc (i,j) contenu dans le secteur S_k et L_ij la longueur totale de l'arc (i,j). Si la portion d'arc contenu dans le secteur S_k est inférieure à la distance de sécurité, il faut majorer la coordination associée :

ì
ï
ï
í
ï
ï
î

Si (p_ij^k . L_ij) < d_secu alors d = e

-[2(

p_ij^k . L_ij

d_secu

-1)]

;

Sinon d =1

On traite ainsi de la même façon les deux contraintes.

A partir de cette formalisation, il nous est possible de développer un principe d'optimisation utilisant les algorithmes génétiques.

4.5.3 Optimisation du problème par Algorithmes Génétiques

Introduction

Dans un premier temps, les algorithmes binaires ont été utilisés pour résoudre ce problème. Le codage du chromosome associé à ce type d'algorithme est constitué de la concaténation du codage binaire de la position de chacun des centres de classe définissant une sectorisation (voir figure 4.3).

Figure 4.3: Codage binaire

Ce codage permet ensuite d'utiliser les opérateurs de croisement et de mutation standard. Après évaluation, on remarque que ce type d'algorithme génétique se comporte correctement pour des petits réseaux (< 20 noeuds) mais lorsque la taille du réseau augmente, il se produit un phénomène de marche aléatoire, lié principalement à la brutalité des opérateurs de croisement et de mutation qui font abstraction de la notion de centres de classe mais travaillent seulement au niveau des bits. Il y a perte de la structure du problème et ceci nous a conduit à changer le codage de l'algorithme en utilisant des algorithmes génétiques opérant sur des données plus complexes. Nous présentons maintenant ce nouveau codage ainsi que les opérateurs associés.

Codage du chromosome

Le chromosome doit contenir l'ensemble des informations nécessaires à l'évaluation de la fitness. Comme nous l'avons dit précédemment la connaissance de la position des centres de classe dans l'espace géographique est suffisante pour définir la sectorisation et donc évaluer ses performances. Ces informations sont codées dans le chromosome à l'aide d'une matrice (de dimensions K x 2) contenant les abscisses et les ordonnées des centres de classe. Un exemple de codage d'un chromosome est donné en figure 4.4.

Figure 4.4: Codage du chromosome

Comme il n'y a pas bijection entre le codage du chromosome et la sectorisation associée, une même sectorisation peut être générée par plusieurs ensembles de centres de classe différents. Toutefois lorsque le nombre de secteurs est important, ce qui est notre cas, il est quasiment impossible qu'un tel événement se produise au sein d'une population. En excluant ce cas de similitude très rare, où deux ensembles de centres de classe génèrent la même sectorisation, il faut remarquer qu'un même ensemble de centres de classe peut être codé par une multitude de chromosomes différents. En effet, toute permutation des centres de classe effectuée à l'intérieur d'un même chromosome, génère le même ensemble, donc la même sectorisation. Ainsi, le nombre de chromosomes synthétisant la même sectorisation est égale à K !. Pour une sectorisation à trois secteurs il y aura donc 3 ! = 6 chromosomes possibles ayant les mêmes centres de classe :

(C₁,C₂,C₃);(C₁,C₃,C₂); (C₂,C₁,C₃);(C₂,C₃,C₁); (C₃,C₁,C₂);(C₃,C₂,C₁).

Ce dernier point aura des répercussions dans le calcul de la distance inter-chromosomes pour le sharing d'état.

Principe de génération de la population initiale

Le processus de génération de la population initiale est immédiat. En effet, pour chaque individu contenu dans la population, on tire aléatoirement et de manière uniforme K couples de coordonnées géographiques représentant les K centres de classe définissant chaque sectorisation.

Opérateur de croisement

Pour ce type de problème nous avons testé deux types de croisement :

``slicing crossover'';
croisement barycentrique.

Le premier correspond au croisement classique utilisé dans les algorithmes génétiques binaires mais implanté ici avec des chaînes de flottants. Ce croisement consiste à tirer aléatoirement une position dans le chromosome et à échanger les deux sous-chaînes ainsi produites (voir figure 4.5).

Figure 4.5: Slicing crossover

Le second consiste à tirer aléatoirement un centre de classe dans chacun des chromosomes puis à joindre artificiellement ces derniers par une ligne droite ; ensuite on déplace aléatoirement (distribution uniforme) les centres sur cette ligne afin de générer deux nouveaux individus. La position des nouveaux centres de classe est alors donnée par :

C₁=a P₁ + (1-a)P₂

C₂=(1-a)P₁ + a P₂

(voir figure 4.6 (dans cet exemple le gène 2 a été sélectionnée)).

Figure 4.6: Croisement et mutation

Ce dernier type de croisement est plus adapté pour les espaces continus et fournit de meilleurs résultats sur notre problème qui comporte une composante continue.

Opérateur de mutation

Pour muter un chromosome, on tire aléatoirement une position dans le chromosome puis on déplace le centre de classe associé en ajoutant du bruit à chacune de ses coordonnées suivant une loi de distribution particulière. Un exemple de mutation est donné en figure 4.6.

Introduction de la distance inter-chromosomes pour le sharing

Pour faire du sharing, il faut être capable d'estimer la distance entre deux chromosomes dans l'espace d'état afin de déterminer le niveau d'agrégation des individus. Les chromosomes étant des concaténations de vecteurs en dimension deux, la méthode la plus simple pour calculer cette distance consiste à faire la somme des distances euclidiennes inter-centre de classe pris deux à deux dans l'ordre où ils apparaissent dans le chromosome. Cette méthode conduit à des erreurs importantes car comme nous l'avons dit dans la section précédente, un même ensemble de centres de classe peut être codé de multiples façons, induisant des valeurs de distance non nulles pour deux codages différents d'une même sectorisation, ce qui est contraire à l'objectif recherché dans le sharing.

Exemple :

soient deux individus

I₁={(10,10);(20,20);(30,30)}

I₂={(30,30),(20,20),(10,10)}

ici d(I₁,I₂) = ((20²+20²)⁽1/2) + ((20²+20²)⁽1/2) = 57

Pour éviter ce problème, il faut calculer la somme des distances des centres de classe les plus proches contenus dans chacun des chromosomes. Ainsi, on commence par rechercher dans I₂ le centre le plus proche d'un centre de I₁. On calcule la distance associée puis on élimine ces deux centres de I₁ et I₂ respectivement en itérant ce processus sur les centres restants.

Calcul du barycentre entre deux chromosomes

Le chromosome étant défini dans un espace vectoriel, le calcul du barycentre entre deux individus est direct. En effet, soient deux individus I₁ et I₂ auxquels on associe les coefficients barycentriques n₁ et n₂. Pour chaque centre de classe de I₁ on recherche dans I₂ le centre le plus proche. Soient C₁ et C₂ les positions géographiques de ces centres, alors le centre barycentrique est donné par :

C_B=

n₁ C₁ + n₂ C₂

n₁ + n₂

;

On élimine ensuite ces deux centres des individus I₁ et I₂ avant d'appliquer le même processus sur les centres restants. Un exemple graphique d'une sectorisation barycentrique à coefficients unitaires (n₁=1 et n₂=1) est donné sur la figure 4.7.

Figure 4.7: Exemple de sectorisation barycentrique

Pour chaque individu il nous faut maintenant déterminer son adaptation qui sera utilisée dans le processus de sélection des algorithmes génétiques.

Calcul et normalisation de la fitness

Pour chacun des secteurs synthétisés par le chromosome, on évalue les charges de conflit, de coordination et de monitoring associées. La charge de conflit aux noeuds étant indépendante de la sectorisation, elle est calculée une seule fois au début du processus de résolution ; seule la classification des noeuds dans les différents secteurs sera effectuée à chaque évaluation de fitness. Pour les deux autres charges, il nous faut déterminer pour chaque arc :

la répartition sectorielle du flux sur l'arc (c'est-à-dire la répartition du flux dans les différents secteurs) ;
le nombre de frontières de secteur qui coupent cet arc.

Ces deux quantités sont recherchées par dichotomie pour chacun des arcs constituant le réseau de transport. On considère pour cela les positions géographiques des noeuds extrémités de l'arc (segment [N_o,N_d]) que l'on traite, ainsi que la position des centres de classe permettant de synthétiser la sectorisation (voir figure 4.8).

Figure 4.8: Répartition sectorielle d'un arc

On effectue ensuite une recherche dichotomique en parcourant le segment [N_o,N_d], afin de déterminer les centres de classe les plus proches de chacun des points de l'arc et donc la répartition sectorielle associée (on ne calcule pas l'équation des droites constituant les frontières des secteurs). A partir des charges de conflit aux noeuds et de la répartition sectorielle de flux, on déduit les trois charges associées à chacun des secteurs et ceci nous permet ensuite de déterminer les critères d'équilibrage et de coordination utilisés dans l'évaluation finale de la fitness.

Mixage de l'AG avec une méthode déterministe

Le principe d'évaluation décrit précédemment correspond à la version de base de l'algorithme dont nous donnons maintenant une amélioration, basée sur le mixage de l'AG avec une technique déterministe d'équilibrage.

Connaissant les charges de contrôle associées à chacun des secteurs, il nous est facile de déterminer les secteurs les plus chargés et d'en déduire une tendance de déplacement des centres de classe permettant de diminuer l'écart de masse entre les secteurs. En effet, si l'on considère une répartition surfacique homogène de masse dans un rectangle et en examinant la situation initiale décrite sur partie gauche de la figure 4.9, on conclut facilement qu'il faut déplacer les centres à droite pour se rapprocher de l'équilibre. Ce principe d'équilibrage a été implanté au niveau de l'évaluation des fitness de l'algorithme génétique. En effet, c'est à ce niveau que l'on calcule les diverses charges de contrôle des secteurs et que l'on peut effectivement déduire le déséquilibre associé. A partir de la connaissance des écarts de ``masse'' entre les secteurs, on déduit les directions de déplacement des centres de classe qui permettent de nous rapprocher de l'équilibre.

Figure 4.9: Équilibrage et densité surfacique de masse

Pour comprendre le principe de rééquilibrage déterministe utilisé, nous allons prendre le cas simple d'une sectorisation à deux secteurs sachant que nous avons étendu cette méthode aux sectorisations à ``K'' secteurs. Nous considérons alors une densité surfacique de masse r(x,y) répartie sur un rectangle de dimension X.Y (voir figure 4.9). Ce rectangle est ensuite sectorisé à l'aide de centres de classe jetés aléatoirement dans cet espace. Pour simplifier la démarche (sans perte de généralité) nous supposons que les centres de classe se trouvent sur une droite horizontale parallèle à la médiane horizontale ``d''. Les masses associées à ces deux secteurs sont alors données par :

m₁=

ó
õ

X_M

r(x,y) dxdy; m₂=

ó
õ

X_M

r(x,y) dxdy;

où M est le point médian du segment [C₁,C₂] :

X_M=

x₁+x₂

; Y_M=

A l'aide de ces masses, on peut calculer les positions des centres de gravité associés à chacun des secteurs S₁,S₂ ainsi que le centre de gravité total : G₁,G₂,G.

On appelle centre géométrique :

G_M=

æ
ç
ç
ç
è

G₁+G₂

ö
÷
÷
÷
ø

Le fonctionnement de l'algorithme est alors basé sur la remarque suivante :

Les deux secteurs sont équilibrés lorsque le centre de gravité est confondu avec le centre géométrique⁴ .

On cherchera donc à induire des déplacements des centres de classes tendant à rapprocher ces deux points. Plus précisément il faut déplacer le centre géométrique vers le centre de gravité. La difficulté vient du fait que l'on ne peut pas changer l'un sans modifier l'autre.

Nous allons alors envisager deux approches :

Approche analytique :

En revenant à notre exemple et en considérant r(x,y) constant (=r₀=1), on a :

ì
í
î

m₁=YG_Mx

m₂=Y(X-G_Mx)

et

G_x=

m₁G_1x + m₂G_2x

m₁+m₂
=

G_MxG_1x+(X-G_Mx)G_2x

X

On se propose de trouver le déplacement D à ajouter à x₁ et à x₂ qui permettent d'annuler l'écart entre G_M et G. On pose :

ì
í
î

x'₁=x₁+D;

x'₂=x₂+D

Après déplacement on a :

G'_x=

G'_MxG'_1x + (X-G'_Mx)G'_2x

X
;

On montre sans difficulté que l'écart G' - G'_M s'annule pour :

D=

X

2
- G_Mx.

Approche itérative : Soit la série Uⁿ=|m₁ⁿ-m₂ⁿ| où n représente le numéro de l'itération courante. Soit :

Dⁿ=Gⁿ-G_Mⁿ=

m₁ⁿ-m₂ⁿ

2(m₁ⁿ+m₂ⁿ)

[

G₁ⁿ - G₂ⁿ

]

Posons :

ì
ï
ï
ï
ï
í
ï
ï
ï
ï
î

x₁ⁿ⁺¹=x₁ⁿ+

D_xⁿ

x₂ⁿ⁺¹=x₂ⁿ+

D_xⁿ

avec

D_xⁿ=

X-(x₁ⁿ+x₂ⁿ)

On a :

m₁ⁿ=Y

æ
ç
ç
ç
è

x₁ⁿ+x₂ⁿ

ö
÷
÷
÷
ø

m₂ⁿ=Y

é
ê
ê
ê
ê
ë

X-

æ
ç
ç
ç
è

x₁ⁿ+x₂ⁿ

ö
÷
÷
÷
ø

ù
ú
ú
ú
ú
û

m₁ⁿ⁺¹=m₁ⁿ+Y

D_xⁿ

m₂ⁿ⁺¹=m₂ⁿ-Y

D_xⁿ

D_xⁿ=

X-(x₁ⁿ+x₂ⁿ)

æ
ç
ç
ç
ç
ç
ç
ç
è

X-

2m₁ⁿ

ö
÷
÷
÷
÷
÷
÷
÷
ø

æ
ç
ç
ç
ç
ç
ç
ç
ç
è

X-2

é
ê
ê
ê
ë

X-

m₂ⁿ

ù
ú
ú
ú
û

ö
÷
÷
÷
÷
÷
÷
÷
÷
ø

m₁ⁿ⁺¹=m₁ⁿ+

é
ê
ê
ê
ê
ê
ê
ê
ë

X-

2m₁ⁿ

ù
ú
ú
ú
ú
ú
ú
ú
û

m₂ⁿ⁺¹=m₂ⁿ+

é
ê
ê
ê
ê
ê
ê
ê
ë

X-

2m₂ⁿ

ù
ú
ú
ú
ú
ú
ú
ú
û

d'où

m₁ⁿ⁺¹=m₁ⁿ+

é
ê
ê
ê
ë

XY-2m₁ⁿ

ù
ú
ú
ú
û

m₂ⁿ⁺¹=m₂ⁿ+

é
ê
ê
ê
ë

XY-2m₂ⁿ

ù
ú
ú
ú
û

soit

m₁ⁿ⁺¹=m₁ⁿ+

é
ê
ê
ê
ë

m₂-m₁ⁿ

ù
ú
ú
ú
û

m₂ⁿ⁺¹=m₂ⁿ+

é
ê
ê
ê
ë

m₁-m₂ⁿ

ù
ú
ú
ú
û

Etude de Uⁿ

A partir des expressions précédentes on déduit :

Uⁿ⁺¹

Uⁿ-

Uⁿ

Þ Uⁿ⁺¹

æ
ç
ç
ç
è

2 a

ö
÷
÷
÷
ø

Uⁿ=b Uⁿ

Þ Uⁿ

bⁿU⁰

On obtient ainsi une série géométrique dont la convergence est assurée pour b < 1 (Þ

<a <¥).

Dans le cas général où r(x,y) est quelconque, on induit des déplacements :

D_n= a _n(G_n - G_M).

pour lesquels la valeur du coefficient a _n dépend du problème et sera ajustée lors des expérimentations (en règle générale on prend 0 < a <

).

Si on augmente le nombre de secteurs, on applique ce principe à chaque paire de secteurs possibles puis on effectue la somme vectorielle des écarts ainsi obtenus en s'assurant que les centres de classe restent dans le domaine géographique (si tel n'est pas le cas on fait des troncatures).

Par rapport à notre problème, ce processus d'équilibrage ne peut être mené à terme pour deux raisons essentielles ;

la répartition surfacique de masse est homogène et non continue en certains points faussant ainsi les calculs de déplacement ;
quand bien même il serait exact, ce processus ne permet pas de satisfaire le critère de minimisation des coordinations.

La difficulté consiste alors à déterminer le nombre d'itérations d'équilibrage. Après expérimentation, et pour deux à cinq itérations, on s'aperçoit que l'algorithme se confine dans des zones d'espace d'état desquelles il ne peut sortir facilement par mutation car le processus d'équilibrage l'y ramène systématiquement. A l'inverse, si l'on ne fait aucun équilibrage l'algorithme est plus lent à converger. D'après les évaluations, il semble qu'un seul équilibrage soit nécessaire. Ainsi après chaque calcul des charges de secteur, on effectue une itération d'équilibrage qui modifie le chromosome avant d'évaluer le critère.

4.5.4 Évaluation

Pour évaluer et comparer les différentes versions d'algorithmes, on utilise un réseau de test pour lequel une solution évidente est connue (voir figure 4.10).

Figure 4.10: Réseau test et sectorisation construite par l'AG

Sans nuire au principe général d'évaluation, on fait l'hypothèse que les flux sur les arcs de ce réseau sont constants. Les paramètres utilisés pour l'AG furent les suivants : 400 éléments de population, 200 générations, 60% de probabilité de croisement , 6% de probabilité de mutation.

Pour observer la convergence de l'algorithme, la meilleure fitness ainsi que la moyenne des fitness sur l'ensemble de la population, sont mémorisées à chaque génération. Dans le cas présent, l'algorithme travaille sur une fitness normalisée qui est bornée à ``1'' lorsque les critères d'équilibrage et de coordination s'annulent simultanément. L'évolution de ces deux paramètres en fonction de la génération est donnée sur la figure 4.11 (sans recuit simulé (FGA)) et sur la figure 4.11 (avec recuit simulé dans le croisement (EGA)).

Figure 4.11: Convergence de l'AG sans et avec RS sur le réseau symétrique

Les deux algorithmes trouvent une solution exacte très rapidement (15 générations pour FGA et 8 générations pour EGA). Un exemple de solution fourni par l'algorithme est donné en figure 4.10.

Le temps de résolution pour ce type de problème est de cinq minutes sur station ``Sparc 10'' (pour les deux cents générations).

Après ce premier réseau, nous avons testé l'algorithme sur un réseau quelconque pour lequel il n'y a pas de solution évidente (voir figure 4.12).

Figure 4.12: Réseau asymétrique et sectorisation construite par l'AG

On se propose de partitionner ce réseau en cinq secteurs. Comme on le constate sur les courbes de convergence, l'algorithme a un très bon comportement et fournit une solution quasi-exacte en moins de 10 générations (voir figure 4.13 et figure 4.13 pour cette solution le secteur le moins équilibré est à 0.7 pour cent de l'équilibre exact)

Figure 4.13: Convergence de l'AG sans et avec RS sur le réseau asymétrique

A l'inverse du cas précédent, ici la fitness ne peut atteindre 1 car il est impossible d'annuler la coordination. La sectorisation physique générée par l'algorithme est donnée en figure 4.12 et le temps de résolution associé est de trois minutes. Comme on peut le constater, cette sectorisation respecte les contraintes et présente un aspect tout à fait satisfaisant.

4.5.5 Conclusion

Cette première étude a apporté des résultats encourageants concernant l'utilisation des algorithmes génétiques dans le problème de sectorisation des réseaux de transport. Le codage du chromosome a une grande importance dans l'efficacité de l'algorithme car il permet la synthèse de sectorisation avec un grande simplicité d'implantation. Cette simplicité se retrouve dans les opérateurs de croisement et de mutation en favorisant les performances de l'algorithme. L'utilisation du recuit simulé dans l'opérateur de croisement améliore la convergence au niveau de la statistique des moyennes.

Dans la description précédente, la valeur de K (nombre de secteurs) était fixe mais il serait envisageable de la coder directement dans le chromosome pour que l'algorithme génétique ajuste sa valeur de façon adaptative. Il faudrait alors modifier le critère pour pénaliser fortement les individus dans lesquels il y a des secteurs qui ont une charge supérieure à la charge maximum que peut gérer un contrôleur.

4.6 Affectation des flux sur un réseau sectorisé

Le problème à résoudre est un problème d'affectation statique dans un réseau à coûts d'arcs non séparables asymétriques ⁵ . Nous allons tout d'abord présenter les méthodes classiques et leurs limitations, puis décrire un principe d'affectation de trafic respectant la contrainte d'équité, basé sur les algorithmes génétiques.

4.6.1 Méthodes classiques d'affectation statique

Algorithme d'affectation de Dijsktra

Initialement cet algorithme a été développé pour simuler le premier principe de Wardrop et converge donc vers un équilibre utilisateur. Nous avons vu précédemment qu'il y a équivalence entre équilibre utilisateur et équilibre système lorsque l'on remplace les coûts réels par les coûts marginaux associés, à condition de vérifier la condition de séparabilité. Notre objectif étant d'obtenir un équilibre système, on se propose d'utiliser un algorithme de Dijsktra sur un réseau pondéré par les coûts marginaux. Le principe de cet algorithme est assez intuitif et consiste à rechercher, pour chaque paire OD, le chemin le plus court sur lequel on affecte un quantum de trafic en réactualisant les coûts d'arcs associés.

Dans le cadre des réseaux à coûts d'arcs non séparables, on peut continuer à utiliser cet algorithme sur les coût marginaux (en vue de déterminer un coût système) à condition que la non séparabilité soit localisée aux noeuds. De fait, on peut remplacer les coût réels par les coûts marginaux pour obtenir l'équilibre système à l'aide d'un algorithme de Dijsktra. Si les coûts sont non séparables mais si l'interaction n'a lieu qu'au niveau des noeuds, l'algorithme de Dijsktra continue également à fonctionner. Dans le cas d'un réseau quelconque, pour lequel la dépendance inter-arcs n'a pas de particularité, les termes dérivés ne s'annulent plus et il faut alors utiliser des algorithmes plus élaborés. C'est le cas du problème qui nous intéresse ici.

Algorithme de Dafermos

Initialement cet algorithme [Daf72] a été développé pour des applications routières afin de tenir compte des interactions des flux croisés lors des dépassements. Ce modèle mathématique s'applique essentiellement à des réseaux à coûts d'arcs non séparables asymétriques pour lesquels l'hypothèse suivante est vérifiée : la fonction coût que l'on cherche à minimiser (coût total) doit être strictement convexe par rapport à f. On suppose de plus qu'il y a une répartition de trafic sur le réseau qui satisfait les lois de Kirchoff. Cette répartition pourrait être, par exemple, le résultat d'un algorithme d'affectation de Dijsktra produisant un équilibre utilisateur.

A partir de la distribution de trafic initiale, l'algorithme recherche pour chaque paire Origine-Destination, le chemin utilisé de coût marginal maximum et le chemin de coût marginal minimum (utilisé ou non). Soient ch_max et ch_min ces deux chemins. On retire ensuite une quantité du flux transitant sur ch_max et on le place sur ch_min afin de minimiser le critère global. On reproduit ce processus sur toutes les OD en itérant par permutation circulaire, jusqu'à ce que l'on ne puisse plus diminuer le critère global. On montre alors que l'on a atteint l'équilibre système.

Dans notre cas, l'algorithme de Dafermos ne peut être utilisé car il ne prend pas en compte la contrainte d'équité susmentionné.

4.6.2 Optimisation du problème par AG

Aucun des algorithmes classiques ne donnant de résultats, il a été nécessaire de recourir à des techniques d'optimisation stochastique. Les algorithmes génétiques ont été préférés au recuit simulé, car ils permettent de fournir plusieurs solutions de coût proche. Or, nous souhaitons avant tout proposer à des experts humains différentes solutions parmi lesquelles ils pourront choisir celle qui leur paraît la plus adapté. L'AG est donc plus adapté que le recuit simulé.

Codage du chromosome

Le codage du chromosome est une des phases les plus importantes car elle conditionne en grande partie la réussite du processus de résolution. Le chromosome doit contenir l'information nécessaire pour évaluer la fitness associée en modélisant un point de l'espace d'état. Dans le cas présent, chacun des points de l'espace d'état est représenté par un tableau dont chaque colonne décrit le chemin de la paire Origine-Destination associée (voir figure 4.14). Comme on peut le constater, l'espace de recherche est discret.

Figure 4.14: Structure d'un point de l'espace d'état

L'appartenance des noeuds à un chemin implique que ces derniers soient connexes, ce qui interdit certaines combinaisons qui violent cette contrainte. De plus, pour des questions d'économie, on ne code dans le chromosome que les noeuds qui appartiennent à un chemin sans tenir compte des autres noeuds du réseau. Ce codage rend la dimension du chromosome variable en fonction des longueurs des chemins qu'il code comme on peut le constater sur l'exemple de codage donné en figure 4.15. Dans cet exemple les avions reliant l'aéroport 1 à l'aéroport 16 sont routés sur le chemin {1,4,3,7,12,16}. Inversement les avions faisant le trajet inverse sont routés sur le chemin {16,11,6,3,4,1} etc.

Figure 4.15: Codage du chromosome

Principe de génération de la population initiale

Pour utiliser correctement les algorithmes génétiques, il nous faut disposer d'une population initiale d'individus regroupant un ensemble de chemins initialisés aléatoirement. Pour chaque individu, on considère le graphe initial dont les coûts d'arcs sont initialisés à l'aide de la distance géographique associée que l'on bruite ensuite à l'aide d'une distribution gaussienne en veillant à ce que les coûts restent positifs. Pour chacune des paires Origine-destination contenues dans le chromosome, on recherche le chemin le plus court à l'aide d'un algorithme de Dijkstra (complexité O(N²) où N est le nombre de noeuds du réseau).

Suivant la déviation de la distribution gaussienne, les chemins générés seront plus ou moins différents du chemin géographique le plus court dans le réseau non bruité. Ce principe d'initialisation évite la génération purement aléatoire des chemins dans le réseau qui conduirait à des aberrations en terme de navigation (par exemple, un chemin qui passerait par Moscou pour une paire Origine-Destination reliant Madrid à Londres). Ce type d'événement doit rester rare mais ne doit pas être complètement inhibé car il permet d'enrichir la diversité des gènes. En effet, après croisement un mauvais chemin peut produire des solutions tout à fait acceptables. Ayant maintenant une population non homogène, il nous faut définir les opérateurs de croisement et de mutation associés qui vont permettre la génération de nouveaux éléments au sein de la population.

Opérateur de croisement

Notre espace de recherche étant discret, on ne peut envisager d'utiliser un croisement barycentrique et seul le croisement à segmentation de chromosome a été utilisé (Slicing Crossover). Pour effectuer un croisement, on tire aléatoirement une position dans le chromosome puis on échange les deux ensembles de chemins terminaux (voir figure 4.16).

Figure 4.16: Opérateur de croisement et de mutation

Opérateur de mutation

L'opérateur de mutation nous permet d'enrichir la diversité de la population en créant de nouveaux chemins. En effet, l'opérateur de croisement décrit précédemment génère des nouveaux chromosomes mais ne modifie pas la population de chemins générés aléatoirement lors de l'initialisation du processus. Pour créer de nouveaux chemins, l'opérateur de mutation tire aléatoirement une paire Origine-Destination dans le chromosome et applique le même principe de génération aléatoire de chemin que celui utilisé lors de la création de la population initiale mais ici avec un écart-type plus fort. Un exemple d'opérateur de mutation est donné dans figure 4.16.

Introduction de la distance inter-chromosomes pour le sharing

Pour effectuer un sharing, on doit disposer d'une distance inter-chromosomes afin d'évaluer le taux d'agrégation des individus dans l'espace d'état. Si l'on considère la description stricte du chromosome, on ne peut pas définir une distance réaliste entre individus car on ne dispose pas d'une structure d'espace vectoriel. En effet, chaque chemin étant codé par la liste des indices des noeuds qui le composent, il est très difficile de déterminer une notion de distance représentative de la différence physique induite dans l'espace géographique sous-jacent. Pour déterminer cette distance entre chemins, on se place directement dans cet espace géographique en considérant non plus les indices des noeuds mais leurs coordonnées. On définit alors la distance entre deux chemins par la surface fermée qu'ils entourent (voir figure 4.17).

Figure 4.17: Surface délimitée par deux chemins

Cette surface est alors calculée en faisant la somme des surfaces des triangles construits à l'aide des noeuds de chacun des chemins comme le montre la figure 4.17. L'expression analytique de cette surface est donnée par la formule suivante:

S=A(P₁,P₂,Q₂) +

m-1

i=2

{A(P_i,Q_i,Q_i+1) + A(P_i,P_i+1,Q_i+1) }+

n-2

i=m

{A(P_m,Q_i,Q_i+1) };

avec

Ch₁={P₁,P₂,...,P_m}; Ch₂={Q₁,Q₂,...,Q_n} m<n et n ³ 3;

Que se passe-t-il lorsque les chemins se croisent ? Dans le cas général, cette pseudo-distance majore l'aire comprise entre les deux chemins ; dans le cas particulier de notre réseau de transport planaire dans lequel les croisements de routes se font au niveau des noeuds, la pseudo-distance est toujours égale à l'aire comprise entre les deux chemins.

Disposant d'une distance entre deux chemins, on calcule la distance entre deux chromosomes en faisant la somme des distances respectives associées à chacune des paires de chemins contenues dans chaque chromosome.

Calcul du barycentre entre deux chromosomes

Comme pour le calcul de la distance inter-chromosomes, il nous faut travailler dans l'espace géographique sous-jacent au réseau de transport pour calculer le barycentre entre deux chemins. Soient deux chemins :

Ch₁={P₁,P₂,...,P_m}; Ch₂={Q₁,Q₂,...,Q_n} n ³ 3; m < n

Soient n₁ et n₂ les coefficients barycentriques associés respectivement aux chemins Ch₁ et Ch₂. Le chemin barycentrique est alors donné par :

Ch_B=( P₁,

n₁ P₂+n₂ Q₂

n₁+n₂

n₁ P₃+n₂ Q₃

n₁+n₂

,...,

n₁ P_m-1+n₂ Q_m-1

n₁+n₂

n₁ P_m-1+n₂ Q_m

n₁+n₂

,...,

n₁ P_m-1+n₂ Q_n-1

n₁+n₂

, Q_n);

Dans cette expression P représente la position géographique du noeud P.

Un exemple de chemin barycentrique est donné sur la figure 4.18 avec n₁=2 et n₂=1.

Figure 4.18: Exemple de chemin barycentrique

Pour déterminer le barycentre entre deux chromosomes, il suffit d'appliquer ce processus de calcul à chacun des chemins contenus dans le chromosome.

Calcul et normalisation de la fitness

Dans un premier temps, on considère le réseau de transport sans trafic. Pour chaque paire Origine-Destination contenue dans le chromosome, on affecte la demande correspondante sur le chemin décrit par la liste des noeuds associée. On dispose alors de la répartition de flux sur chacun des arcs du réseau, ce qui nous permet de calculer le sous-critère d'affectation C₁ ainsi que la charge de contrôle globale (et donc le critère C).

Le nombre d'opérations nécessaires à l'évaluation d'une fitness dépend de la taille du réseau et varie en O(N_od+L+K(N+L)) (N_od : nombre de paires Origine-Destination, L : nombre d'arcs du réseau, K : nombre de secteurs, N : nombre de noeuds).

Évaluation

Pour évaluer notre algorithme, on utilise un réseau test pour lequel on connaît une solution triviale d'affectation (voir figure 4.19).

Figure 4.19: Réseau test et affectation résultante

Sur ce réseau, les noeuds sur la première diagonale représentent les aéroports et ceux de la deuxième diagonale sont les balises. On se propose d'affecter une demande de trafic constante entre chaque paire d'aéroports de façon symétrique (chaque aéroport génère une demande à destination de l'aéroport symétrique, ce dernier lui envoyant la même quantité de trafic).

Pour cet exemple, on règle le coefficient de congestion de telle sorte que deux flots de trafic ne peuvent emprunter le même arc ; on interdit de même que deux flots se retrouvent face à face sur un arc. Le critère se présente alors sous la forme suivante :

C=a

(i,j) Î L

C_ij(f_ij) + (1-a)

(i,j) Î L

g f_ijf_ji

Comme on peut le constater, il n'y a pas de sectorisation mais la forme du critère est similaire à celle décrite précédemment et ne change en rien la généralité de l'algorithme.

Les paramètres utilisés furent les suivants : 400 éléments de population, 300 générations, 60% de probabilité de croisement , 6% de probabilité de mutation.

Pour ce test nous avons utilisé un algorithme génétique avec du recuit simulé dans l'opérateur de croisement afin d'améliorer les performances de convergence. L'évolution de la fitness (normalisée entre 0 et 1) du meilleur individu ainsi que la moyenne des fitness sur l'ensemble de la population, en fonction de la génération, sont données sur la figure 4.20.

Figure 4.20: Évolution de la fitness normalisée

Comme on peut le constater, une solution optimale est trouvée à partir de la génération 180 pour laquelle intervient seulement la partie du critère liée à la distance de parcours. Cette solution est obtenue en six minutes sur une station ``Sparc 10''. L'affectation physique correspondant à cette solution est donnée sur la figure 4.19.

Au cours de ces évaluations, on s'aperçoit que les performances de cet algorithme sont très sensibles à l'amplitude de l'écart-type de la distribution utilisée pour bruiter les coûts d'arcs dans le processus de génération des chemins aléatoires. Pour chaque problème, il faut régler ce paramètre afin d'obtenir des chemins aléatoires différents du chemin optimal (en terme de distance) mais qui à l'inverse ne soient pas trop pénalisants par rapport au rallongement induit. Une solution consisterait à coder ce paramètre dans le chromosome et à le faire ajuster par l'algorithme génétique de façon adaptative.

4.6.3 Conclusion

La contrainte d'équité nous empêche d'utiliser les méthodes classiques d'affectation de trafic sur les réseaux à coûts d'arcs non séparables et induit une forte complexité nous obligeant à nous orienter vers des méthodes d'optimisation stochastique. Après avoir développé un codage du chromosome ainsi que des opérateurs adaptés, on s'aperçoit que les algorithmes génétiques traitent ce problème de façon efficace à condition que le générateur de chemins aléatoires soit adapté au réseau de transport utilisé.

La contrainte d'équité, qui permet de conserver la libre concurrence des compagnies aériennes, a pour inconvénient de réduire notre espace de recherche et nous interdit donc d'accéder à des zones d'espace où le critère serait assurément meilleur. En effet, on montre que lorsque le critère à optimiser n'est pas linéaire par rapport aux flux sur les chemins, mais plutôt quadratique, il est plus avantageux de segmenter les flux afin de rendre le système plus capacitif.

4.7 Sectorisation et affectation de trafic simultanées

La dépendance très forte des problèmes d'affectation et de sectorisation incite à penser que ces deux problèmes doivent être résolus simultanément. Dans le cas de la sectorisation, l'optimisation visait essentiellement à réduire les coordinations et à équilibrer les charges de contrôle. De même, l'optimisation de l'affectation avait pour but la minimisation de la charge globale de contrôle tout en minimisant les rallongements de route induits.

La diversité des critères liés à ces deux problèmes, quand bien même certains sont communs, révèle la nature multi-objectifs du problème global. Dans un premier temps, une approche itérative avec deux algorithmes génétiques bouclés s'est révélée inefficace de par l'instabilité des solutions fournies. Cet échec a amené Daniel Delahaye à proposer de traiter le problème dans sa globalité à l'aide d'un algorithme génétique unique en codant les deux sous-problèmes dans un diploïde ⁶ . Cette approche n'a pas encore été testée.

4.8 Regroupement de secteurs

4.8.1 Introduction

Au cours d'une journée de trafic ordinaire, on remarque que la charge de contrôle fluctue dans le temps en fonction des demandes de trafic entre les diverses paires Origine-Destination. Par exemple, en France, il y a une pointe de trafic le matin et une pointe le soir.

Les algorithmes présentés jusqu'à présent ont toujours travaillé avec des flux importants sur le réseau afin d'assurer l'absorption des pointes de trafic, ce qui correspond au cas le plus défavorable. Ainsi nos problèmes sont optimisés pour ce genre de trafic et les solutions apportées deviennent sous-optimales lorsque les flux sur le réseau diminuent.

Dans le système opérationnel actuel, le nombre de contrôleurs varie en fonction des demandes de trafic. Ainsi, la nuit, le nombre d'équipes de contrôle est réduit car il y a beaucoup moins de trafic. Si tel n'était pas le cas, on se retrouverait avec des positions de contrôle traversées par une dizaine d'avions par heure ; ce qui générerait un coût de contrôle surdimensionné par rapport au service rendu aux usagers. Les secteurs sont donc regroupés la nuit en groupe de trois à quatre ; chaque groupe ainsi constitué est ensuite attribué à une équipes de contrôleurs. Actuellement ce regroupement est fait de façon empirique au niveau de chaque centre de contrôle régional par des experts gérant l'espace aérien, qui groupent et dégroupent les secteurs par anticipation des fluctuations de trafic. Ainsi, le matin, les secteurs sont dégroupés un peu avant la pointe de trafic liée à l'ouverture des aéroports.

Dans ce chapitre, nous décrivons une méthode automatique de regroupement ⁷ de secteurs fournissant une solution globale sur l'ensemble de l'espace aérien.

4.8.2 Modélisation

Nous faisons l'hypothèse que les secteurs initiaux sont convexes au sens géométrique du terme et pourraient être le résultat de l'algorithme de sectorisation décrit dans les chapitres précédents. Ceci ne change en rien les propriétés de l'algorithme de regroupement proposé dans ce chapitre et ce dernier pourrait très bien s'appliquer à la sectorisation actuelle qui est constituée par des secteurs convexes au sens des routes aériennes. Les propriétés d'un bon regroupement sont en fait les mêmes que celles demandées à la sectorisation : on cherche à synthétiser des groupes de secteurs dont les charges de contrôle résultantes sont équilibrées et qui minimisent les coordinations restantes (coordination inter-groupes). Un exemple de regroupement de secteurs de contrôle est fourni sur la figure 4.21.

Figure 4.21: Exemple de regroupement pour N=4 et K=2

Comme on peut le constater, le regroupement {(S₁,S₂,S₃);(S₄,S₅,S₆)} fait disparaître les charges de coordination liées aux anciennes frontières de secteur : (S₁,S₂);(S₂,S₃);(S₄,S₅);(S₅,S₆).

D'autre part, tous les secteurs appartenant à un même groupe doivent être connexes. Cette contrainte évite par exemple qu'un même contrôleur gère une portion de trafic à Lille et une autre à Marseille ; ce qui est une aberration en terme de contrôle du trafic aérien dans la mesure où l'on perd l'homogénéité du trafic dans les secteurs gérés par une même équipe de contrôleurs et produit de plus des coordinations inutiles.

Comme on peut le remarquer, ce problème est très proche du problème de sectorisation. La différence essentielle réside dans la description de l'espace de recherche associé. En effet, dans le problème de sectorisation l'espace était continu et les frontières des secteurs générés pouvaient se trouver à n'importe quel endroit dans l'espace géographique. A l'inverse, l'espace de recherche lié au problème de regroupement est un espace discret pour lequel les frontières des groupes constitués doivent coïncider avec les frontières des secteurs existants (chaque groupe associe un ensemble de secteurs sans en créer de nouveaux). Notre problème de regroupement s'apparente donc à un problème de classification.

4.8.3 Complexité du principe de regroupement

Dans un premier temps nous examinons le nombre de points constituant notre espace de recherche en négligeant la contrainte de connexité. Il s'agit donc de savoir quel est le nombre de façon possible de construire K sous-ensembles d'un ensemble de N éléments où N représente le nombre total de secteurs et K le nombre de groupes constitués. Le nombre de cas possibles est donné par le second nombre de Stirling,soit pour N=600 et K=200 (groupement moyen de trois secteurs) :

S₆₀₀²⁰⁰ = 0.8 10¹⁰⁰¹

Si l'on tient compte maintenant de la contrainte de connexité l'espace de recherche se réduit. Pour étudier la complexité induite, le problème est modélisé de la façon suivante. On construit un graphe dans un espace euclidien dont chaque noeud représente le barycentre de chacun des secteurs constituant la sectorisation initiale et dont chaque arc traduit la relation ont une frontière commune.

Il s'agit alors de la recherche d'un K-partitionnement optimal d'un graphe à N noeuds en composantes connexes, problème connu pour être NP_complet. Le problème traité étant de forte dimension (N=600,K=200), seules les techniques d'optimisation stochastique ont été envisagées pour le résoudre.

4.8.4 Optimisation par algorithme génétique

La ressemblance des problèmes de sectorisation et de regroupement conduit à des similitudes dans l'utilisation des algorithmes génétiques pour les résoudre. En effet, le problème de regroupement étant une version discrète du problème de sectorisation, il est tout à fait logique d'utiliser un codage et des opérateurs similaires.

Ainsi, disposant d'une sectorisation initiale, on calcule pour chaque secteur le barycentre géométrique associé auquel on affecte la charge de contrôle qu'il renferme. Pour générer aléatoirement N groupes de secteurs, on jette N points (centres de groupe) dans l'espace géographique, dont les coordonnées suivent une loi de distribution uniforme, puis on agrège chaque barycentre à son centre de groupe le plus proche. On synthétise ainsi des groupes qui respectent toujours la contrainte de connexité car le polygone construit à l'aide des barycentres des secteurs contenus dans un groupe est convexe, les secteurs associés sont donc obligatoirement connexes. On retrouve alors un codage du chromosome identique à celui utilisé pour le problème de sectorisation dans lequel sont regroupés ici les coordonnées des centres de groupe.

Ayant un codage identique à celui utilisé dans la résolution du problème de sectorisation on utilise les mêmes opérateurs de croisement et de mutation. Le calcul des distances inter-chromosomes et du barycentre entre deux individus est effectué de la même façon.

A l'initialisation du processus, on calcule la charge de contrôle de chacun des secteurs de la sectorisation initiale. Pour chaque individu, on détermine la charge de monitoring et de conflit dans chacun des groupes qu'il renferme en faisant la somme des charges de contrôle contenues dans les divers secteurs ainsi que la charge résiduelle de coordination. Ces quantités nous permettent ensuite de calculer les sous-critères d'équilibrage et de coordination et donc la fitness associée à un regroupement.

De la même manière que pour les problèmes de sectorisation, on valide les performances de l'algorithme à l'aide d'un réseau artificiel pour lequel on connaît une solution évidente. Dans le cas présent, on reprend le réseau test utilisé dans le problème de sectorisation (voir figure 4.22) que l'on découpe initialement en 81 secteurs (voir figure 4.22) et pour lequel on recherche neuf groupes équilibrés qui minimisent les coordinations. La solution évidente de ce problème est constituée des neuf sous-réseaux regroupant chacun neuf secteurs.

Figure 4.22: Réseau test utilisé et son découpage

Une solution optimale est trouvée à la génération 50 (après une minute de temps de calcul sur ``Sparc 10'').

Figure 4.23: Solution et regroupement résultant

Le résultat obtenu peut surprendre au premier abord (figure 4.23), mais il faut se rappeler que l'algorithme travaille avec les barycentres des secteurs et non avec les secteurs eux-mêmes. En revenant à la définition initiale des secteurs, on obtient le regroupement décrit sur la figure 4.23 qui correspond bien au résultat attendu.

Les résultats fournis par ces évaluations, nous incitent à penser que les algorithmes génétiques sont bien adaptés pour résoudre le problème de regroupement. Malgré la restriction de l'espace d'état liée au codage du chromosome, les solutions apportées par l'algorithme sont de très bonne qualité dans la plupart des cas.

4.9 Limitations du modèle

4.9.1 Modélisation de la charge de contrôle

Les paramètres liés à la description de cette charge ont été choisis empiriquement et pourraient être affinés à l'aide d'expérimentations. Cette modélisation est très délicate car beaucoup de facteurs entrent en jeu dans la résultante de la charge de contrôle. EUROCONTROL (Brétigny projet RAMS) a développé un modèle assez réaliste de cette charge mais au prix d'une complexité élevée. En effet, ce dernier intègre 200 tâches élémentaires de contrôle dans le cadre des simulations arithmétiques qu'on ne peut utiliser dans nos algorithmes génétiques pour des questions de temps de calcul.

Une autre approche consisterait à faire de l'apprentissage sur les paramètres utilisés dans la description simplifiée de la charge de contrôle que l'on a développée. Dans un premier temps, l'algorithme génétique utiliserait des paramètres grossiers, et fournirait tout de même une sectorisation. Ce résultat serait ensuite présenté à des experts qui corrigeraient ce dernier en modifiant les frontières des secteurs à l'aide d'une interface graphique. On calculerait alors un écart (D) entre les deux sectorisations qui servirait de base à la redéfinition des coefficients du modèle. On itèrerait ce procédé jusqu'à ce que les experts soient satisfaits du résultat produit par l'algorithme. Si l'on ne peut atteindre cet objectif, il faudrait revoir le modèle lui-même et non le réglage de ses coefficients. Pour que cette méthode fonctionne correctement il faut que les objectifs de sectorisation utilisés par les algorithmes génétiques soient les mêmes que ceux des experts, ce qui n'est pas toujours le cas.

Enfin, il serait possible de faire un ajustement statistique des paramètres utilisés dans notre modèle de charge de contrôle à l'aide de la connaissance précise de la charge de travail dans un secteur (connaissance issue d'un modèle intégrant un grand nombre de tâches de contrôle (simulation RAMS par exemple) que l'on ne peut utiliser dans nos algorithmes à cause de la complexité associée).

4.9.2 Prise en compte de la troisième dimension

Jusqu'à présent, seul le trafic en route a été pris en compte pour synthétiser la charge de contrôle. Cette hypothèse sur la nature du trafic nous a permis de modéliser le réseau de transport aérien à l'aide d'un graphe dans un espace de dimension deux.

Malheureusement, ce type de représentation n'est pas adapté pour le trafic évolutif pour lequel les avions changent très souvent de niveau de vol. Il faut alors utiliser un réseau de transport à trois dimensions dans lequel les arcs représentent des ``routes aériennes 3D''.

On pourrait essayer de se rapprocher du principe actuel de sectorisation 3D qui utilise des secteurs de forme polygonale à frontières verticales planaires (voir figure 4.24). Ces secteurs ont de plus des extensions verticales différentes qui produit une structure imbriquée dont un exemple est donné sur la figure 4.24.

Figure 4.24: Structure des secteurs actuels

Cependant cette structure de sectorisation demande de modifier en profondeur la représentation du chromosome et donc l'algorithme génétique dans son ensemble.

4.9.3 Limitation de l'exploration de l'espace d'état

La synthèse des secteurs de contrôle à l'aide des centres de classe (voir chapitre traitant de la sectorisation) est très intéressante pour la description du chromosome utilisé par les algorithmes génétiques car très peu d'informations sont nécessaires pour construire une sectorisation complète qui de plus, satisfait la propriété de convexité géométrique. On rappelle que seules les positions géographiques des centres de classe sont codées dans le chromosome. En examinant la sectorisation actuelle, on constate que les secteurs ont des formes polygonales mais pas nécessairement convexes d'un point de vue géométrique. Ce type de représentation est plus riche en terme d'exploration spatiale et permet d'accéder à de nouveaux points de l'espace d'état, que la propriété de convexité nous interdit d'adresser. Ainsi, sur l'exemple de la figure 4.25, une sectorisation convexe ne peut pas équilibrer les charges de contrôle alors qu'en supprimant la convexité géométrique il est possible d'atteindre cet objectif.

Figure 4.25: Exemple de limitation liée à la convexité géométrique

De la même façon que pour la limitation des algorithmes génétiques par rapport à l'extension tridimensionnelle, le codage de chromosomes permettant de synthétiser des sectorisations polygonales non convexes s'avère assez compliqué. Daniel Delahaye propose diverses solutions pour remédier à ce problème [Del95].

4.9.4 Prise en compte des zones militaires

Une partie de l'espace aérien est réservé aux autorités militaires. L'activation de ces zones, qui est faite à l'initiative des instances de la défense, provoque des perturbations plus ou moins importantes dans le trafic aérien civil suivant la configuration du moment. De plus, les secteurs qui contiennent ces zones voient leur espace se réduire brutalement limitant ainsi les possibilités d'action des contrôleurs. Cette restriction d'espace provoque une augmentation de la charge de contrôle induite pour la même quantité de trafic.

Nous n'avons pas pris en compte ce type d'événement dans nos algorithmes car leur modélisation est très délicate. Un moyen détourné d'intégrer ces zones dans le processus de résolution consisterait à augmenter artificiellement la charge de contrôle des secteurs qui les contiennent.

4.9.5 Problèmes politiques liés à la souveraineté de l'espace aérien

En observant la sectorisation actuelle, on constate que les limites des secteurs épousent les frontières géographiques des pays qui les contiennent. Ceci se justifie dans la mesure où le contrôle du trafic aérien est généralement confié aux pays survolés par les aéronefs. Il est clair que cette restriction réduit les performances de la sectorisation actuelle car elle provoque des coordinations superflues.

4.9.6 Prise en compte de la propagation des flux

Le fait d'utiliser des flux statiques sur le réseau produit une charge de contrôle invariante dans le temps, que l'on a majorée en considérant le flux maximum enregistré sur une journée sur chacun des arcs du réseau. Or, on sait très bien que ces valeurs extrêmes ne sont jamais présentes simultanément, car les heures de pointe de trafic sont locales aux fuseaux dans lesquels se trouvent les aéroports. Ainsi, les pointes sont décalées dans le temps. De plus, lorsqu'il y a une augmentation de la demande de trafic sur une paire Origine-Destination donnée, elle va induire un accroissement du flux sur la route associée avec un délai de propagation lié à la vitesse des aéronefs. Les algorithmes (de sectorisation et surtout d'affectation) devraient tenir compte de cette propagation pour déterminer la charge réellement présente sur le réseau de transport.

4.10 Conclusion

En examinant le contexte opérationnel, on remarque que ces algorithmes ont besoin d'adaptation pour envisager leur utilisation sur le réseau aérien réel. La principale amélioration se situe au niveau de la description de la charge de contrôle. Le problème à résoudre est complexe et il n'existe pas aujourd'hui de modèle fiable facile à implanter.

La seconde limitation se trouve au niveau du codage du chromosome de sectorisation qui, dans son état actuel, synthétise des secteurs convexes au sens géométrique du terme. Ce type de convexité masque des domaines de l'espace d'état où se trouve parfois l'optimum global.

Enfin, la prise en compte de la troisième dimension permettrait de traiter le trafic évolutif dans les zones terminales, mais il faut pour cela synthétiser des secteurs à frontières latérales verticales, ce qui complique sensiblement la description du chromosome. En amont de la sectorisation, il est clair que le réseau de routes aériennes actuel nécessite lui-même une optimisation qui permettrait ensuite de développer une sectorisation plus performante. En effet, ce réseau a été ``construit'' en regroupant un ensemble de sous-réseaux (propres à chaque pays européen), optimisés individuellement. Il est possible que l'augmentation de la capacité des secteurs ATC, passe d'abord par une redéfinition du réseau de routes : ces dernières ont été construites pour une demande de trafic donnée qui ne cesse aujourd'hui de se modifier tant en volume qu'en orientation.

1: Ce chapitre présente les résultats obtenus par Daniel Delahaye dans le cadre de sa thèse.
2: Ce travail a donné lieu à deux publication[DASF94a, DASF94c]
3: Il faut préciser que ce type de convexité (géométrique) restreint notre espace d'état en nous interdisant de générer des secteurs polygonaux non convexes.
4: Cet objectif est bien différent de celui proposé dans les méthodes de partitionnement (voir chapitre 3) pour lesquelles on recherche une minimisation de l'inertie intra-classe.
5: Ce travail a donné lieu à une publication[DASF94b]
6: Un ``diploïde'' est un chromosome à deux branches possédant des gènes bien distincts.
7: Ce travail a donné lieu à une publication[DASF95].