, Solution method : Deterministic equivalent problem solved by CPLEX Chapitre 6. Conclusion

. Finalement, L. Dans-cette-thèse, and . Paradigme, de choix pour la prise en compte de l'incertitudeétait la programmation stochastiqueà deuxétapes. Cela ne réduit en rien le potentiel d'autres paradigmes d'optimisation sous incertitude, tels que la programmation robuste ou l'optimisation en ligne (online)

, Il est du ressort du contrôle en approche (APP) de garantir la sécurité des avionsévoluant dans une TMA : avions en approche et avions en montée. Une TMA est cylindrique aussi avec un rayon d'environ cinquante miles nautiques. Quantà sa limite verticale supérieure

, Pendant la phase de vol en-route, tant que l'avionévolue dans des secteurs contrôlés de l'espace aérien inférieur 6 , il bénéficie du service de contrôle délivré par les centres de contrôle régionaux (CCR) successifs par lesquelles il passe, A.3.3 Région d'information de

, Une TMAétendue est une TMA dont le diamètre aété augmenté au détriment de l'espace aérien en-route. Le diamètre d'une TMAétendue atteint une centaine de miles nautiques, Le contrôle des avions dans une TMAétendue permet de mieux anticiper le séquencement des avionsà l'IAF

, Au-delà, c'est l'espace aérien dit supérieur

, Annexe B Procédures de décollage et d'atterrissage B.1 Procédure de décollage

, La progression d'un avion dans la procédure de décollage est sujetteà l'attribution par les contrôleurs de la tour de contrôle d'autorisations, appelées clairances,à l'avion en question. Cette procédure se décompose en 4 phases : Repoussage push-back : Après avoir effectué les opérations d'escale (débarquement / embarquement des passagers et des bagages, réapprovisionnement en carburant etc

. Roulage, Une fois que l'avion eut quitté son stationnement parking et que les moteurs eurentété allumés, le pilote demande la clairance de roulage, qui l'autorisè a suivre des voies de circulation (taxiways) jusqu'au point d'arrêtà l'entrée d'une piste de décollage. Les voies de circulation, le point d'arrêt et la piste de décollage

, Décollage : Le contrôleur autorise l'avion en attenteà l'entrée de la piste de s'aligner pour le décollage. L'avion s'aligne alorsà la piste de décollage et met la poussée des avionsà son maximum. L'avion accélère età l'atteinte de la vitesse de rotation (V R ), le pilote lève le nez de l'avion. Porté par la force de l'air sous ses ailes, l'avion prend son envol et entame sa montée

. Montée-initiale, Dès que l'avion dépasse la hauteur de 35 piedsà la vitesse de sécurité (V 2 ), le décollage est considéré comme réussi. L'avion poursuit sa montée généralement en suivant une SID indiquée par la tour de contrôle

, La dernière portion de la phase d'en-route d'un vol finit par une STAR se terminant au point d'entrée de l'espace aérien en approche (TMA), appelé repère d'approche initiale (Initial Approach Fix -IAF )

, Expected Approach time -EAT ) est estimée pour chaque aéronef. Elle correspondà l'heure de passage de l'aéronefà l'IAF ou de sortie du "stack" s'il yétait maintenu. Un temps estimé d'atterrissage (Estimated Landing Time -ELT ) peutêtre calculé aussi en estimant la durée de l'approcheà

, y a pas besoin de gérer les circuits d'attente ni de recalculer les heures d'approche prévues. Les contrôleurs peuvent recourir au guidage radar pour amener l'aéronef jusqu'à un pointà partir duquel le pilote peut exécuter l'approche finale. Le guidage radar consistè a donner les instructions de cap (direction en degrés dans le plan horizontal), de vitesse et d'altitude nécessaire pour guider l'avion

, Approche intermédiaire : de l'IF au FAF (Final Approach Fix )

