Un paradigme organis´e pour le trafic a´erien

Télécharger le fichier pdf d’un mémoire de fin d’études

Le travail des contrˆoleurs a´eriens

Diﬀ´erents types de contrˆoleurs a´eriens existent. Le plus connu de tous est celui qui travaille dans une tour de contrˆole. Son m´etier consiste a` diriger les avions qui arrivent sur les a´eroports et en repartent. Il existe aussi le contrˆole d’approche, dont le but est d’assurer les services de la circulation a´erienne aux abords des a´eroports, de fa¸con notamment `a optimiser l’utilisation des pistes d’atterrissage. Cependant les avions ne sont pas contrˆol´es uniquement aux alentours des a´eroports, mais sur quasiment tout l’espace. Pour cela, diﬀ´erents centres de contrˆoles s’occupent chacun d’une partie du territoire. La France, par exemple, est divis´ee en cinq centres (CRNA) : le CRNA Nord d’Athis-Mons, le CRNA Est de Reims, le CRNA Sud-Est d’Aix-En-Provence, le CRNA Sud-Ouest de Bordeaux et le CRNA Ouest de Brest. Pour chaque centre, des secteurs de contrˆole sont d´efinis, et attribu´es `a des ´equipes de contrˆoleurs. Chaque secteur est caract´eris´ par sa capacit´e, qui est le nombre maximal d’avions par unit´e de temps qu’il peut accueillir. Si les tours am`enent les avions vers les terrains d’atterrissage puis les font red´ecoller vers leur destination, les centres en route finissent de guider les appareils vers leur niveau de croisi`ere, commencent `a les faire descendre vers leur terrain de destination ou encore les surveillent lorsqu’ils sont sur les routes a´eriennes. Cette partie pourrait sembler plus simple que le contrˆole d’approche ou le contrˆole terminal mais la diﬃcult´e est tout aussi importante. En eﬀet, il faut g´erer des avions dont les vitesses peuvent ˆetre diﬀ´erentes, tout comme leurs performances en mont´ee et en descente. Il faut aussi faire face `a la proximit´e des a´eroports, ce qui implique que des flux de mont´ee peuvent interf´erer avec des flux de descente, ou bien mˆeme avec des avions en croisi`ere. Les avions sont aussi contrˆol´es au-dessus des eaux internationales, notamment l’oc´ean Atlantique, mais pas de la mˆeme fa¸con. Il n’existe pas de couverture radar, mais les avions suivent des tracks parall`eles sur lesquels ils sont s´equenc´es avec des s´eparations sup´erieures `a celles de l’espace en route, et reportent r´eguli`erement leur position par radio aux centres de contrˆoles en charge.

Limites du syst`eme

Lorsque le trafic augmente de mani`ere durable, la solution habituelle de r´egulation consistant `a retarder les vols au sol ne suﬃt plus. Il est alors n´ecessaire d’augmenter la capa-cit´e en divisant en deux certains secteurs et en recrutant des contrˆoleurs. Malheureusement, cette m´ethode par division ne peut se poursuivre ind´efiniment, car il existe une taille mini-male pour les secteurs en dessous de laquelle ceux-ci deviennent incontrˆolables, les avions restant trop peu de temps `a l’int´erieur. C’est notamment le cas dans la r´egion du Benelux, comme le montre la figure 1.1 qui permet de se faire une id´ee de la complexit´ du contrˆole a´erien. Le trafic a´erien europ´een a augment´ de 4,1% en 2006 [28] et de 5,3% en 2007 [29]. Mˆeme si l’augmentation a marqu´e le pas en 2008 (0,4%) et risque d’ˆetre l´eg`erement n´egative en 2009, les estimations actuelles pr´evoient que le nombre de mouvements d’avions soit multipli´e par 2 au cours des deux prochaines d´ecennies [30] ; il est donc clair que le syst`eme de circulation a´erien par contrˆole sectoris´ ne pourra pas ˆetre viable `a long terme.
Dans ce syst`eme de trafic a´erien, il ne faut bien sˆur pas oublier les retards, l’une des principales sources de m´econtentement des usagers. En 2008, plus de 20% des vols ont eu au moins 15 minutes de retard `a l’arriv´ee, pour un coˆut aux compagnies estim´ `a environ 1,5 milliard d’euros. Mˆeme si la cause essentielle de ces retards n’est plus aujourd’hui la gestion du trafic a´erien, grˆace `a de r´ecents eﬀorts ayant permis des gains de capacit´e, la croissance du trafic reposera in´evitablement le probl`eme dans les ann´ees `a venir.
Le r´eseau de routes actuel engendre ´egalement un rallongement de la distance parcourue par les avions. En eﬀet, ceux-ci ne peuvent pas suivre une orthodromie, c’est-`a-dire le plus court chemin entre deux points sur la sph`ere, entre leur origine et leur destination. La diﬀ´erence de distance globale parcourue a et´ de 5,6% en 2008, ce qui repr´esente environ 500 millions de kilom`etres additionnels, et environ 9 millions de tonnes de CO2 ´emises [30]. Cette distance suppl´ementaire a aussi et´ chiﬀr´ee en termes de coˆut pour les compagnies (en additionnant le coˆut du temps et celui du carburant) et a et´ estim´ee `a 2,7 milliards d’euros pour l’ann´ee 2008.

