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 rapport-gratuit.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