Télécharger le fichier original (Mémoire de fin d’études)
Outils d’aide a la decision en ordonnancement des avions
Center TRACON Automation System (CTAS) est l’outil pionnier d’aide a la decision en ordonnancement des arrivees concu par la NASA a la n des annees 1980 [58, 72]. Les outils equivalents europeens ont emerg rapidement [31] et sont de nos jours appeles Arrival Manager (AMAN) 5.
Arrival Manager (AMAN) et Departure Manager (DMAN) sont des outils d’aide a la decision destines aux contr^oleurs aeriens (en approche et a la tour de contr^ole) pour le sequencement des atterrissages et des decollages respectivement. De nos jours, plusieurs aeroports europeens sont equipes d’outils AMAN et DMAN.
En raison de l’importance de l’enjeu de l’ordonnancement des atterrissages compare a celui des decollages, les systemes AMAN se sont developpes plus t^ot et ont recu plus d’inter^et que les systemes DMAN. Il en resulte qu’a l’heure actuelle les systemes AMAN sont consideres plus matures. L’integration de AMAN et DMAN est prevue dans le cadre du programme europeen SESAR 6. En France, le systeme AMAN mis en place s’appelle MAESTRO, delivr par Thales Air System SAS. Il equipe, parmi d’autres, l’aeroport de Paris Charles de Gaulle (CDG).
AMAN
AMAN peut ^etre decompos en trois modules comme schematis dans la gure 1.2 : Prediction de trajectoire : Ce module integre des modeles de performance avion, les plans de vols, les donnees radar et les donnees meteo pour estimer l’heure d’approche sans contraintes (Expected Approach Time – EAT ) de chaque avion.
Sequencement : les avions sont generalement sequences selon leur ordre d’arrivee \premier arrive, premier servi ». D’autres regles peuvent ^etre appliquees telles que l’equite, la distribution du retard ou le groupement par classe de turbulence. Des que deux avions ne satisfont pas les criteres de separation, la sequence est revisee. Il en resulte de nouvelles heures d’approche sous contraintes.
Recommandations aux contr^oleurs : La di erence entre les heures d’approche sans et avec contraintes est calculee par avion en termes de temps a gagner (Time To Gain – TTG) ou de temps a perdre (Time To Lose – TTL). Certaines implementations sophistiquees d’AMAN proposent des suggestions de man uvres (par exemple, guidage radar, changement de vitesse) pour les contr^oleurs.
E-AMAN
E-AMAN (Extended AMAN) est une version de AMAN dont l’horizon operationnel a et etendu au-dela de la region de contr^ole (Terminal Maneuvring Area – TMA). Le rayon maximal de ce nouvel outil d’aide a la decision peut atteindre 500 NM [41]. L’inter^et de cette extension est de pouvoir commencer a ordonnancer les avions a destination du m^eme aeroport pendant la phase d’en-route, par exemple en ajustant convenablement leurs vitesses de croisiere. Ceci a pour avantage de minimiser et idealement eliminer l’attente circulaire, au niveau des circuits d’attente situes a la frontiere de la TMA.
XMAN (Cross-border AMAN) est l’appellation donnee a AMAN quand son rayon d’action englobe plusieurs pays. Dans le contexte europeen, les E-AMAN doivent ^etre egalement des XMAN.
La gure 1.3 montre des horizons operationnels d’un AMAN actuel, d’un XMAN et d’un E-AMAN gerant les arrivees sur la capitale britannique Londres.
Figure 1.3 { Horizons operationnels de AMAN, E-AMAN et XMAN au Royaume-Uni [59]
Programmation stochastique a deux etapes
La programmation stochastique est un paradigme de modelisation de problemes d’op-timisation prenant en compte l’incertitude sur certaines donnees d’entree du probleme. Ces donnees incertaines sont supposees des variables aleatoires dont les lois de probabilite sont connues a l’avance.
La programmation stochastique a deux etapes distingue deux etapes de decision. Dans la premiere etape, les valeurs des donnees incertaines sont considerees inconnues. Une decision, dite de premiere etape, doit ^etre prise a n d’optimiser un certain critere de premiere etape. Dans la deuxieme etape, l’incertitude est supposee levee ; les donnees incertaines sont alors connues avec certitude. Ainsi, un nouveau probleme d’optimisation { deterministe {, dit de deuxieme etape, est forme. Une nouvelle decision, dite egalement de deuxieme etape ou de recours, doit ^etre prise a n d’optimiser un critere de deuxieme etape. Remarquons que la de nition du probleme de deuxieme etape depend des valeurs incertaines revelees. Ainsi, chaque levee de l’incertitude peut donner lieu a un probleme d’optimisation de deuxieme etape di erent.
La programmation stochastique a deux etapes permet de lier les problemes de premiere et de deuxieme etape en considerant la premiere etape comme une etape ma^tresse et la deuxieme comme une sous-etape dependante des decisions de la premiere etape et de la levee de l’incertitude. Notons qu’une telle structure se retrouve egalement dans l’optimisation bi-niveau [4]. La fonction objectif d’un probleme stochastique a deux etapes s’exprime, classiquement, comme la somme du critere de premiere etape et l’esperance du critere de deuxieme etape.
La solution optimale d’un tel probleme est une decision de premiere etape uniquement, dite une decision a priori, qui optimise cette fonction objectif bi-critere. Cette decision a priori a l’avantage de ne pas ^etre myope par rapport a la deuxieme etape, mais surtout d’^etre la solution permettant d’obtenir le meilleur \co^ut en moyenne », si le probleme de deuxieme etape serait a formuler et a resoudre un grand nombre de fois (selon la loi des grands nombres). Aussi faut-il preciser qu’il n’est pas question dans la programmation stochastique a deux etapes de fournir une \politique » de decision qui indiquerait, en plus de la decision optimale de la premiere etape, la decision optimale de la deuxieme etape en fonction de la decision de la premiere etape et de la realisation de l’incertitude (comme, par exemple, dans un processus de decision de Markov ou dans la programmation dynamique stochastique [11, chap. 2.10]).
En toute generalite, une decision de recours (ou de deuxieme etape) peut representer une revision de la decision de premiere etape ou bien une nouvelle decision correspondant a un nouveau probleme d’optimisation, qui emerge \naturellement » suite a la revelation de l’incertitude. Dans la suite, nous rapportons deux exemples de la litterature representant les deux points de vue. Probleme du vendeur de journaux : En premiere etape, ne connaissant pas la demande de sa clientele du lendemain, le vendeur doit decider de la quantite de journaux a approvisionner (decision de premiere etape). Le lendemain, le pro t est fonction du minimum entre son stock et la demande observee, mais il peut eventuellement revendre, a perte, le surplus de journaux (decision de deuxieme etape) si son stock procure la veille excede la demande observee.
Probleme du fermier : Dans l’exemple du fermier, present dans [11], la decision de premiere etape consiste a decider des surfaces a planter pour chaque type de culture (ble, canne a sucre, etc), le rendement etant inconnu au prealable. Apres la recolte (deuxieme etape), le fermier doit decider des quantites a vendre sur le marche et de celles a conserver ou a se procurer pour satisfaire la consommation de ses betails. Le probleme de deuxieme etape n’a pas de sens tant que la recolte n’a pas eu lieu. Il est plut^ot un nouveau probleme qui appara^t apres revelation de l’incertitude.
La revelation de l’incertitude donne lieu a di erents scenarios, dont le nombre peut ^etre arbitrairement grand, voire in ni dans le cas de variables aleatoires continues par exemple.
La programmation stochastique a deux etapes ne cherche pas a se proteger contre les scenarios extr^emes du futur (contrairement a l’optimisation robuste, par exemple) mais plut^ot a fournir des decisions de premiere etape permettant d’optimiser en esperance les criteres de premiere et de deuxieme etape sur l’ensemble des scenarios consideres.
Il important de preciser qu’optimiser l’esperance du critere de deuxieme etape n’est pas equivalent a optimiser ledit critere sur le scenario esper (ou moyen). D’ailleurs, l’ecart entre les valeurs des solutions optimales de ces deux problemes d’optimisation constitue une quantite importante en programmation stochastique, appelee la valeur de la solution stochastique.
Dans la suite de cette section, nous presentons la forme generale d’un programme stochastique a deux etapes, ainsi que di erentes notions generales telles que les types de recours et la valeur de la solution stochastique. Ensuite, nous presentons la methode d’approximation par moyenne empirique, ou SAA (\Sample Average Approximation »), utilisee sur des problemes stochastiques avec un grand nombre de scenarios. Finalement, nous abordons les methodes de resolution pour les programmes stochastiques, notamment la decomposition de Benders.
Formulation et notions generales
Soit m1; m2; n1; n2 et r des entiers naturels. Soit x 2 Rr [Zn1 r un vecteur de variables de decision, A une matrice de Rm1 Rn1 et b un vecteur de Rm1 . Soit ! un vecteur de variables aleatoires de lois connues. Une realisation d’un tel vecteur est notee ! . Soit f1 une fonction lineaire de nie sur Rn1 a valeurs dans R. Soit y 2 Rn2 un vecteur de variables de decision, B (!) une matrice de Rm2 Rn1 , C une matrice de Rm2 Rn2 , et d (x; !) un vecteur de Rm2 . Soit f2 une fonction lineaire en y et a valeurs dans R. En n, notons E! [:] l’operateur de l’esperance relativement a la variable aleatoire !.
Type de recours : Selon la forme du probleme de deuxieme etape, il est possible que certaines solutions de premiere etape puissent donner des problemes de deuxieme etape non realisables. Ceci nous amene a distinguer di erents types de problemes de deuxieme etape, appeles aussi types de recours :
recours complet : un recours est dit complet si le probleme de deuxieme etape ad-met des solutions realisables, qu’il y ait ou non des solutions pour le probleme de premiere etape recours relativement complet : un recours est dit relativement complet si le probleme de deuxieme etape admet des solutions realisables pour toute solu-tion realisable du probleme de premiere etape recours xe : le recours xe correspond au cas ou la matrice des contraintes C ne depend pas de x et ! (comme presentee ici).
recours simple : le recours simple correspond au cas ou la matrice des contraintes C a une structure particuliere : C = (Im2 Im2 ), ou Im2 est la matrice identit de nie sur Rm2 Rm2 . Notons egalement que le recours simple est un cas particulier du recours complet. Le probleme du vendeur des journaux est un exemple d’un probleme stochastique a deux etapes avec un recours simple [11].
Notons Q : x 7!E! [Q (x; !)] la fonction de recours minimum esper . Alors, la pro-jection de (2SSP) sur l’espace des x s’ecrit :
x 1 Q (x) (Proj-2SSP)
min f (x) +
Ax = b
Theoreme 1.3.1. Dans le cas de la programmation stochastique lineaire a deux etapes (i.e., les problemes de premiere et de deuxieme etape sont lineaires en leurs variables de decision, x et y respectivement) avec recours xe (la matrice C ne depend pas de x et !), alors Q est convexe en x [11].
Le theoreme 1.3.1 exprime le fait que la programmation stochastique lineaire avec recours xes s’inscrit bien sous le volet de la programmation convexe. Toutefois, le calcul de Q (x) est souvent tres di cile et necessite le calcul d’une integrale multiple [11, chap. 3.1]. Dans la suite, nous traitons les deux cas possibles des valeurs des variables aleatoires selon leur cardinalite (denombrables ou non denombrables), et nous presentons comment le calcul, ou a defaut l’approximation, de Q (x) est possible.
Cas de variables aleatoires discretes a support ni : Dans le cas de variables aleatoires discretes a support ni, le calcul de l’esperance se resume a un calcul de moyenne. Notons = f!1; !2 : : : ; !K g le support de la variable aleatoire !, ou chaque realisation !k, pour k 2 f1; : : : ; K g, a une probabilite pk. Rappelons qu’a chaque realisation !k et pour un vecteur de decision de premiere etape donne, x, un probleme k de deuxieme etape est formule. Notons yk le vecteur de decision pour ce probleme k de deuxieme etape.
Alors, (2SSP) peut ^etre re ecrit comme suit :
x 1 K k yk 2 k k
min f x X p min f (x; y ; ! )
B (!k) x + Cyk = d (x; !k) ; k 2 f1; : : : ; Kg
Ou encore :
min Xk (x; yk; !k) (Determ. Eq.)
f1 (x) + pkf2
k=1;:::;K =1
s.c. Ax = b
B (!k) x + Cyk = d (x; !k) ; k 2 f1; : : : ; Kg
Cette derniere formulation (Determ. Eq.), appelee l’equivalent deterministe, se presente comme un programme lineaire deterministe (a une seule etape), comprenant K copies du probleme de deuxieme etape, et donc potentiellement de grande taille. La resolution de (Determ. Eq.) peut ^etre envisagee par Branch-and-Cut via un solveur generique de pro-grammes lineaires en variables mixtes (tel que CPLEX). Neanmoins, quand le nombre de scenarios augmente, (Determ. Eq.) peut devenir de tres grande taille et sa resolution clas-sique par Branch-and-Cut sera ine cace. Heureusement, sa matrice des contraintes est creuse, presentant des colonnes liantes (B (!k) x) et des blocs separables par scenario (Cyk pour k 2 f1; : : : ; K g). Une telle structure se pr^ete bien a une decomposition de Benders avec des sous-problemes separables par scenario. Quand elle est appliquee a la program-mation stochastique a deux etapes, la decomposition de Benders est souvent evoquee sous le nom de l’algorithme L-Shaped [11, 71]. Dans la sous-section 1.4, nous presentons la decomposition de Benders, ainsi que son application a la programmation stochastique a deux etapes.
Cas de variables aleatoires a support in ni (ou de tres grande taille) : Quand le support des variables aleatoires est in ni ou de tres grande taille, l’approximation par moyenne empirique, appelee SAA (pour Sample Average Approximation), permet de reduire le calcul de l’esperance au calcul d’une moyenne sur un ensemble ni de scenarios, appel un echantillon. Cette methode sera presentee dans la Sous-section 1.3.3. En uti-lisant la methode SAA, le programme stochastique resultant, dit programme d’approxi-mation, presente une structure similaire a (Determ. Eq.), suggerant ainsi l’utilisation des m^emes techniques de resolution.
Pour resumer, la programmation stochastique a deux etapes permet de modeliser un probleme d’optimisation comprenant deux etapes de decision entre lesquelles des donnees incertaines, supposees suivre des lois de probabilite connues, sont revelees. Le probleme de deuxieme etape depend de l’incertitude revelee. La fonction objectif a optimiser est la somme du critere de la premiere etape et de l’esperance du critere de la deuxieme etape. Le cas de la programmation stochastique lineaire a deux etapes avec recours xe releve de l’optimisation convexe. Un programme stochastique lineaire a deux etapes, formule sur un ensemble ni de scenarios, presente une structure en blocs separables par scenario avec des variables liantes. Une telle structure est favorable a une resolution e cace par decomposition de Benders.
Quels que soient les details de la modelisation, un programme stochastique est souvent plus di cile a resoudre qu’un programme deterministe ou les donnees incertaines sont reduites a leurs valeurs moyennes. Pour un decideur, il est important de pouvoir justi er son choix de modelisation de l’incertitude comme des variables aleatoires et son choix du paradigme de la programmation stochastique. La prise en compte de l’incertitude via la formulation d’un programme stochastique a deux etapes peut ^etre justi ee en calculant une quantite appelee la valeur de la solution stochastique. Nous en donnons la de nition dans la suite.
Valeur de la solution stochastique
En presence d’incertitude sur les donnees d’entree, le decideur peut se poser la question sur la pertinence de la prise en compte de l’incertitude via des variables aleatoires (de lois connues) face a la reduction des donnees incertaines a leurs valeurs moyennes. La premiere alternative conduit le decideur a formuler un probleme stochastique, eventuellement a deux etapes tel qu’il est le cas dans le present manuscrit. Un tel choix de modelisation peut avoir l’avantage de mieux representer le probleme reel. La deuxieme alternative amene a la formulation d’un probleme d’optimisation deterministe, utilisant uniquement les valeurs moyennes des donnees, appel probleme du scenario moyen (ou \Expected Value Problem » en anglais).
A n de quanti er l’avantage de la modelisation plus ne de l’incertitude par des va-riables aleatoires, il est possible de calculer la valeur de la solution stochastique, notee VSS. D’une part, par de nition, une solution stochastique, notee xSP, est une solution optimale obtenue en resolvant le probleme stochastique a deux etapes : xSP 2 arg min ff1 (x) + E! [Q (x; !)] jAx = bg (1.1)
Notons vSP la valeur de la fonction objectif correspondant a la solution stochastique xSP. D’autre part, notons xEV la solution du probleme du scenario moyen (appelee aussi solution deterministe), de nie comme suit : xEV 2 arg min ff1 (x) + Q (x; E [!]) jAx = bg (1.2)
La valeur de la solution deterministe, notee vEV, correspond a l’evaluation de xEV sur le probleme stochastique a deux etapes. Plus formellement, supposons que A xEV = b et Q (xEV) < 1 (i.e., xEV est une solution realisable de (2SSP)), alors vEV est de nie comme suit : vEV = f1 (xEV) + Q (xEV) (1.3)
La valeur de la solution stochastique, VSS, est de nie comme la di erence absolue entre la valeur optimale du probleme stochastique a deux etapes, vSP, et l’evaluation de la solution du probleme du scenario moyen sur le probleme stochastique a deux etapes, vEV : VSS = vSP vEV (1.4)
Approximation par moyenne empirique
Nous presentons ici une breve introduction a la methode d’approximation par moyenne empirique (de l’anglais : Sample Average Approximation – SAA) est tiree de [29, chap. 8] et de [64]. Nous presenterons trois resultats de convergence de la methode SAA qui sont utilises dans les chapitres 3 et 4 de ce manuscrit.
Dans le contexte de la programmation stochastique a deux etapes, le terme d’esperance, E! [Q (x; !)], peut ^etre approxime par une moyenne empirique sur un echantillon donne de nS scenarios, S = !1; : : : ; !nS . Soit le programme suivant, appel programme d’approximation SAA, de ni pour l’echantillon S :
min f1 (x) + 1 nS Q (x; !s) (Approx-2SSP)
x =1
s.c. Ax = b S Xs
avec : Q (x; !) = min f2 (x; y; !)
B (!) x + Cy = d (x; !)
Notons v? la valeur optimale du probleme d’origine (2SSP). Notons v^ (nS) la valeur optimale de (Approx-2SSP), pour un echantillon S quelconque de taille nS. Remarquons qu’il est plus correct de noter la valeur optimale de (Approx-2SSP) comme v^ (S). Mais, a n de presenter les resultats de convergence, la quantite d’inter^et est la taille de l’echantillon nS, plus que l’echantillon m^eme. Remarquons que v^ (nS) est une variable aleatoire. Nous avons le resultat de convergence suivant Theoreme 1.3.3 (Proposition 8.6, [29], Proposition 5.6, [64]). Pour tout nS 1, nous avons :
| E [^v (nS)] E [^v (nS + 1)]
| E [^v (nS)] v?
Rappelons que pour deux fonctions f : n 7!f (n) et g : n 7!g (n), f est un grand \O » de g, note f = O (g), veut dire que f ne cro^t pas plus rapidement que g, quand n ! 1. Quand f(n) ! l et g(n) ! l pour n ! 1, f = O (g) signi e que f converge vers l au mieux aussi rapidement que g.
Sous des hypotheses faibles de regularite, nous avons le theoreme suivant sur le taux de convergence de la methode SAA (comme une application du theoreme 5.7, [64]) : 1=2
Decomposition de Benders
La decomposition de Benders est une methode de resolution de programmes lineaires en variables mixtes, qui a et d’abord proposee par [7]. Cette methode est motivee par la remarque que dans un programme lineaire en variables mixtes, si les variables entieres sont xees, alors le probleme se reduit a un programme lineaire, souvent facile a resoudre. Le probleme en variables mixtes peut alors ^etre partitionne en deux problemes : un probleme ma^tre de Benders, comprenant toutes les variables entieres, et un sous-probleme de Ben-ders, comprenant les variables continues. Une variable continue, dite de reformulation, est ajoutee a la fonction objectif du probleme ma^tre a n de modeliser la valeur optimale du sous-probleme. Le schema de resolution classique d’un tel programme selon cette parti-tion est un schema iteratif, ou a chaque iteration il y a resolution du probleme ma^tre, ensuite resolution du sous-probleme, et en n une generation de coupes, dits de Benders, a integrer au probleme ma^tre.
Dans la suite, nous presentons le principe de la reformulation de Benders et de la resolution par decomposition de Benders. Ensuite, nous donnons quelques techniques d’acceleration de la decomposition de Benders. Le lecteur interess peut se referer a la revue de litterature [62]. Decomposition de Benders La decomposition de Benders commence par la resolution du probleme ma^tre de Benders rel^ache initial (PMR0), qui correspond a la reformulation de Benders mais sans aucune coupe d’optimalite, ni de realisabilit . Une solution du probleme ma^tre rel^ache (^x0; ^0) est trouvee. Ensuite, iterativement, le sous-probleme de Benders correspondant a la solution x^0, note (SPB(^x0)), est formule et resolu. Si (SPB(^x0)) est non-realisable, alors une coupe de realisabilit de la forme (1.5) est ajoutee au probleme ma^tre rel^ache. Sinon, autrement dit si (SPB(^x0)) est optimal, et si ^0 < vSP B(^x0), alors une coupe d’optimalite de la forme (1.6) est ajoutee au probleme ma^tre rel^ache.
Suite a l’ajout de coupes au probleme ma^tre rel^ache (PMR0), un nouvelle iteration commence avec le nouveau probleme ma^tre de Benders rel^ache (PMR1). Ce dernier est resolu une nouvelle fois, pour donner une nouvelle solution (^x1; ^1).
L’algorithme de decomposition de Benders s’arr^ete quand pour une iteration i ( 0) le sous-probleme de Benders (SPB(^xi)) est optimal et ^i = vSP B(^xi).
La solution optimale de (ORG) est (^xi; y^i), ou y^i est la solution optimale de (SPB(^xi)).
Application a la programmation stochastique a deux etapes
La decomposition de Benders a et appliquee avec succes a la resolution de programmes stochastiques a deux etapes [71, 62]. Dans ce contexte, il est souvent appel l’algorithme du L-Shaped [11]. En e et, la structure d’un programme stochastique a deux etapes co ncide avec le partitionnement en un probleme ma^tre, correspondant a la premiere etape, et un sous-probleme, correspondant a la deuxieme etape. En outre, la reformulation de Ben-ders peut ^etre vue comme la projection du probleme d’origine (ORG) sur l’espace des variables du probleme ma^tre, x. Ainsi, la valeur de la variable de reformulation peut ^etre vue comme l’approximation, par valeurs inferieures, de Q (x). Les coupes de Benders (1.5) et (1.6) servent a corriger cette approximation. Comme Q est une fonction convexe (theoreme 1.3.1), les coupes de Benders peuvent ^etre vues comme des hyperplans-supports de Q.
Remarquons que dans l’introduction ci-dessus a la decomposition de Benders, nous avons consider le cas general ou le sous-probleme de Benders ne presente pas de structure particuliere. Par contre, en programmation stochastique a deux etapes, le sous-probleme de Benders est separable par scenario, donnant lieu a plusieurs sous-problemes, ou chaque sous-probleme correspond a un probleme de deuxieme etape pour un scenario donne. Un des avantages d’une telle separabilit est de pouvoir resoudre chaque sous-probleme independamment des autres. La resolution exploitant la separabilit est souvent plus e cace que la resolution directe d’un sous-probleme unique issu de l’agregation des sous-problemes par scenarios. Egalement, la parallelisation peut ^etre envisagee surtout quand le nombre de scenarios de deuxieme etape est tres grand.
Dans l’algorithme du L-Shaped [11], il est preconis de veri er d’abord que tous les sous-problemes sont realisables. En cas de non realisabilite, uniquement les coupes de realisabilit sont ajoutees. Sinon, autrement dit si tous les sous-problemes sont realisables, alors les coupes d’optimalite sont ajoutees (si besoin).
En n, suite a la resolution separee de chaque sous-probleme, trois approches sont possibles en vue de generer et d’ajouter les coupes de Benders au probleme ma^tre rel^ache :
1. D’abord, il est possible d’agreger les solutions sur tous les sous-problemes pour retrouver la solution du sous-probleme agrege, et ensuite d’appliquer le schema de resolution decrit plus haut. Une seule coupe (au plus) peut alors ^etre generee par iteration. Nous ferons reference a cette approche sous le nom de la decomposition de Benders simple coupe.
2. Une deuxieme approche, quali ee de desagregee, est de generer une coupe de Ben-ders par sous-probleme et d’ajouter ces coupes au probleme ma^tre rel^ache. Cette approche sera appelee la decomposition de Benders multi-coupes.
3. Une troisieme approche \partiellement agregee » est d’agreger les solutions de cer-tains sous-problemes d’un m^eme groupe de scenarios. Ainsi, il sera possible de generer une coupe qui correspond au sous-probleme issu de l’agregation des sous-problemes d’un m^eme groupe de scenario. Notons que le partitionnement des scenarios en groupes reste a de nir par l’utilisateur. Ainsi, une coupe sera po-tentiellement generee pour chaque groupe de sous-problemes. Une telle approche est investiguee dans le chapitre 4.
L’avantage de la version multi-coupes est de pouvoir generer des coupes de meilleure qualite, dans le sens d’approcher plus nement la fonction Q. D’autre part, son principal inconvenient est le grand nombre de coupes pouvant s’accumuler au l des operations. Par contre, l’approche \simple coupe » permet de reduire le nombre des coupes generees par iteration au detriment de la qualite des coupes. En n, la version partiellement agregee peut presenter un bon compromis, surtout si les scenarios peuvent ^etre regroupes d’une facon non triviale.
Dans la suite, nous presentons l’algorithme de decomposition de Benders simple coupe.
Techniques d’acceleration
M^eme si la decomposition de Benders est une methode e cace de resolution des pro-grammes lineaires en variables mixtes, sa mise en uvre informatique peut ^etre di cile et sa performance peut ne pas ^etre a la hauteur des attentes, m^eme quand il s’agit de l’appliquer sur des cas bien adaptes comme des programmes stochastiques a deux etapes. Il n’est donc pas surprenant qu’une implementation \classique » de la decomposition de Benders puisse ^etre moins performante qu’un Branch-and-Cut d’un solveur de pointe. De nombreux auteurs ont etudie les raisons de la mauvaise performance en pratique de la decomposition de Benders. Leurs travaux ont conduit a proposer de nombreuses tech-niques algorithmiques d’acceleration. Le lecteur interess est refer a l’article [62] pour un panorama assez complet de ces techniques d’acceleration. Notons que, recemment, a partir de sa version 12.7, le solveur CPLEX d’IBM integre un algorithme de decomposition de Benders automatique qui pro te de plusieurs techniques d’acceleration. Dans la suite, nous decrivons quelques techniques classiques d’acceleration de la decomposition de Benders.
De nos jours, les solveurs de pointe a base de Branch-and-Bound o rent des fonc-tionnalites avancees comme les callbacks, permettant a l’utilisateur de modi er le com-portement de l’algorithme en cours de resolution. Plus particulierement, un cut callback permet d’ajouter des coupes dynamiquement. Une telle fonctionnalite, facile a prendre en main, permet d’implementer une version de la decomposition de Benders dite Branch-and-Benders-Cut, ou la decomposition de Benders est integree dans un arbre de recherche de type Branch-and-Bound.
L’algorithme de la decomposition de Benders present au paragraphe 1.4.2 suppose qu’a chaque iteration, le probleme ma^tre de Benders est resolu a optimalite, avant de resoudre le sous-probleme. En e et, les solutions entieres non optimales peuvent aussi servir pour formuler des sous-problemes et generer des coupes de Benders valides. Selon cette observation, a chaque n ud de l’arbre de recherche du Branch-and-Bound, si une solution entiere est trouvee, alors il est possible de generer des coupes de Benders. Ce fonctionnement est facile a mettre en place gr^ace au lazy constraint callback appel par le solveur CPLEX chaque fois qu’il trouve une solution entiere.
Dans une telle implementation, un seul arbre de recherche est dresse, au bout duquel la solution optimale retournee correspond a la solution optimale du probleme d’origine. Les implementations recentes de la decomposition de Benders utilisent, le plus souvent, un seul arbre de recherche. Remarquons qu’il n’est pas necessaire qu’une solution d’un probleme ma^tre de Ben-ders soit entiere pour donner des coupes de Benders valides. Ainsi, m^emes les solutions fractionnaires peuvent ^etre exploitees, au m^eme titre que les solutions entieres.
Schema de resolution en deux phases
McDaniel and Devine [54] proposent d’appliquer la decomposition de Benders en deux phases. Dans la premiere phase, la relaxation lineaire du probleme ma^tre de Benders rel^ache est resolue par decomposition de Benders. Les auteurs montrent que les coupes generees pendant cette premiere phase sont valides pour le probleme d’origine, lineaire en variables mixtes. Dans la seconde phase, les contraintes d’integralit sont reintroduites et la decomposition de Benders est relancee sur le probleme ma^tre rel^ache, mais cette fois-ci enrichi des coupes trouvees en premiere phase.
Une telle approche peut ^etre aisement incluse dans un Branch-and-Benders-Cut en implementant une decomposition de Benders \traditionnelle » en premiere phase unique-ment, pendant laquelle les coupes de Benders sont ajoutees explicitement comme des contraintes au probleme ma^tre. Cette procedure ressemble a une methode classique de plans secants.
Coupes Pareto-optimales
Magnanti and Wong [53] observent que, dans plusieurs applications, le sous-probleme dual de Benders est degener , c’est-a-dire qu’il possede plusieurs solutions optimales. Sa-chant que chaque solution duale du sous-probleme de Benders peut donner une coupe (d’optimalite) de Benders, potentiellement di erente, Magnanti and Wong [53] montrent qu’il existe une relation de dominance (voir la de nition en chapitre 4) entre toutes ces coupes. Plus particulierement, il est possible de trouver un ensemble de coupes de Ben-ders qui ne sont dominees par aucune autre coupe. Ces coupes de Benders non-dominees sont dites des coupes Pareto-optimales. En generant des coupes Pareto-optimales, le nombre de coupes de Benders ainsi que le nombre d’iterations necessaires pour resoudre le probleme sont reduits. Par consequent, le temps de resolution peut ^etre reduit a son tour. A n d’obtenir une coupe Pareto-optimale a une iteration donnee, l’article [53] pro-pose de resoudre un programme lineaire auxiliaire, appel le probleme de Magnanti-Wong. En pratique, l’apport des coupes Pareto-optimales est juge selon le compromis entre le temps passe a resoudre les problemes auxiliaires et le temps gagne en raccourcissant le chemin de resolution (gr^ace aux coupes de meilleure qualite). Une di culte pratique supplementaire dans l’implementation des coupes Pareto-optimales est de formuler cor-rectement le probleme de Magnanti-Wong qui requiert un point c ur (\core point ») ; de ni comme un point dans l’interieur relatif de l’enveloppe convexe du probleme ma^tre de Benders.
D’autres techniques telles que la separation \In-Out » [25, 26] ou une version simpli ee de la decomposition de Benders partielle [20] peuvent ^etre testees rapidement avec un e ort d’implementation relativement reduit, dans le cas d’un programme stochastique a deux etapes.
Table des matières
1 Introduction
1.1 Minima de séparation et turbulences de sillage
1.1.1 Séparation radar
1.1.2 Séparation de turbulence de sillage
1.2 Outils d’aide à la décision en ordonnancement des avions
1.2.1 AMAN
1.2.2 E-AMAN
1.3 Programmation stochastique à deux étapes
1.3.1 Formulation et notions générales
1.3.2 Valeur de la solution stochastique
1.3.3 Approximation par moyenne empirique
1.4 Décomposition de Benders
1.4.1 Principe
1.4.2 Application à la programmation stochastique à deux étapes
1.4.3 Techniques d’accélération
2 état de l’art
2.1 Ordonnancement déterministe des avions
2.1.1 Ordonnancement des avions sur une piste unique
2.1.2 Ordonnancement sur des pistes multiples
2.1.3 Analogies et complexités
2.1.4 Limites des analogies
2.1.5 Variantes polynomiales
2.1.6 Modèle de Beasley et al. [5]
2.2 Ordonnancement des atterrissages d’avions sous incertitude
2.2.1 Modèles stochastiques à deux étapes
2.2.2 Autres travaux
3 Démonstration de faisabilité et étude numérique { A proof of concept and a numerical study
3.1 Introduction
3.1.1 Literature review
3.1.2 Contribution and paper outline
3.2 Problem statement
3.2.1 Minimum-time separation at the IAF
3.2.2 Time windows at the IAF
3.3 Solution method
3.4 Computational study
3.4.1 Instances and problem characteristics
3.4.2 Optimization parameters
3.4.3 Results for instance 1
3.4.4 Comparison of real-time solution methods : scenario-based versus replication-based approaches
3.4.5 Results for instance 2
3.4.6 Eect on FCFS policy performance in the terminal area
3.5 Conclusions
4 Modélisation par programmation stochastique à deux étapes { Two- stage stochastic programming modeling
4.1 Introduction
4.2 Problem statement
4.3 A two-stage stochastic optimization model with recourse
4.3.1 Second-stage objective function : minimizing total time-deviation impact cost
4.3.2 Reformulating probability constraints in the i.i.d. case
4.4 Solution methods
4.4.1 Model with Sample Average Approximation
4.4.2 Benders reformulations
4.4.3 Implementing Benders decomposition
4.5 Computational study
4.5.1 Instances and parameter values
4.5.2 Determining an appropriate number of scenarios
4.5.3 Value of the stochastic solution
4.5.4 Solution-method performance comparison
4.6 Conclusion and perspectives
4.7 Appendix : Extensive results
5 Extension au cas de plusieurs points de début d’approche { Extension to the multiple-IAF case
5.1 Introduction
5.2 Problem statement
5.3 First-variant model : IAF assignment as a rst-stage decision
5.3.1 First-stage problem
5.3.2 Second-stage problem
5.3.3 Candidate expressions for the second-stage objective function :
5.3.4 Full two-stage stochastic model for the rst variant
5.4 Second-variant model : IAF assignment as a problem input
5.5 Computational study
5.5.1 Data
5.5.2 Solution method
5.5.3 Results
5.6 Conclusions and perspectives
6 Conclusion
Annexe A Introduction à la gestion de trafic aérien
A.1 Gestion de trafic aérien
A.2 Phases de vol
A.3 Espaces aériens et organismes de contr^ole associés
A.3.1 Zone de contr^ole – CTR
A.3.2 Région de contr^ole – TMA
A.3.3 Région d’information de vol – FIR
A.3.4 TMA Etendue (Extended TMA – E-TMA)
Annexe B Procédures de décollage et d’atterrissage
B.1 Procédure de décollage
B.2 Procédure d’approche