Evolution du syst`eme de trafic a´erien

Le programme SESAR (Single European Sky ATM Research) [1] [2] est un projet europ´een visant `a am´eliorer la gestion du trafic a´erien a` l’horizon 2020, en cr´eant un ciel europ´een unique. D’un point de vue technologique, ce projet pr´evoit l’int´egration des t´el´ecommunications et de la navigation par satellite, en se servant notamment de GALILEO [3]. A l’heure actuelle, les contrˆoleurs a´eriens donnent des instructions aux pilotes par une liaison radio VHF. L’un des principes d´evelopp´ dans SESAR est le rˆole central de la trajectoire (business trajectory ). Dans ce concept, la trajectoire 4D de vol optimale d’un appareil est d´efinie par les usagers et les prestataires de service de gestion du trafic a´erien (ANSP). Ceci mettrait fin au syst`eme de routes a´eriennes et permettrait de r´eduire la consommation et le temps de parcours des avions. Dans ses objectifs chiﬀr´es, SESAR pr´evoit de tripler la capacit´e du syst`eme europ´een de gestion du trafic a´erien, et de r´eduire de 10% par vol les incidences sur l’environnement. Pour satisfaire ces objectifs, SESAR propose une base de donn´ees appel´ee SWIM (System Wide Information Management), qui sera d´edi´ee `a la gestion du trafic a´erien. Cette base sera ouverte `a tous les acteurs jouant un rˆole dans cette gestion, aussi bien les compagnies a´eriennes que les ANSP. Cette base contiendra toutes les informations n´ecessaires sur les positions des appareils et leurs caract´eristiques et permettra de partager les informations sur la Business Trajectory ; seront notamment incluses en temps r´eel les masses des avions, les r´eserves en carburant et les heures pr´evues d’arriv´ees.
Le groupe ACARE (Advisory Council for Aeronautics Research in Europe), qui a lar-gement inspir´e le programme SESAR, propose de cr´eer des trajectoires 4D de la mani`ere suivante [8] : « The 4D trajectory is the basis of a contract between the aircraft operator and the ATM services. Changes to this trajectory are kept to the minimum. The 4D-trajectory is as conflict-free as possible, remaining conflicts being solved either automatically or ma-nually through ground operators’ intervention. » Les conclusions du rapport d’examen des performances 2005 [13] vont dans le mˆeme sens ; la commission sugg`ere « des changements plus radicaux de la structure de l’espace a´erien civil et militaire » afin de pouvoir « traiter les questions li´ees a` l’organisation et a` l’utilisation strat´egiques de l’espace a´erien. » Ce rapport pr´econise la mise en place, `a moyen ou `a long terme, d’un « plan-cadre visant a` restructurer l’espace a´erien europ´een, compte tenu des imp´eratifs a` la fois civils et mi-litaires. » La commission conclut que, « dans les cas compatibles avec les prescriptions de s´ecurit´ et de capacit´e, rien ne devrait ˆetre n´eglig´e pour r´eduire les ineﬃcacit´es des trajectoires en route, et att´enuer d’autant l’incidence environnementale. »

Positionnement du paradigme

Nous proposons dans cette th`ese l’´etude d’un nouveau syst`eme de circulation a´erienne, en coh´erence avec le projet SESAR d´ecrit ci-avant mais dont la mise en oeuvre ne peut ˆetre envisag´ee qu’`a tr`es long terme, au-del`a de la version initiale de SESAR pr´evue pour 2020. L’id´ee principale est de r´eduire la quantit´e de conflits et d’essayer, dans la mesure du possible, de voler sur des routes `a consommation optimale afin de diminuer l’impact environnemental. Pour cela, nous proposons de d´efinir des points mobiles fictifs et r´eguliers auxquels sont assujettis les avions durant la plus grande partie de leur trajet, voire la totalit´e. Les points mobiles peuvent avoir deux ´etats : autoris´e ou interdit. Seuls les points mobiles autoris´es ont le droit d’accueillir un avion. Autrement dit, un avion ne peut pas se trouver sur un point mobile interdit, ni en-dehors des points mobiles. Le statut des points mobiles est organis´e d’une fa¸con telle qu’il n’y a que peu de conflit entre les points mobiles autoris´es, et donc encore moins entre les avions. Le travail des contrˆoleurs se r´eduira ainsi `a r´esoudre les conflits r´esiduels.
Le syst`eme que nous proposons est fortement organis´e, notamment temporellement, puisqu’il impose aux avions de suivre un ensemble de points 4D. Nous nous pla¸cons donc `a l’oppos´e du Free Flight [7] et du Free Routing [4][6][7] ; dans le Free Flight, les avions peuvent prendre n’importe quelle route et assurent directement leur s´eparation, alors que dans le Free Routing les avions restent sous l’autorit´e des contrˆoleurs. Ces approches laissent beaucoup de libert´es aux avions, et ne pourront probablement pas ˆetre appliqu´ees dans des r´egions o`u la densit´ de trafic est tr`es importante, comme la r´egion du Benelux. Notre paradigme, au contraire, impose des profils de vitesses aux avions, ce qui permet d’augmenter la capacit´e du r´eseau.