, Lesétapes de l'approche initiale et intermédiaire serventà amener l'avion de la frontière de la TMA (précisément d'un IAF) jusqu'à s'aligner selon l'axe final de la piste d'atterrissage (au niveau du FAF). Pour cela, le contrôleur d'approche peut soit demanderà l'avion de suivre une trajectoire d'approche standardisée

, Afin d'aider les avionsà intercepter avec précision l'axe de la piste, un moyen aéroportuaire de radio-navigation, appelé système d'atterrissage aux instruments (Instrument Landing System -ILS ), fournit un plan horizontal et un plan vertical dont l'intersection définit l'axe de descente pour rejoindre correctement la piste

, Approche finale : du FAF au seuil de piste si l'avion finit son atterrissage et sinon du FAFà un point aérien spécifique appelé Missed Approach Point -MAPT

L. , Pendant l'approche finale, l'avion adopte une vitesse qui lui est particulière, appelée la vitesse d'approche, et descend selon les plans donnés par l'ILS jusqu'à une hauteur, dite de décision (Decision Hight -DH).À cette hauteur, le pilote doit décider de poursuivre ou non l'atterrissage. S'il voit le seuil de pisteà cette hauteur, le pilote continue l'atterrissage en posant l'avion. Par contre, si le pilote n'arrive pasà voir le seuil de pisteà cette hauteur, il doit interrompre son atterrissage en remettant les gaz. Dans ce cas, l'approche est appelée approche interrompue (API). D'où un quatrième segment : Approche interrompue : du MAPTà un circuit de remise de gaz

. Quand-le-pilote and . Freiner, La distance nécessaire pour le freinage dépend principalement de la masse de l'avionà l'atterrissage et de l'état de la piste (mouillée ou sèche). L'avion se dirige ensuite vers une bretelle désignée pour gagner une voie de circulation et quitter la piste. En fonction du type et de l'emplacement de la bretelle

S. Ahmed, Two-stage stochastic integer programming : A brief introduction, 2011.

I. Anagnostakis and J. Clarke, Runway operations planning : a twostage solution methodology, Proceedings of the 36th Annual Hawaii International Conference on System Sciences, 2003.

H. Balakrishnan, G. Bala, and . Chandran, Algorithms for scheduling runway operations under constrained position shifting, Operations Research, vol.58, issue.6, pp.1650-1665, 2010.

J. F. Bard, Practical bilevel optimization : Algorithms and applications, volume 30, 2013.

J. E. Beasley, M. Krishnamoorthy, Y. M. Sharaiha, and D. Abramson, Scheduling aircraft landings : The static case, Transportation Science, vol.34, issue.2, pp.180-197, 2000.

C. Beck, P. Prosser, and E. Selensky, Vehicle routing and job shop scheduling : What's the difference ?, Proceedings of the 13th International Conference on Automated Planning and Scheduling, pp.267-276, 2003.

J. F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, vol.4, issue.1, pp.238-252, 1962.

J. A. Bennell, M. Mesgarpour, and C. N. Potts, Airport runway scheduling, vol.4, pp.115-138, 2011.

J. A. Bennell, M. Mesgarpour, and C. N. Potts, Dynamic scheduling of aircraft landings, European Journal of Operational Research, vol.258, issue.1, pp.315-327, 2017.

J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, Julia : A fresh approach to numerical computing, SIAM Review, vol.59, issue.1, pp.65-98, 2017.

R. John, F. Birge, and . Louveaux, Introduction to stochastic programming, Springer Science & Business Media, 2011.

P. Bonami, D. Salvagnin, and A. Tramontani, Implementing automatic Benders decomposition in a modern MIP solver, Integer Programming and Combinatorial Optimization, pp.78-90, 2020.

C. Bosson, M. Xue, and S. Zelinski, Optimizing integrated arrival, departure and surface operations under uncertainty, Proceedings of the 10th USA/Europe ATM Research and Development Seminar, 2015.

C. S. Bosson and D. Sun, Optimization of airport surface operations under uncertainty, Journal of Air Transportation, vol.24, issue.3, pp.84-92, 2016.

D. Briskorn and R. Stolletz, Aircraft landing problems with aircraft classes, Journal of Scheduling, vol.17, issue.1, pp.31-45, 2014.

C. Gregory, H. Carr, F. Erzberger, and . Neuman, Fast-time study of airlineinfluenced arrival sequencing and scheduling, Journal of Guidance, Control, and Dynamics, vol.23, issue.3, pp.526-531, 2000.

G. Bala, H. Chandran, and . Balakrishnan, A dynamic programming algorithm for robust runway scheduling, Proceedings of the 2007 American Control Conference, pp.1161-1166, 2007.

A. Charnes and W. W. Cooper, Deterministic equivalents for optimizing and satisficing under chance constraints, Operations Research, vol.11, issue.1, pp.18-39, 1963.

A. J. Cook and G. Tanner, European airline delay cost reference values, 2015.

T. G. Crainic, M. Hewitt, F. Maggioni, and W. Rei, Partial Benders decomposition strategies for two-stage stochastic integer programs, Canada, 2016.

A. Richard-de-neufville, P. Odoni, T. Belobaba, and . Reynolds, Airport Systems : Planning, Design and Management, 2013.

R. G. Dear, The dynamic scheduling of aircraft in the near terminal area, 1976.

, Traffic Management Advisor, 2016.

A. Faye, A quadratic time algorithm for computing the optimal landing times of a fixed sequence of planes, European Journal of Operational Research, vol.270, pp.1148-1157, 2018.

M. Fischetti and D. Salvagnin, An in-out approach to disjunctive optimization, International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, pp.136-140

. Springer, , 2010.

M. Fischetti, I. Ljubi?, and M. Sinnl, Benders decomposition without separability : A computational study for capacitated facility location problems, European Journal of Operational Research, vol.253, issue.3, pp.557-569, 2016.

M. Fischetti, I. Ljubi?, and M. Sinnl, Redesigning benders decomposition for large-scale facility location, Management Science, vol.63, issue.7, pp.2146-2162, 2016.

M. J. Frankovich, Air traffic flow management at airports : A unified optimization approach, 2012.

C. Michael and . Fu, Handbook of Simulation Optimization, vol.216, 2015.

F. Furini, M. P. Kidd, C. A. Persiani, and P. Toth, Improved rolling horizon approaches to the aircraft sequencing problem, Journal of Scheduling, vol.18, issue.5, pp.435-447, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01273501

J. Garcia, MAESTRO-A metering and spacing tool, Proceedings of the 1990 American Control Conference, pp.502-507, 1990.

E. Garone, J. Determe, and R. Naldi, Generalized traveling salesman problem for carrier-vehicle systems, Journal of Guidance, Control, and Dynamics, vol.37, issue.3, pp.766-774, 2014.

A. Ghoniem, F. Farhadi, and M. Reihaneh, An accelerated branch-and-price algorithm for multiple-runway aircraft sequencing problems, European Journal of Operational Research, vol.246, issue.1, pp.34-43, 2015.

R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. , Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling : A survey, Annals of Discrete Mathematics, vol.5, pp.287-326, 1979.

J. Guepet, Optimisation de la gestion des avions dans un aéroport : affectation aux points de stationnement, routage au sol et ordonnancementà la piste, 2015.

N. Hasevoets and P. Conroy, Arrival Manager -Implementation Guidelines and Lessons Learned, EUROCONTROL, 2010.

A. Heidt, Uncertainty Models for Optimal and Robust ATM Schedules, 2017.

A. Heidt, H. Helmke, and M. Kapolke, Frauke Liers, and Alexander Martin. Robust runway scheduling under uncertain conditions, Journal of Air Transport Management Part A, vol.56, pp.28-37, 2016.

, IBM. Benders Decomposition in CPLEX 12.7.0, at CPLEX School, 2017.

. Ibm and . Ibm, ILOG CPLEX Optimization Studio CPLEX User's Manual Version 12 Release 7, 2017.

. Sesar-ju, Extended Arrival Manager (E-AMAN) Frequently Asked Questions, 2015.

M. Kapolke, N. Fürstenau, and A. Heidt, Pre-tactical optimization of runway utilization under uncertainty, Journal of Air Transport Management Part A, vol.56, pp.48-56, 2016.

M. Kaut, W. Stein, and . Wallace, Evaluation of scenario-generation methods for stochastic programming, Pacific Journal of Optimization, vol.3, issue.2, pp.257-271, 2007.

E. James and . Kelley, The cutting-plane method for solving convex programs, Journal of the Society for Industrial and Applied Mathematics, vol.8, issue.4, pp.703-712, 1960.

A. Khassiba, F. Bastin, S. Cafieri, B. Gendron, and M. Mongeau, Extended aircraft arrival management under uncertainty : A chanceconstrained two-stage mixed-integer programming model, 2018.

A. Khassiba, F. Bastin, and B. Gendron, Extended aircraft arrival management under uncertainty : A computational study, Journal of Air Transportation, vol.27, issue.3, pp.131-143, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02135040

E. Klotz, Automatic Benders Decomposition in CPLEX, 2017.

G. Laporte and F. V. Louveaux, The integer L-shaped method for stochastic integer programs with complete recourse, Operations Research Letters, vol.13, issue.3, pp.133-142, 1993.

H. Lee, Tradeoff evaluation of scheduling algorithms for terminal-area air traffic control, 2008.

H. Lee and H. Balakrishnan, A study of tradeoffs in scheduling terminalarea operations, Proceedings of the IEEE, vol.96, issue.12, pp.2081-2095, 2008.

A. Lieder and R. Stolletz, Scheduling aircraft take-offs and landings on interdependent and heterogeneous runways, Transportation Research Part E, vol.88, pp.167-188, 2016.

A. Lieder, D. Briskorn, and R. Stolletz, A dynamic programming approach for the aircraft landing problem with aircraft classes, European Journal of Operational Research, vol.243, issue.1, pp.61-69, 2015.

L. Thomas, R. T. Magnanti, and . Wong, Accelerating Benders decomposition : Algorithmic enhancement and model selection criteria, Operations Research, vol.29, issue.3, pp.464-484, 1981.

. Bibliographie,

D. Mcdaniel and M. Devine, A modified Benders' partitioning algorithm for mixed integer programming, Management Science, vol.24, issue.3, pp.312-319, 1977.

A. Larry, H. Meyn, and . Erzberger, Airport arrival capacity benefits due to improved scheduling accuracy, Proceedings of the 5th Aviation, Technology Integration and Operations and the 16th Lighter-Than-Air Systems Technology and Balloon Systems Conferences, 2005.

L. Bruce, H. M. Miller, and . Wagner, Chance constrained programming with joint constraints, Operations Research, vol.13, issue.6, pp.930-945, 1965.

C. E. Miller, A. W. Tucker, and R. A. Zemlin, Integer programming formulation of traveling salesman problems, Journal of the ACM, vol.7, issue.4, pp.326-329, 1960.

F. Neuman and H. Erzberger, Analysis of sequencing and scheduling methods for arrival traffic, 1990.

H. Orthogon, Extended AMAN enabling sesar deployment, 2016.

M. L. Pinedo, Scheduling : Theory, algorithms, and systems, 2012.

N. Harilaos and . Psaraftis, A dynamic programming approach to the aircraft sequencing problem, 1978.

R. Rahmaniani, T. G. Crainic, M. Gendreau, and W. Rei, The Benders decomposition algorithm : A literature review, European Journal of Operational Research, vol.259, issue.3, pp.801-817, 2017.

A. Shapiro and T. Mello, On the rate of convergence of optimal solutions of Monte Carlo approximations of stochastic programs, SIAM Journal on Optimization, vol.11, issue.1, pp.70-86, 2000.

A. Shapiro, D. Dentcheva, and A. Ruszczy?ski, Lectures on stochastic programming : Modeling and theory, 2009.

G. Sölveling, Stochastic programming methods for scheduling of airport runway operations under uncertainty, 2012.

G. Sölveling and J. Clarke, Scheduling of airport runway operations using stochastic branch and bound methods, Transportation Research Part C, vol.45, pp.119-137, 2014.

G. Sölveling, S. Solak, J. Clarke, and E. Johnson, Runway operations optimization in the presence of uncertainties, Journal of Guidance, Control, and Dynamics, vol.34, issue.5, pp.1373-1382, 2011.

M. Soomer and G. Franx, Scheduling aircraft landings using airlines' preferences, European Journal of Operational Research, vol.190, issue.1, pp.277-291, 2008.

L. Stell, Prediction of top of descent location for idle-thrust descents, Proceedings of the 9th USA/Europe Air Traffic Management Research and Development Seminar, 2011.

M. Tielrooij, C. Borst, M. Marinus, M. Van-paassen, and . Mulder, Predicting arrival time uncertainty from actual flight information, Proceedings of the 11th USA/Europe Air Traffic Management Research and Development Seminar, pp.577-586, 2015.

R. M. Van-slyke and R. Wets, L-Shaped linear programs with applications to optimal control and stochastic programming, SIAM Journal on Applied Mathematics, vol.17, issue.4, pp.638-663, 1969.

, Arrival planning and sequencing with COMPAS-OP at the Frankfurt ATC-Center, Proceedings of the 1990 American Control Conference, pp.496-501, 1990.

R. D. Wollmer, Two-stage linear programming under uncertainty with 0-1 integer first stage variables, Mathematical Programming, vol.19, issue.1, pp.279-288, 1980.

M. Xue and S. Zelinski, Dynamic stochastic scheduler for integrated arrivals and departures, Proceedings of the 33rd Digital Avionics Systems Conference, 2014.

M. Xue and S. Zelinski, A stochastic scheduler for integrated arrival, departure, and surface operations in Los Angeles, Proceedings of the 15th Aviation Technology, Integration, and Operations Conference, 2015.