Un paradigme organis´e pour le trafic a´erien

Ce chapitre a pour but d’exposer notre paradigme d’un point de vue op´erationnel. Pour cela, nous le d´ecrivons dans la section 2.1, et d´efinissons notamment les notions d’axes et de points mobiles. La section 2.2 est d´edi´ee `a l’´etat de l’art des ´etudes dont le but est d’augmenter la capacit´e de l’espace europ´een et/ou de r´eduire le nombre de conflits. Notre paradigme est r´egi par deux conditions, appel´ees condition d’unicit´e et condition de p´eriodicit´e, qui sont d´ecrites `a la section 2.3. Nous montrons que ces deux conditions sont op´erationnellement concevables. Nous d´efinissons dans la section 2.4 le probl`eme central de notre th`ese, appel´ probl`eme de la densit´ maximum, ainsi qu’un probl`eme connexe, le probl`eme de l’ensemble d’axes k1 −denses maximum. Enfin, dans la section 2.5, de nombreuses r´eponses sont propos´ees aux questions relatives `a la mise en place op´erationnelle de notre paradigme.

Description du paradigme

Dans cette th`ese, nous envisageons un nouveau syst`eme de trafic a´erien, caract´eris´ par un tr`es haut degr´ d’organisation, `a l’oppos´e du Free Flight [10]. Le concept fondamental de notre syst`eme est d’assujettir les avions `a suivre des points mobiles fictifs durant une grande partie ou la totalit´e de leur trajet. D’un point de vue op´erationnel, on peut supposer qu’une nouvelle g´en´eration de pilote automatique pourra suivre de fa¸con pr´ecise des consignes 4D, et en particulier les points mobiles de notre paradigme. Ces points mobiles sont organis´es et s´equenc´es de fa¸con `a ´eviter les conflits entre avions, notamment lorsque ces derniers convergent vers une mˆeme intersection.
Nous introduisons les d´efinitions suivantes, utilis´ees tout au long de la th`ese :
D´efinition 1 On appelle axe un ensemble constitu´e d’une origine, d’une destination et d’un profil tridimensionnel pour aller de l’origine vers la destination.
D´efinition 2 Sur chaque axe i sont g´en´er´es de fa¸con r´eguli`ere des points mobiles, qui se d´eplacent avec le mˆeme profil de vitesse vi. Ce profil d´epend du temps et est donn´e dans un rep`ere fixe par rapport a` la Terre. Ainsi, pour chaque axe, le temps s´eparant deux points mobiles successifs au passage d’un mˆeme point donn´e quelconque est constant. On l’appelle p´eriode de points mobiles et on le note Ti. Il faut noter qu’`a l’instant t = 0 il n’y a pas n´ecessairement un point mobile a` l’origine de l’axe. On appelle phase a` l’origine le temps entre l’instant initial et l’apparition du premier point mobile a` l’origine. On note ΔTi la phase a` l’origine de l’axe i.
D´efinition 3 On note p(i, x) le x`EME point mobile de l’axe i.
La figure 2.1 illustre les notations d´efinies ci-dessus. Il est important de noter que nous nous pla¸cons `a un horizon de temps de l’ordre d’une journ´ee, ce qui peut ˆetre consid´er´ comme un horizon de temps infini.

Am´eliorer le r´eseau de routes

Plusieurs articles s’int´eressent `a la modification du r´eseau de routes actuel, afin de le rendre plus eﬃcace. Dans [21], l’id´ee est de cr´eer un r´eseau prioritaire de routes directes entre les principales zones terminales (TMA) europ´eennes, et d’y aﬀecter un certain pour-centage du trafic total. Ce r´eseau est sans conflit et prioritaire, entraˆınant en th´eorie une diminution du nombre d’avions `a surveiller pour les contrˆoleurs. Hering [22] propose de te-nir compte du fait que 20% du trafic europ´een est intercontinental, c’est-`a-dire avec l’origine et/ou la destination hors de l’Europe. Cela engendre la cr´eation de deux axes d’autoroute (un axe Dublin-Ath`enes, un axe Madrid-Milan-Stockholm), pour lesquels l’auteur d´efinit au moins 2 voies dans chaque sens de circulation, et 8 points d’entr´ee/sortie.
Irvine et Hering [23] construisent un treillis sur une r´egion dense de l’Europe (cf figure 2.3). Cette structure est compos´ee verticalement de 9 niveaux de vol successifs (du FL300 au FL380). Sur chaque niveau de vol, les avions peuvent voler sur une paire de directions, compos´ee d’une direction altern´ee avec son oppos´ee. Entre deux niveaux successifs, les directions changent de 45˚. Il faut donc 4 niveaux de vol avant de retrouver la direction initiale. Le fait d’avoir 9 niveaux de vol dans ce treillis permet de r´ep´eter les mˆemes directions `a 2 niveaux de vol diﬀ´erents (et mˆeme 3 pour les directions du FL300). Les r´esultats num´eriques sont pour le moment limit´es, puisque les auteurs concluent sur une augmentation de 1,3% de la consommation et de 5% du nombre de conflits.

Etude dynamique du syst`eme a´erien

Une autre possibilit´e pour r´eduire le nombre de conflits consiste `a jouer sur la vitesse des avions `a court terme. Villiers [33] recommande une approche subliminale du contrˆole pour r´esoudre les conflits. Cela pourrait consister `a modifier l´eg`erement la vitesse des avions, de sorte que le changement ne soit pas per¸cu par le contrˆoleur et que les conflits soient evit´es. Constans et al. [14] proposent de minimiser une quantit´e de conflit potentiel, dans une boucle de commande `a horizon glissant, en modifiant les vitesses des avions. A chaque it´eration, un sous-probl`eme d’optimisation est r´esolu en utilisant la programmation lin´eaire. Les r´esultats donn´es consid`erent uniquement une partie du trafic journalier europ´een, et la quantit´e de conflit diminue de 6% `a 20%.

Vers une optimisation 4D

Des ´etudes r´ecentes proposent d’am´eliorer le syst`eme de trafic a´erien actuel en jouant non seulement sur la dimension spatiale, mais aussi sur la dimension temporelle. Gianazza [20] d´ecoupe ainsi les trajectoires des avions en segments d’une certaine longueur, auxquels sont associ´es des intervalles de temps pendant lesquels ils sont occup´es par un avion. Le but est ensuite de trouver des trajectoires 4D, s´epar´ees les unes des autres, pour les principaux flux en utilisant un algorithme A*. Les r´esultats sont pour le moment limit´es, puisqu’ils ne concernent que 7,3% du trafic europ´een et le temps de calcul est de plus de 24 heures. Dans sa th`ese [31], Richard se place dans le cadre de la r´egulation `a court terme du trafic a´erien et d´etermine les trajectoire 4D des vols, tout en respectant les capacit´es des secteurs et en minimisant les coˆuts des trajectoires (surconsommation, retard `a l’arriv´ee, propagation des retards). La mod´elisation de ce probl`eme en programme lin´eaire mixte est r´esolue `a l’aide d’une technique de g´en´eration de colonnes et de branch-and-bound.

Approches combinatoires

Certains auteurs essaient d’am´eliorer le syst`eme actuel en se basant sur des approches combinatoires de recherche op´erationnelle. Ainsi, Fondacci et al. [18] ´etudient de fa¸con plus pr´ecise la dimension verticale des vols. Pour cela, ils supposent que les avions peuvent changer de niveau de vol pendant leur phase de croisi`ere, en se limitant `a N = 2 niveaux. Ils essaient de minimiser le nombre de changements de niveau des avions afin qu’il ne reste aucune intersection entre les flux d’avions. Les auteurs montrent que ce probl`eme peut se r´eduire au probl`eme de Via Minimization et proposent un algorithme optimal, bas´e sur l’algorithme de Barahona [9]. Les auteurs examinent aussi le probl`eme consistant `a minimiser le nombre de niveaux de vol afin que deux ODs (Origine-Destination) au mˆeme niveau de vol ne s’intersectent pas. Ce probl`eme s’apparente `a un probl`eme de coloration, amenant les auteurs `a utiliser deux heuristiques. La premi`ere utilise des cliques maximales, et est donc elle-mˆeme bas´ee sur des heuristiques de cliques. L’heuristique de coloration aﬀecte ensuite `a chaque segment (qui repr´esente une OD) de la clique maximale (appel´ segment maˆıtre) une couleur, et essaie de colorer le plus de segments possible en cette couleur. L’heuristique ainsi obtenue est de complexit´e O(n5) ou O(n4 log log n) selon l’heuristique de clique utilis´ee. Dans la seconde heuristique, les segments maˆıtres sont obtenus en essayant de diviser au mieux l’espace. Cette heuristique a pour complexit´ O(n3). Les auteurs ´etudient aussi le probl`eme visant `a aﬀecter un niveau de vol `a chaque flux d’avions de fa¸con `a minimiser le nombre d’intersections sur chaque niveau de vol, en utilisant des heuristiques de N-coupes. Barnier et Brisset [11] ´etudient le mˆeme probl`eme, mais en utilisant un algorithme de clique et de la programmation par contraintes. Dans sa th`ese [20], Gianazza utilise un algorithme A* afin de calculer des trajectoires 3D, s´epar´ees les unes des autres, pour les principaux flux de trafic.
Ces approches visent principalement `a r´eduire le nombre d’intersections entre les diﬀ´erentes routes a´eriennes, et il est int´eressant de noter que les probl`emes associ´es peuvent ˆetre plac´es dans le domaine de la th´eorie des graphes d’intersections. Si M est une famille d’ensembles {Mi, i = 1, .., n}, on appelle graphe d’intersections de M le graphe G = (V, E), o`u chaque ensemble Mi de M d´efinit un sommet vi du graphe, et tel que ∀i, ∀j, i = j, vivj ∈ E ⇐⇒ Mi ∩ Mj = ∅
Suivant la g´eom´etrie des el´ements de M , diﬀ´erents noms sont donn´es aux classes de graphes construites. Une liste assez compl`ete des classes est donn´ee par Kratochvil [24]. La classe SEG est la classe de graphes d’intersections pour laquelle chaque el´ement Mi est un seg-ment dans le plan. En prenant leur projection, on peut consid´erer que les ODs sont des segments du plan. On peut ainsi construire un graphe d’intersections de segments, comme sur la figure 2.4.
Le probl`eme qui consiste `a aﬀecter diﬀ´erents niveaux de vol aux ODs qui s’intersectent revient donc `a r´esoudre un probl`eme de χ−coloration dans le graphe d’intersections.
Ehrlich et al. [16] montrent que le probl`eme de χ−coloration reste NP-diﬃcile, pour χ ≥ 3, dans la classe SEG. Kratochvil et Nesetril [25] prouvent que le probl`eme de stable maximum est NP-complet dans la classe SEG, y compris lorsque les segments n’ont que deux directions possibles. Ils d´emontrent aussi que le probl`eme de clique maximum est polynˆomial pour la classe SEG lorsque le nombre de directions est fini, en exposant un algorithme en O(nk+1) pour k directions. En revanche, le probl`eme de clique maximum pour un nombre non born´e de directions dans la classe SEG reste un probl`eme ouvert `a ce jour.

Position de la th`ese par rapport `a l’´etat de l’art

La mod´elisation des probl`emes de trafic a´erien avec les graphes de segments ne permet pas de tenir compte de la temporalit´ du probl`eme, tout comme les ´etudes pr´esent´ees dans la section 2.2.1. Dans cette th`ese, nous proposons une autre mod´elisation `a l’aide de deux graphes prenant en consid´eration les aspects spatiaux et temporels. Nous nous situons dans le cadre d’une optimisation quadridimensionnelle, en proposant de jouer sur les trajectoires et les vitesses des avions. Alors que Richard [31] s’attache `a optimiser `a court terme, le travail pr´esent´ ici se place `a un horizon de temps infini, ou de fa¸con plus op´erationnelle `a l’horizon d’une journ´ee. En se pla¸cant `a un horizon faible, Richard peut s’aﬀranchir des incertitudes li´ees notamment aux conditions m´et´eorologiques et aux retards. Au contraire, les solutions propos´ees par Gianazza [20] ne sont pas forc´ement r´eactives face aux incertitudes. L’approche propos´ee dans cette th`ese permet d’ˆetre robuste aux perturbations ; en eﬀet, l’une des id´ees principales consiste `a garantir des cr´eneaux de d´ecollage de fa¸con p´eriodique pour chaque vol. Cette possibilit´e est mod´elis´ee par la notion de densit´ qui est introduite `a la section 2.4.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction
1 Evolution n´ecessaire du syst`eme de trafic a´erien
1.1 Syst`eme a´erien actuel
1.1.1 L’organisation de l’espace
1.1.2 La gestion du trafic a´erien
1.1.3 Le travail des contrˆoleurs a´eriens
1.2 Limites du syst`eme
1.3 Evolution du syst`eme de trafic a´erien
1.4 Positionnement du paradigme
2 Un paradigme organis´e pour le trafic a´erien
2.1 Description du paradigme
2.2 Etat de l’art
2.2.1 Am´eliorer le r´eseau de routes
2.2.2 ´ Etude dynamique du syst`eme a´erien
2.2.3 Vers une optimisation 4D
2.2.4 Approches combinatoires
2.2.5 Position de la th`ese par rapport `a l’´etat de l’art
2.3 Conditions de l’´etude
2.4 D´efinition du probl`eme de la densit´e maximum
2.5 Probl`emes op´erationnels pos´es
3 Probl`eme de la densit´e maximum
3.1 Pr´esentation des graphes
3.1.1 Poids des cycles dans le graphe des axes
3.1.2 Lien entre le graphe des axes et le graphe des conflits
3.2 R´esultats sur le graphe des axes
3.2.1 Graphe des axes et cycles
3.2.2 D’un cycle vers une base de cycles
3.2.3 Caract´erisation des solutions 1 2−denses
3.2.4 Calcul en temps polynˆomial de w(GA)
3.2.5 Graphe des axes et planarit´e
3.3 R´esultats sur le graphe des conflits
3.3.1 Probl`eme de la densit´e maximum et coloration
3.3.1.1 Bornes inf´erieures au probl`eme de la densit´e maximum
3.3.1.2 Bornes sup´erieures au probl`eme de la densit´e maximum
3.3.2 Etude du graphe des conflits biparti
3.3.2.1 Une autre caract´erisation des solutions 1 2−denses
3.3.2.2 Comment reconnaˆıtre un graphe des conflits biparti ?
3.4 Synth`ese des r´esultats
4 Recherche de solutions op´erationnelles
4.1 Structures
4.1.1 Treillis dans le plan
4.1.1.1 Structure `a deux paires de directions
4.1.1.2 Structures `a trois paires de directions
4.1.1.3 Structures `a quatre paires de directions
4.1.2 Capacit´es des diff´erentes structures
4.1.3 Probl`eme de la sph`ere : d´eformation des structures
4.2 Pr´esentation d’une heuristique pour le probl`eme de l’ensemble d’axes 1 k−denses maximum
4.2.1 Se ramener `a un probl`eme de stable maximum
4.2.2 Discussion sur la qualit´e d’une solution exactement 1 k−dense
4.2.2.1 Propagation de l’existence de solutions exactement denses
4.2.2.2 Solutions optimales non exactement denses
4.2.2.3 G´en´eralisation sur les solutions non exactement denses
4.2.3 Heuristiques de stable maximum
4.2.3.1 Recherche d’un stable maximal initial
4.2.3.2 Recherche locale autour du stable initial
4.3 Synth`ese
5 Applications num´eriques
5.1 Description des donn´ees
5.2 Affectation des plans de vol `a un ou des treillis
5.2.1 Conditions d’affectation d’un vol `a un treillis
5.2.2 R´esultats des simulations
5.3 Affectation des plans de vol `a des axes de points mobiles en orthodromie
5.3.1 R´esultats des diff´erentes heuristiques de stable maximum
5.3.2 R´esultats des simulations
5.4 Affectation des plans de vol `a une combinaison d’axes en orthodromie et de treillis
Conclusion
Bibliographie