Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-07-01T11:43:52Z No. of bitstreams: 1 germandavidyagimoromisato.pdf: 4216499 bytes, checksum: a1b6dec404f94fd91a0a919755636775 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-07-13T16:00:06Z (GMT) No. of bitstreams: 1 germandavidyagimoromisato.pdf: 4216499 bytes, checksum: a1b6dec404f94fd91a0a919755636775 (MD5) / Made available in DSpace on 2016-07-13T16:00:06Z (GMT). No. of bitstreams: 1 germandavidyagimoromisato.pdf: 4216499 bytes, checksum: a1b6dec404f94fd91a0a919755636775 (MD5) Previous issue date: 2012-08-02 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho tem como objetivo apresentar uma nova metodologia baseada em Programação Dinâmica Dual Determinística (PDDD) para o cálculo da Energia Firme de sistemas energéticos. A Energia Firme tem uma relação direta com os certificados de energia garantida atribuídos às usinas hidráulicas, os quais representam o limite superior para os contratos de energia estabelecidos com os consumidores (distribuidores e consumidores livres). Neste contexto, este trabalho possui uma importância relevante para o cenário atual do Setor Elétrico Brasileiro (SEB). Os resultados são comparados com aqueles obtidos pela metodologia em vigor no SEB, o qual é baseado em métodos heurísticos. / The objective of this work is to introduce a new methodology based in The Deterministic Dual Dynamic Programming (DDDP) to calculate the firm energy of energetic systems. The firm energy is directly related to the guaranteed energy certificates assigned to hydraulic power plants. These energy certificates represent the limits of energy contracts that can be established with consumers (energy distributors and free consumers). In this context, this work has a relevant importance to the current scenario of the Brazilian Electric Sector (BES). The results are compared to those obtained by the BES approved computational model based in heuristic methods.

Les réseaux optiques sont aujourd’hui l’élément de base des systèmes de communica- tions modernes, en particulier l’Internet. Grâce au multiplexage en longueurs d’onde et au groupage du tra?c, la bande passante disponible sur une ?bre optique est supérieure à plusieurs térabits par seconde. Cependant les équipements opto-électroniques qui permettent d’opérer ces réseaux sont très coûteux car il doivent fonctionner à un débit très important. Le problème de groupage et du routage d’un ensemble de requêtes couplé avec l’affectation des longueurs d’onde (GRWA) est donc un problème stratégique de première importance. L’objectif est de minimiser le coût du réseau, évalué comme le nombre de ports optiques installés aux nœuds. Il peut être modélisé sous la forme d’un problème d’allocation de ressources dans un réseau à capacité multi-niveaux avec multi-?ots non bifurqués. Cette catégorie de problème est connue pour être très dif?cile compte tenu de la faiblesse de la relaxation linéaire des formulations associées. Les travaux réalisés durant cette thèse ont consisté en le développement de méthodes de résolution pour ce problème à partir de multiples techniques de recherche opéra- tionnelle : méta-heuristique de type recherche avec tabous, décomposition de Dantzig- Wolfe, décomposition de Benders, reformulation en variables binaires, méthode de plans coupants, heuristique d’arrondi. Les méthodes résultantes, dont certaines sont hybrides, permettent d’avoir un aperçu des méthodes ef?caces pour ce type de problème. En partic- ulier, les méthodes basées sur la décomposition de Benders, qui donnent lieu à des procédures d’optimisation hiérarchique dans lesquelles l’affectation de longueurs d’onde est placée au dernier niveau, sont les méthodes les plus ef?caces car elles permettent de séparer le routage optique du routage physique. En?n, nous utilisons la meilleure méthode de résolution pour observer l’impact des contraintes de délais sur la qualité des solutions. / Optical networks are the core element of modern communication systems and in particu- lar Internet. With wavelength multiplexing and grooming capability, terabits per second bandwidth can be reached. However, opto-electronic equipment used to operate these networks are very expensive as their bit rate must be very large. The grooming, routing and wavelength assignment (GRWA) problem, which consists in minimizing the net- work cost, evaluated by the number of required optical ports, while guaranteeing that each request is granted, is of great interest. The GRWA problem can be modeled as a multi-layer capacitated network design problem with non-bifurcated multi-?ows. This type of problem is known to be hard to solve as their linear relaxation is weak. The objective of this work was to develop solution methods based on multiple oper- ations research techniques : Tabu search based meta-heuristic, Dantzig-Wolfe decompo- sition, Benders decomposition, 0 1 reformulation, cutting-planes, rounding heuristic. The resulting solution tools, some of them hybrid, give a perspective on the effective solution approaches for this type of problem. From the experiments, it turns out that the methods based on Benders’ decomposition, which lead to hierarchical optimization procedures, are the most ef?cient as they allow to separate the optical routing from the physical routing with the wavelength assignment decisions taken in the lower stage sub- problem. In addition to the approach comparison, we use the most effective method to evaluate the impact of the delay constraints on the solution quality.

Cotutelle avec l'Université de Toulouse 3 - Paul Sabatier, France. Laboratoire d'accueil: Laboratoire de recherche de l'École Nationale de l'Aviation Civile (ENAC), équipe OPTIM, Toulouse, France. / Dans le contexte d'une augmentation soutenue du trafic aérien et d'une faible marge d'expansion des capacités aéroportuaires, la pression s'accroît sur les aéroports les plus fréquentés pour une utilisation optimale de leur infrastructure, telle que les pistes, reconnues comme le goulot d'étranglement des opérations aériennes. De ce besoin opérationnel est né le problème d'ordonnancement des atterrissages d'avions, consistant à trouver pour les avions se présentant à un aéroport la séquence et les heures d'atterrissage optimales par rapport à certains critères (utilisation des pistes, coût total des retards, etc) tout en respectant des contraintes opérationnelles et de sécurité. En réponse à ce besoin également, depuis les années 1990 aux États-Unis et en Europe, des outils d'aide à la décision ont été mis à la disposition des contrôleurs aériens, afin de les assister dans leur tâche d'assurer la sécurité et surtout la performance des flux d'arrivée. Un certain nombre de travaux de recherche se sont focalisés sur le cas déterministe et statique du problème d'atterrissage d'avions. Cependant, le problème plus réaliste, de nature stochastique et dynamique, a reçu une attention moindre dans la littérature. De plus, dans le cadre du projet européen de modernisation des systèmes de gestion de trafic aérien, il a été proposé d’étendre l’horizon opérationnel des outils d’aide à la décision de manière à prendre en compte les avions plus loin de l'aéroport de destination. Cette extension de l'horizon opérationnel promet une meilleure gestion des flux d'arrivées via un ordonnancement précoce plus efficient. Néanmoins, elle est inévitablement accompagnée d'une détérioration de la qualité des données d'entrée, rendant indispensable la prise en compte de leur stochasticité. L’objectif de cette thèse est l’ordonnancement des arrivées d’avions, dans le cadre d'un horizon opérationnel étendu, où les heures effectives d'arrivée des avions sont incertaines. Plus précisément, nous proposons une approche basée sur la programmation stochastique à deux étapes. En première étape, les avions sont pris en considération à 2-3 heures de leur atterrissage prévu à l'aéroport de destination. Il s'agit de les ordonnancer à un point de l'espace aérien aéroportuaire, appelé IAF (Initial Approach Fix). Les heures effectives de passage à ce point sont supposées suivre des distributions de probabilité connues. En pratique, cette incertitude peut engendrer un risque à la bonne séparation des avions nécessitant l'intervention des contrôleurs. Afin de limiter la charge de contrôle conséquente, nous introduisons des contraintes en probabilité traduisant le niveau de tolérance aux risques de sécurité à l'IAF après révélation de l'incertitude. La deuxième étape correspond au passage effectif des avions considérés à l'IAF. Comme l'incertitude est révélée, une décision de recours est prise afin d'ordonnancer les avions au seuil de piste en minimisant un critère de deuxième étape (charge de travail des contrôleurs, coût du retard, etc). La démonstration de faisabilité et une étude numérique de ce problème d'ordonnancement des arrivées d'avions en présence d'incertitude constituent la première contribution de la thèse. La modélisation de ce problème sous la forme d’un problème de programmation stochastique à deux étapes et sa résolution par décomposition de Benders constituent la deuxième contribution. Finalement, la troisième contribution étend le modèle proposé au cas opérationnel, plus réaliste où nous considérons plusieurs points d’approche initiale. / Airport operations are well known to be a bottleneck in the air traffic system, which puts more and more pressure on the world busiest airports to optimally schedule landings, in particular, and also – but to a smaller extent – departures. The Aircraft Landing Problem (ALP) has arisen from this operational need. ALP consists in finding for aircraft heading to a given airport a landing sequence and landing times so as to optimize some given criteria (optimizing runway utilization, minimizing delays, etc) while satisfying operational constraints (safety constraints mainly). As a reply to this operational need, decision support tools have been designed and put on service for air traffic controllers since the early nineties in the US as well as in Europe. A considerable number of publications dealing with ALP focus on the deterministic and static case. However, the aircraft landing problem arising in practice has a dynamic nature riddled with uncertainties. In addition, operational horizon of current decision support tools are to be extended so that aircraft are captured at larger distances from the airport to hopefully start the scheduling process earlier. Such a horizon extension affects the quality of input data which enlarges the uncertainty effect. In this thesis, we aim at scheduling aircraft arrivals under uncertainty. For that purpose, we propose an approach based on two-stage stochastic programming. In the first stage, aircraft are captured at a large distance from the destination airport. They are to be scheduled on the same initial approach fix (IAF), a reference point in the near-to-airport area where aircraft start their approach phase preparing for landing. Actual IAF arrival times are assumed to be random variables with known probability distributions. In practice, such an uncertainty may cause loss of safety separations between aircraft. In such situations, air traffic controllers are expected to intervene to ensure air traffic safety. In order to alleviate the consequent air traffic control workload, chance constraints are introduced so that the safety risks around the IAF are limited to an acceptable level once the uncertainty is revealed. The second stage corresponds to the situation where aircraft are actually close to the IAF. In this stage, the uncertainty is revealed and a recourse decision is made in order to schedule aircraft on the runway threshold so that a second-stage cost function is minimized (e.g., air traffic control workload, delay cost, etc). Our first contribution is a proof of concept of the extended aircraft arrival management under uncertainty and a computational study on optimization parameters and problem characteristics. Modeling this problem as a two-stage stochastic programming model and solving it by a Benders decomposition is our second contribution. Finally, our third contribution focuses on extending our model to the more realistic case, where aircraft in the first stage are scheduled on several IAFs.

[pt] Este trabalho explora a estrutura de decomposição de um problema de planejamento da expansão da geração hidrotérmica, utilizando uma integração entre uma Decomposição de Benders modificada e um Progressive Hedging. Consideramos uma representação detalhada das restrições cronológicas de curto prazo, com resolução horária, baseando-se em dias típicos para cada etapa. Além disso, representamos a natureza estocástica de uma política operacional hidrotérmica multiestágio por meio de uma Regra de Decisão Linear otimizada, garantindo decisões de investimento compatíveis com uma política operacional não antecipativa. Para resolver este problema de otimização em grande escala, propomos um método de decomposição de Benders aprimorado com várias instâncias do problema mestre, onde cada uma delas é reforçada por cortes primários além dos cortes de Benders gerados a cada candidato a solução do mestre. Nossa nova abordagem permite o uso de termos de penalização de Progressive Hedging para fins de regularização. Mostramos que o algoritmo proposto é 60 porcento mais rápido que os tradicionais e que a consideração de uma política operacional não antecipativa pode economizar, em média, 8.27porcento do custo total em testes fora da amostra. / [en] This paper exploits the decomposition structure of the hydrothermal generation expansion planning problem with an integrated modified Benders Decomposition and Progressive Hedging approach. We consider a detailed representation of hourly chronological short-term constraints based on typical days per month and year. Also, we represent the multistage stochastic nature of the hydrothermal operational policy through an optimized linear decision rule, thereby ensuring investment decisions compatible with a nonanticipative implementable operational policy. To solve the resulting large-scale optimization problem, we propose an improved Benders Decomposition method with multiple instances of the master problem, each of which strengthened by primal cuts and new Benders cuts generated by each master s trial solution. Additionally, our new approach allows using Progressive Hedging penalization terms for regularization purposes. We show that our method is 60 percent faster than the traditional ones and also that the consideration of a nonanticipative operational policy can save, on average, 8.27 percent of the total cost in out-of-sample tests.

Die Erreichung der ehrgeizigen Dekarbonisierungsziele Deutschlands erfordert eine massive Ausweitung der Onshore-Windenergie. In den letzten Jahren sahen sich Onshore-Wind Projektentwickler zunehmend mit sozialen und Umweltbedenken aufgrund von Landnutzungskonflikten konfrontiert. Aus regulatorischer Sicht stellen die weitere Integration von Onshore-Windkapazitäten in das deutsche Energiesystem besondere Herausforderungen in Bezug auf geografische und zeitliche Aspekte der Stromerzeugung dar. Die hohen Windgeschwindigkeiten und die vergleichsweise geringe Bevölkerungsdichte haben dazu geführt, dass Investoren in der Vergangenheit überproportional in den nördlichen Bundesländern Windparks entwickelten. Eine starke gleichzeitige Einspeisung von Strom an nahegelegenen Windstandorten führt jedoch zu einem Druck auf die Großhandelsstrompreise, was die Markterträge der Entwickler reduziert. Diese Arbeit zielt daher darauf ab, einen Beitrag zum zukünftigen Design des deutschen Energiesystems zu leisten und insbesondere den weiteren Ausbau der Onshore-Windenergie in Deutschland unter Berücksichtigung sozialer, Umwelt- und wirtschaftlicher Einschränkungen zu untersuchen. Dabei werden GIS-Software und ein neues inverses Zeitreihenmodellierungsverfahren genutzt, um das Windpotenzial und Landnutzungskonflikte zu analysieren. Zukünftige Marktszenarien werden mit Hilfe eines dekomposierten Kraftwerkseinsatz und -investitionsmodells hinsichtlich ihrer Wirkungen auf die ökonomische Effizienz der Marktintegration von Onshore-Windenergie bewertet, wobei Preisentwicklungen für CO2-Emissionszertifikate eine entscheidende Rolle spielen. Die Ergebnisse deuten auf eine abnehmende Rentabilität der Onshore-Windenergie in Deutschland hin, während der Süden Deutschlands aus ganzheitlicher Perspektive einen größeren Beitrag zur Windenergie leisten könnte.:I Analysis framework 1 1 Introduction 3 1.1 Research motivation . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Research objective, aims and questions . . . . . . . . . . . . . 5 1.3 Scientific contribution . . . . . . . . . . . . . . . . . . . . . . . 7 1.3.1 Research focus specification . . . . . . . . . . . . . . . 7 1.3.2 Contribution regarding renewable energy potentials and levelised generation cost . . . . . . . . . . . . . . . 10 1.3.3 Contribution regarding generic wind time series modelling 12 1.3.4 Contribution regarding electricity market modelling and model decomposition . . . . . . . . . . . . . . . . . 14 1.3.5 Contribution regarding evaluating the market integration of wind energy . . . . . . . . . . . . . . . . . . 17 1.4 Organisation of thesis and software tools applied . . . . . . . 20 2 Basics of electricity economics 23 2.1 Pricing and investments in electricity markets . . . . . . . . . 23 2.1.1 Long-term market equilibrium . . . . . . . . . . . . . . 23 2.1.2 Short-term market equilibrium . . . . . . . . . . . . . . 25 2.2 Interplay of price formation and renewable support . . . . . . 27 2.2.1 Definitions and concepts . . . . . . . . . . . . . . . . . 27 2.2.2 Quantity and price effect of environmental policies and implications for geographic deployment pathways 29 II Regionalisation of data inputs 33 3 GIS-based windenergy potential analysis 35 3.1 Framing the approach . . . . . . . . . . . . . . . . . . . . . . . . 35 3.1.1 Taxonomy of renewable potentials . . . . . . . . . . . 35 3.1.2 GIS-based analysis procedure . . . . . . . . . . . . . . 36 3.1.3 Three-stage sensitivity analysis . . . . . . . . . . . . . 37 3.2 Land assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2.1 Land characteristics . . . . . . . . . . . . . . . . . . . . 37 3.2.2 Results on the land availability . . . . . . . . . . . . . . 41 3.3 Technical potential . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.3.1 Technical wind turbine configuration . . . . . . . . . . 44 3.3.2 Electrical energy conversion . . . . . . . . . . . . . . . 45 3.3.3 Wind-farm design . . . . . . . . . . . . . . . . . . . . . 46 3.3.4 Results on the technical potential . . . . . . . . . . . . 47 3.4 Economic potential . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.4.1 Cost-potential curves at a country level . . . . . . . . 49 3.4.2 Cost-potential curves at a regional level . . . . . . . . 52 4 Generic wind energy feed-in time series 55 4.1 Generic wind speed data in energy systems analysis . . . . . . 55 4.1.1 Motivation of generic time series . . . . . . . . . . . . 55 4.1.2 Incorporation of time series generation into modelling setup . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2 Dynamic adjustment of model size via clustering . . . . . . . 56 4.2.1 Introduction to hierarchical and partitional cluster methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2.2 Euclidean distance as proximity measure . . . . . . . . 57 4.2.3 Linkage of observations and cluster verification . . . 58 4.2.4 Specification of input data and data organisation . . . 59 4.2.5 Results on cluster algorithm selection and representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.3 Vector autoregressive stochastic process with Normal-to- Weibull transformation . . . . . . . . . . . . . . . . . . . . . . . 61 4.3.1 Wind characteristics . . . . . . . . . . . . . . . . . . . . 61 4.3.2 Data description and handling . . . . . . . . . . . . . . 62 4.3.3 Additive modelling procedure . . . . . . . . . . . . . . 63 4.3.4 Standard Normal-to-Weibull transformation . . . . . . 64 4.3.5 Time series decomposition . . . . . . . . . . . . . . . . 67 4.3.6 (V)AR-Parameter estimation . . . . . . . . . . . . . . . 70 4.3.7 Statistical dependence between different locations . . 73 4.3.8 Time series simulation . . . . . . . . . . . . . . . . . . . 75 4.3.9 Results on time series simulation . . . . . . . . . . . . 77 III Market model-based investigation 81 5 Modelling investment decisions in power markets 83 5.1 Motivation for illustration of model decomposition . . . . . . 83 5.2 Simplified market model formulation . . . . . . . . . . . . . . . 83 5.2.1 Power plant dispatch problem . . . . . . . . . . . . . . 83 5.2.2 Capacity expansion extension . . . . . . . . . . . . . . 84 5.2.3 Constraint matrix structure . . . . . . . . . . . . . . . . 85 5.3 Complexity reduction via Benders decomposition . . . . . . . 87 5.3.1 Benders strategies . . . . . . . . . . . . . . . . . . . . . 87 5.3.2 Single-cut procedure . . . . . . . . . . . . . . . . . . . . 88 5.3.3 Multi-cut procedure . . . . . . . . . . . . . . . . . . . . 93 5.4 Acceleration strategies for decomposed market models . . . . 98 5.4.1 Scenario solver . . . . . . . . . . . . . . . . . . . . . . . 98 5.4.2 Distributed computing . . . . . . . . . . . . . . . . . . . 98 5.4.3 Regularisation . . . . . . . . . . . . . . . . . . . . . . . 98 5.5 Numerical testing of model formulation and solving strategy 99 5.5.1 Preliminary remarks . . . . . . . . . . . . . . . . . . . . 99 5.5.2 Effects of multiple cuts . . . . . . . . . . . . . . . . . . 100 5.5.3 Effects of scenario solver and parallelisation . . . . . . 101 5.5.4 Effects of regularisation . . . . . . . . . . . . . . . . . . 103 5.6 Implications for a large-scale application . . . . . . . . . . . . 105 6 ELTRAMOD-dec: A market model tailored for investigating the European electricity markets 107 6.1 Understanding the model design . . . . . . . . . . . . . . . . . 107 6.1.1 Market modelling fundamentals . . . . . . . . . . . . . 107 6.1.2 ELTRAMOD-dec’s model structure and solving conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6.1.3 Central capacity planning assumptions . . . . . . . . . 109 6.1.4 Central market clearing assumptions . . . . . . . . . . 110 6.2 Mathematical formulation of ELTRAMOD-dec . . . . . . . . . 111 6.2.1 Nomenclature . . . . . . . . . . . . . . . . . . . . . . . . 111 6.2.2 Master problem equations . . . . . . . . . . . . . . . . 114 6.2.3 Subproblem equations . . . . . . . . . . . . . . . . . . . 117 6.2.4 Program termination . . . . . . . . . . . . . . . . . . . 123 6.2.5 Research-specific extensions . . . . . . . . . . . . . . . 124 6.3 Data description and model calibration . . . . . . . . . . . . . 126 6.3.1 Base year modelling data . . . . . . . . . . . . . . . . . 126 6.3.2 Model performance validation . . . . . . . . . . . . . . 131 6.3.3 Target year modelling data . . . . . . . . . . . . . . . . 133 6.4 Determination of ELTRAMOD-dec’s solving conventions and tuning parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.4.1 Framing some modelling experiments . . . . . . . . . 137 6.4.2 Effects of regularisation on convergence behaviour . 138 6.4.3 Effects of time slicing on solution accuracy . . . . . . 142 6.4.4 Effects of decomposition on solving speed . . . . . . . 145 7 Model-based investigation of onshore wind deployment pathways in Germany 149 7.1 Scenario framework and key assumptions . . . . . . . . . . . . 149 7.1.1 Scenario creation . . . . . . . . . . . . . . . . . . . . . . 149 7.1.2 Definition of market configuration . . . . . . . . . . . 152 7.1.3 Summary on scenario key assumptions . . . . . . . . . 154 7.2 Results on market integration at a market zone level . . . . . 155 7.2.1 Introducing market integration indicators . . . . . . . 155 7.2.2 Market integration indicators for baseline calculation 156 7.2.3 Market integration indicators for increased renewable uptake calculation . . . . . . . . . . . . . . . . . . 157 7.2.4 Market integration indicators for ultimate renewable uptake calculation . . . . . . . . . . . . . . . . . . . . . 159 7.3 Results on market integration at a detailed regional level . . . 160 7.3.1 Introducing regional market integration indicators . . 160 7.3.2 Regional market integration indicators for baseline calculation . . . . . . . . . . . . . . . . . . . . . . . . . . 161 7.3.3 Regional market integration indicators for increased renewable uptake calculation . . . . . . . . . . . . . . . 163 7.3.4 Regional market integration indicators for ultimate renewable uptake calculation . . . . . . . . . . . . . . . 164 8 Summary and conclusions 169 8.1 Findings regarding the market integration . . . . . . . . . . . . 169 8.1.1 Onshore wind resources constitute a limiting factor for achieving Germany’s energy transition . . . . . . 169 8.1.2 Distribution of wind farm fleet has a strong impact on market premia in the centre and south of Germany 170 8.2 Findings regarding the technical underpinning . . . . . . . . . 173 8.2.1 Generic wind speed velocities can be a powerful tool for power system modellers . . . . . . . . . . . . . . . 173 8.2.2 Decomposition enables efficient solving of large-scale power system investment and dispatch models . . . . 174 8.3 Implications for policymakers . . . . . . . . . . . . . . . . . . . 176 IV Appendix 179 A Additional tables and figures 181 B Code listings 187 Bibliography 199 / Achieving Germany's ambitious decarbonisation goals requires a massive expansion of onshore wind energy. In recent years, onshore wind project developers have increasingly faced social and environmental concerns due to land use conflicts. From a regulatory perspective, further integrating onshore wind capacity into the German energy system poses particular challenges regarding geographical and temporal aspects of electricity generation. High wind speeds and comparatively low population density have led investors to disproportionately develop wind farms in the northern states in the past. However, a strong simultaneous electricity feed-in at nearby wind sites suppresses wholesale electricity prices, reducing developers' market returns. This study aims to contribute to the future design of the German energy system and, in particular, to examine the further expansion of onshore wind energy in Germany, considering social, environmental, and economic constraints. GIS software and a new inverse time series modelling approach are utilised to investigate wind potential and land use conflicts. Future market scenarios are evaluated using a decomposed power plant dispatch and investment model regarding their effects on the economic efficiency of onshore wind energy market integration, with price developments for carbon emission certificates playing a crucial role. The results indicate a decreasing profitability of onshore wind energy in Germany, while from a holistic perspective, southern Germany could make a more significant contribution to wind energy at reasonable increases in support requirements.:I Analysis framework 1 1 Introduction 3 1.1 Research motivation . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Research objective, aims and questions . . . . . . . . . . . . . 5 1.3 Scientific contribution . . . . . . . . . . . . . . . . . . . . . . . 7 1.3.1 Research focus specification . . . . . . . . . . . . . . . 7 1.3.2 Contribution regarding renewable energy potentials and levelised generation cost . . . . . . . . . . . . . . . 10 1.3.3 Contribution regarding generic wind time series modelling 12 1.3.4 Contribution regarding electricity market modelling and model decomposition . . . . . . . . . . . . . . . . . 14 1.3.5 Contribution regarding evaluating the market integration of wind energy . . . . . . . . . . . . . . . . . . 17 1.4 Organisation of thesis and software tools applied . . . . . . . 20 2 Basics of electricity economics 23 2.1 Pricing and investments in electricity markets . . . . . . . . . 23 2.1.1 Long-term market equilibrium . . . . . . . . . . . . . . 23 2.1.2 Short-term market equilibrium . . . . . . . . . . . . . . 25 2.2 Interplay of price formation and renewable support . . . . . . 27 2.2.1 Definitions and concepts . . . . . . . . . . . . . . . . . 27 2.2.2 Quantity and price effect of environmental policies and implications for geographic deployment pathways 29 II Regionalisation of data inputs 33 3 GIS-based windenergy potential analysis 35 3.1 Framing the approach . . . . . . . . . . . . . . . . . . . . . . . . 35 3.1.1 Taxonomy of renewable potentials . . . . . . . . . . . 35 3.1.2 GIS-based analysis procedure . . . . . . . . . . . . . . 36 3.1.3 Three-stage sensitivity analysis . . . . . . . . . . . . . 37 3.2 Land assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2.1 Land characteristics . . . . . . . . . . . . . . . . . . . . 37 3.2.2 Results on the land availability . . . . . . . . . . . . . . 41 3.3 Technical potential . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.3.1 Technical wind turbine configuration . . . . . . . . . . 44 3.3.2 Electrical energy conversion . . . . . . . . . . . . . . . 45 3.3.3 Wind-farm design . . . . . . . . . . . . . . . . . . . . . 46 3.3.4 Results on the technical potential . . . . . . . . . . . . 47 3.4 Economic potential . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.4.1 Cost-potential curves at a country level . . . . . . . . 49 3.4.2 Cost-potential curves at a regional level . . . . . . . . 52 4 Generic wind energy feed-in time series 55 4.1 Generic wind speed data in energy systems analysis . . . . . . 55 4.1.1 Motivation of generic time series . . . . . . . . . . . . 55 4.1.2 Incorporation of time series generation into modelling setup . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2 Dynamic adjustment of model size via clustering . . . . . . . 56 4.2.1 Introduction to hierarchical and partitional cluster methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2.2 Euclidean distance as proximity measure . . . . . . . . 57 4.2.3 Linkage of observations and cluster verification . . . 58 4.2.4 Specification of input data and data organisation . . . 59 4.2.5 Results on cluster algorithm selection and representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.3 Vector autoregressive stochastic process with Normal-to- Weibull transformation . . . . . . . . . . . . . . . . . . . . . . . 61 4.3.1 Wind characteristics . . . . . . . . . . . . . . . . . . . . 61 4.3.2 Data description and handling . . . . . . . . . . . . . . 62 4.3.3 Additive modelling procedure . . . . . . . . . . . . . . 63 4.3.4 Standard Normal-to-Weibull transformation . . . . . . 64 4.3.5 Time series decomposition . . . . . . . . . . . . . . . . 67 4.3.6 (V)AR-Parameter estimation . . . . . . . . . . . . . . . 70 4.3.7 Statistical dependence between different locations . . 73 4.3.8 Time series simulation . . . . . . . . . . . . . . . . . . . 75 4.3.9 Results on time series simulation . . . . . . . . . . . . 77 III Market model-based investigation 81 5 Modelling investment decisions in power markets 83 5.1 Motivation for illustration of model decomposition . . . . . . 83 5.2 Simplified market model formulation . . . . . . . . . . . . . . . 83 5.2.1 Power plant dispatch problem . . . . . . . . . . . . . . 83 5.2.2 Capacity expansion extension . . . . . . . . . . . . . . 84 5.2.3 Constraint matrix structure . . . . . . . . . . . . . . . . 85 5.3 Complexity reduction via Benders decomposition . . . . . . . 87 5.3.1 Benders strategies . . . . . . . . . . . . . . . . . . . . . 87 5.3.2 Single-cut procedure . . . . . . . . . . . . . . . . . . . . 88 5.3.3 Multi-cut procedure . . . . . . . . . . . . . . . . . . . . 93 5.4 Acceleration strategies for decomposed market models . . . . 98 5.4.1 Scenario solver . . . . . . . . . . . . . . . . . . . . . . . 98 5.4.2 Distributed computing . . . . . . . . . . . . . . . . . . . 98 5.4.3 Regularisation . . . . . . . . . . . . . . . . . . . . . . . 98 5.5 Numerical testing of model formulation and solving strategy 99 5.5.1 Preliminary remarks . . . . . . . . . . . . . . . . . . . . 99 5.5.2 Effects of multiple cuts . . . . . . . . . . . . . . . . . . 100 5.5.3 Effects of scenario solver and parallelisation . . . . . . 101 5.5.4 Effects of regularisation . . . . . . . . . . . . . . . . . . 103 5.6 Implications for a large-scale application . . . . . . . . . . . . 105 6 ELTRAMOD-dec: A market model tailored for investigating the European electricity markets 107 6.1 Understanding the model design . . . . . . . . . . . . . . . . . 107 6.1.1 Market modelling fundamentals . . . . . . . . . . . . . 107 6.1.2 ELTRAMOD-dec’s model structure and solving conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6.1.3 Central capacity planning assumptions . . . . . . . . . 109 6.1.4 Central market clearing assumptions . . . . . . . . . . 110 6.2 Mathematical formulation of ELTRAMOD-dec . . . . . . . . . 111 6.2.1 Nomenclature . . . . . . . . . . . . . . . . . . . . . . . . 111 6.2.2 Master problem equations . . . . . . . . . . . . . . . . 114 6.2.3 Subproblem equations . . . . . . . . . . . . . . . . . . . 117 6.2.4 Program termination . . . . . . . . . . . . . . . . . . . 123 6.2.5 Research-specific extensions . . . . . . . . . . . . . . . 124 6.3 Data description and model calibration . . . . . . . . . . . . . 126 6.3.1 Base year modelling data . . . . . . . . . . . . . . . . . 126 6.3.2 Model performance validation . . . . . . . . . . . . . . 131 6.3.3 Target year modelling data . . . . . . . . . . . . . . . . 133 6.4 Determination of ELTRAMOD-dec’s solving conventions and tuning parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.4.1 Framing some modelling experiments . . . . . . . . . 137 6.4.2 Effects of regularisation on convergence behaviour . 138 6.4.3 Effects of time slicing on solution accuracy . . . . . . 142 6.4.4 Effects of decomposition on solving speed . . . . . . . 145 7 Model-based investigation of onshore wind deployment pathways in Germany 149 7.1 Scenario framework and key assumptions . . . . . . . . . . . . 149 7.1.1 Scenario creation . . . . . . . . . . . . . . . . . . . . . . 149 7.1.2 Definition of market configuration . . . . . . . . . . . 152 7.1.3 Summary on scenario key assumptions . . . . . . . . . 154 7.2 Results on market integration at a market zone level . . . . . 155 7.2.1 Introducing market integration indicators . . . . . . . 155 7.2.2 Market integration indicators for baseline calculation 156 7.2.3 Market integration indicators for increased renewable uptake calculation . . . . . . . . . . . . . . . . . . 157 7.2.4 Market integration indicators for ultimate renewable uptake calculation . . . . . . . . . . . . . . . . . . . . . 159 7.3 Results on market integration at a detailed regional level . . . 160 7.3.1 Introducing regional market integration indicators . . 160 7.3.2 Regional market integration indicators for baseline calculation . . . . . . . . . . . . . . . . . . . . . . . . . . 161 7.3.3 Regional market integration indicators for increased renewable uptake calculation . . . . . . . . . . . . . . . 163 7.3.4 Regional market integration indicators for ultimate renewable uptake calculation . . . . . . . . . . . . . . . 164 8 Summary and conclusions 169 8.1 Findings regarding the market integration . . . . . . . . . . . . 169 8.1.1 Onshore wind resources constitute a limiting factor for achieving Germany’s energy transition . . . . . . 169 8.1.2 Distribution of wind farm fleet has a strong impact on market premia in the centre and south of Germany 170 8.2 Findings regarding the technical underpinning . . . . . . . . . 173 8.2.1 Generic wind speed velocities can be a powerful tool for power system modellers . . . . . . . . . . . . . . . 173 8.2.2 Decomposition enables efficient solving of large-scale power system investment and dispatch models . . . . 174 8.3 Implications for policymakers . . . . . . . . . . . . . . . . . . . 176 IV Appendix 179 A Additional tables and figures 181 B Code listings 187 Bibliography 199

The air transportation market has been growing steadily for the past three decades since the airline deregulation in 1978. With competition also becoming more intense, airline companies have been trying to enhance their market shares and profit margins by composing favorable flight schedules and by efficiently allocating their resources of aircraft and crews so as to reduce operational costs. In practice, this is achieved based on demand forecasts and resource availabilities through a structured airline scheduling process that is comprised of four decision stages: schedule planning, fleet assignment, aircraft routing, and crew scheduling. The outputs of this process are flight schedules along with associated assignments of aircraft and crews that maximize the total expected profit. Traditionally, airlines deal with these four operational scheduling stages in a sequential manner. However, there exist obvious interdependencies among these stages so that restrictive solutions from preceding stages are likely to limit the scope of decisions for succeeding stages, thus leading to suboptimal results and even infeasibilities. To overcome this drawback, we first study the aircraft routing problem, and develop some novel modeling foundations based on which we construct and analyze an integrated model that incorporates fleet assignment, aircraft routing, and crew pairing within a single framework. Given a set of flights to be covered by a specific fleet type, the aircraft routing problem (ARP) determines a flight sequence for each individual aircraft in this fleet, while incorporating specific considerations of minimum turn-time and maintenance checks, as well as restrictions on the total accumulated flying time, the total number of takeoffs, and the total number of days between two consecutive maintenance operations. This stage is significant to airline companies as it directly assigns routes and maintenance breaks for each aircraft in service. Most approaches for solving this problem adopt set partitioning formulations that include exponentially many variables, thus requiring the design of specialized column generation or branch-and-price algorithms. In this dissertation, however, we present a novel compact polynomially sized representation for the ARP, which is then linearized and lifted using the Reformulation-Linearization Technique (RLT). The resulting formulation remains polynomial in size, and we show that it can be solved very efficiently by commercial software without complicated algorithmic implementations. Our numerical experiments using real data obtained from United Airlines demonstrate significant savings in computational effort; for example, for a daily network involving 344 flights, our approach required only about 10 CPU seconds for deriving an optimal solution. We next extend Model ARP to incorporate its preceding and succeeding decision stages, i.e., fleet assignment and crew pairing, within an integrated framework. We formulate a suitable representation for the integrated fleeting, routing, and crew pairing problem (FRC), which accommodates a set of fleet types in a compact manner similar to that used for constructing the aforementioned aircraft routing model, and we generate eligible crew pairings on-the-fly within a set partitioning framework. Furthermore, to better represent industrial practice, we incorporate itinerary-based passenger demands for different fare-classes. The large size of the resulting model obviates a direct solution using off-the-shelf software; hence, we design a solution approach based on Benders decomposition and column generation using several acceleration techniques along with a branch-and-price heuristic for effectively deriving a solution to this model. In order to demonstrate the efficacy of the proposed model and solution approach and to provide insights for the airline industry, we generated several test instances using historical data obtained from United Airlines. Computational results reveal that the massively-sized integrated model can be effectively solved in reasonable times ranging from several minutes to about ten hours, depending on the size and structure of the instance. Moreover, our benchmark results demonstrate an average of 2.73% improvement in total profit (which translates to about 43 million dollars per year) over a partially integrated approach that combines the fleeting and routing decisions, but solves the crew pairing problem sequentially. This improvement is observed to accrue due to the fact that the fully integrated model effectively explores alternative fleet assignment decisions that better utilize available resources and yield significantly lower crew costs. / Ph. D.

This dissertation focuses on selected issues in regard to the mathematical modeling of electricity markets. In a first step the interrelations of electric power market modeling are highlighted a crossroad between operations research, applied economics, and engineering. In a second step the development of a large-scale continental European economic engineering model named ELMOD is described and the model is applied to the issue of wind integration. It is concluded that enabling the integration of low-carbon technologies appears feasible for wind energy. In a third step algorithmic work is carried out regarding a game theoretic model. Two approaches in order to solve a discretely-constrained mathematical program with equilibrium constraints using disjunctive constraints are presented. The first one reformulates the problem as a mixed-integer linear program and the second one applies the Benders decomposition technique. Selected numerical results are reported.

[pt] Portfólios de fontes renováveis de energia elétrica são mecanismos de gerenciamento de risco interessantes para comercialização de energia em mercados de negociação bilateral. Quando formados por agentes que pertencem a diferentes companhias sua estabilidade depende da maneira com que os benefícios de mitigação de risco gerados pelo portfólio são alocados individualmente entre os participantes. O problema de se encontrar uma solução estável pode ser matematicamente formulado através da busca de um vetor de alocação de quotas que pertença ao núcleo do jogo cooperativo, que por sua vez pode ser formulado como um conjunto de restrições lineares que aumenta exponencialmente com o número de participantes. Adicionalmente, o lado direito de cada restrição que define o núcleo do jogo cooperativo define o valor de uma determinada coalisão que, no presente trabalho, é obtido através de um modelo de otimização estocástica de dois estágios. Este trabalho compara diferentes metodologias computacionalmente eficientes baseadas em programação linear inteira mista e na técnica de decomposição de Benders para encontrar vetores de alocação de quotas que pertençam ao núcleo de portfólios de larga escala de geradores de energia renovável. São apresentados estudos de casos que utilizam dados reais do sistema elétrico brasileiro. / [en] Portfolios of renewable electricity sources are interesting risk-management mechanisms for trading in electricity contract markets. When they are formed by players belonging to different companies, their stability relies on the way the riskmitigation benefit generated by the optimal portfolio is allocated through individual participants. The problem of reaching a stable allocation can be mathematically formulated in terms of finding a quota-sharing vector belonging to the Core of a cooperative game, which can be formulated as a set of linear constraints that exponentially grows with the number of participants. Moreover, the right-hand-side of each constraint defining the Core relies on a given coalition value which, in the present work, is obtained by a two-stage stochastic optimization model. This work presents and compares efficient methodologies mainly based on mixed integer linear programming and Benders decomposition to find quota allocation vectors that belongs to the Core of large-scale renewable energy portfolios. Case studies are presented with realistic data from the Brazilian power system.

[pt] Recentes apagões em todo o mundo fazem da confiabilidade de sistemas de potência, no tocante a contingências múltiplas, um tema de pesquisa mundial. Dentro desse contexo, se faz importante investigar métodos eficientes de proteger o sistema contra falhas de alguns de seus componentes, sejam elas dependentes e/ou independentes de outras falhas. Nesse sentido, se tornou crucial a incorporação de critérios de segurança mais rigorosos na operação e planejamento de sistemas de potência. Contingências múltiplas são mais comuns e desastrosas do que falhas naturais e independentes. A principal razão para isso reside na complexidade da estabilidade dinâmica de sistemas de potência. Além disso, o sistema de proteção que opera em paralelo ao sistema de distribuição não é livre de falhas. Portanto, interrupções naturais podem causar contingências em cascata em decorrência do mau funcionamento de mecanismos de proteção ou da instabilidade do sistema elétrico como um todo. Nesse contexto, se dá a motivação pela busca de critérios de segurança mais severos como, por exemplo, o n - K, onde K pode ser maior do que 2. Nesse trabalho, o principal objetivo é incorporar o crtitério de segurança geral n-K para geração e transmissão em modelos de operação e planejamento de sistemas de potência. Além de interrupções em geradores, restrições de rede, bem como falhas em linhas de transmiss˜ao também são modeladas. Esse avanço leva a novos desafios computacionais, para os quais formulamos metodologias de solução eficientes baseadas em decomposição de Benders. Considerando operação, duas abordagens são apresentadas. A primeira propõe um modelo de otimização trinível para decidir o despacho ótimo de energia e reservas sob um critério de segurançaa n - K. Nessa abordagem, a alta dimensionalidade do problema, por contemplar restrições de rede, bem como falhas de geradores e de linhas de transmissão, é contornada por meio da implícita consideração do conjunto de possíveis contingências. No mesmo contexto, a segunda abordagem leva em conta a incerteza da carga a ser suprida e a correlação entre demandas de diferentes barras. Considerando planejamento de expansão da transmissão, outro modelo de otimização trinível é apresentado no intuito de decidir quais linhas de transmissão, dentro de um conjunto de candidatas, devem ser construídas para atender a um critério de segurança n - K e, consequentemente, aumentar a confiabilidade do sistema como um todo. Portanto, as principais contribuições do presente trabalho são as seguintes: 1) modelos de otimização trinível para considerar o critério de segurança n - K em operação e planejamento de sistemas de potência, 2) consideração implícita de todo o conjunto de contingências por meio de uma abordagem de otimização robusta ajustável, 3) otimização conjunta de energia e reserva para operação de sistemas de potência, considerando restrições de rede e garantindo a entregabilidade das reservas em todos os estados pós-contingência considerados, 4) metodologias de solução eficientes baseadas em decomposição de Benders que convergem em passos finitos para o ótimo global e 5) desenvolvimento de restrições válidas que alavancam a eficiência computacional. Estudos de caso ressaltam a eficácia das metodologias propostas em capturar os efeitos econômicos de demanda nodal correlacionada sob um critério de segurançaa n - 1, em reduzir o esfor¸co computacional para considerar os critérios de seguran¸ca convencionais n-1 e n-2 e em considerar critérios de segurança mais rigorosos do que o n - 2, um problema intratável até então. / [en] Recent major blackouts all over the world have been a driving force to make power system reliability, regarding multiple contingencies, a subject of worldwide research. Within this context, it is important to investigate efficient methods of protecting the system against dependent and/or independent failures. In this sense, the incorporation of tighter security criteria in power systems operation and planning became crucial. Multiple contingencies are more common and dangerous than natural independent faults. The main reason for this lies in the complexity of the dynamic stability of power systems. In addition, the protection system, that operates in parallel to the supply system, is not free of failures. Thus, natural faults can cause subsequent contingencies (dependent on earlier contingencies) due to the malfunction of the protection mechanisms or the instability of the overall system. These facts drive the search for more stringent safety criteria, for example, n - K, where K can be greater than 2. In the present work, the main objective is to incorporate the joint generation and transmission general security criteria in power systems operation and planning models. Here, in addition to generators outages, network constraints and transmission lines failures are also accounted for. Such improvement leads to new computational challenges, for which we design efficient solution methodologies based on Benders decomposition. Regarding operation, two approaches are presented. The first one proposes a trilevel optimization model to decide the optimal scheduling of energy and reserve under an n - K security criterion. In such approach, the high dimensionality curse of considering network constraints as well as outages of generators and transmission assets is withstood by implicitly taking into account the set of possible contingencies. The second approach includes correlated nodal demand uncertainty in the same framework. Regarding transmission expansion planning, another trilevel optimization model is proposed to decide which transmission assets should be built within a set of candidates in order to meet an n - K security criterion, and, consequently, boost the power system reliability. Therefore, the main contributions of this work are the following: 1) trilevel models to consider general n - K security criteria in power systems operation and planning, 2) implicit consideration of the whole contingency set by means of an adjustable robust optimization approach, 3) co-optimization of energy and reserves for power systems operation, regarding network constraints and ensuring the deliverability of reserves in all considered post-contingency states, 4) efficient solution methodologies based on Benders decomposition that finitely converges to the global optimal solution, and 5) development of valid constraints to boost computational efficiency. Case studies highlight the effectiveness of the proposed methodologies in capturing the economic effect of nodal demand correlation on power system operation under an n - 1 security criterion, in reducing the computational effort to consider conventional n-1 and n-2 security criteria, and in considering security criteria tighter than n - 2, an intractable problem heretofore.

Dans cette thèse, nous étudions le problème d’optimisation des effectifs dans les centres d’appels, dans lequel nous visons à minimiser les coûts d’exploitation tout en offrant aux clients une qualité de service (QoS) élevée. Nous introduisons également l'utilisation de contraintes probabilistes qui exigent que la qualité de service soit satisfaite avec une probabilité donnée. Ces contraintes sont adéquates dans le cas où la performance est mesurée sur un court intervalle de temps, car les mesures de QoS sont des variables aléatoires sur une période donnée. Les problèmes de personnel proposés sont difficiles en raison de l'absence de forme analytique pour les contraintes probabilistes et doivent être approximées par simulation. En outre, les fonctions QoS sont généralement non linéaires et non convexes. Nous considérons les problèmes d’affectation personnel dans différents contextes et étudions les modèles proposés tant du point de vue théorique que pratique. Les méthodologies développées sont générales, en ce sens qu'elles peuvent être adaptées et appliquées à d'autres problèmes de décision dans les systèmes de files d'attente. La thèse comprend trois articles traitant de différents défis en matière de modélisation et de résolution de problèmes d'optimisation d’affectation personnel dans les centres d'appels à compétences multiples. Les premier et deuxième article concernent un problème d'optimisation d'affectation de personnel en deux étapes sous l'incertitude. Alors que dans le second, nous étudions un modèle général de programmation stochastique discrète en deux étapes pour fournir une garantie théorique de la consistance de l'approximation par moyenne échantillonnale (SAA) lorsque la taille des échantillons tend vers l'infini, le troisième applique l'approche du SAA pour résoudre le problème d’optimisation d'affectation de personnel en deux étapes avec les taux d’arrivée incertain. Les deux articles indiquent la viabilité de l'approche SAA dans notre contexte, tant du point de vue théorique que pratique. Pour être plus précis, dans le premier article, nous considérons un problème stochastique discret général en deux étapes avec des contraintes en espérance. Nous formulons un problème SAA avec échantillonnage imbriqué et nous montrons que, sous certaines hypothèses satisfaites dans les exemples de centres d'appels, il est possible d'obtenir les solutions optimales du problème initial en résolvant son SAA avec des échantillons suffisamment grands. De plus, nous montrons que la probabilité que la solution optimale du problème de l’échantillon soit une solution optimale du problème initial tend vers un de manière exponentielle au fur et à mesure que nous augmentons la taille des échantillons. Ces résultats théoriques sont importants, non seulement pour les applications de centre d'appels, mais également pour d'autres problèmes de prise de décision avec des variables de décision discrètes. Le deuxième article concerne les méthodes de résolution d'un problème d'affectation en personnel en deux étapes sous incertitude du taux d'arrivée. Le problème SAA étant coûteux à résoudre lorsque le nombre de scénarios est important. En effet, pour chaque scénario, il est nécessaire d'effectuer une simulation pour estimer les contraintes de QoS. Nous développons un algorithme combinant simulation, génération de coupes, renforcement de coupes et décomposition de Benders pour résoudre le problème SAA. Nous montrons l'efficacité de l'approche, en particulier lorsque le nombre de scénarios est grand. Dans le dernier article, nous examinons les problèmes de contraintes en probabilité sur les mesures de niveau de service. Notre méthodologie proposée dans cet article est motivée par le fait que les fonctions de QoS affichent généralement des courbes en S et peuvent être bien approximées par des fonctions sigmoïdes appropriées. Sur la base de cette idée, nous avons développé une nouvelle approche combinant la régression non linéaire, la simulation et la recherche locale par région de confiance pour résoudre efficacement les problèmes de personnel à grande échelle de manière viable. L’avantage principal de cette approche est que la procédure d’optimisation peut être formulée comme une séquence de simulations et de résolutions de problèmes de programmation linéaire. Les résultats numériques basés sur des exemples réels de centres d'appels montrent l'efficacité pratique de notre approche. Les méthodologies développées dans cette thèse peuvent être appliquées dans de nombreux autres contextes, par exemple les problèmes de personnel et de planification dans d'autres systèmes basés sur des files d'attente avec d'autres types de contraintes de QoS. Celles-ci soulèvent également plusieurs axes de recherche qu'il pourrait être intéressant d'étudier. Par exemple, une approche de regroupement de scénarios pour atténuer le coût des modèles d'affectation en deux étapes, ou une version d'optimisation robuste en distribution pour mieux gérer l'incertitude des données. / In this thesis, we study the staffing optimization problem in multiskill call centers, in which we aim at minimizing the operating cost while delivering a high quality of service (QoS) to customers. We also introduce the use of chance constraints which require that the QoSs are met with a given probability. These constraints are adequate in the case when the performance is measured over a short time interval as QoS measures are random variables in a given time period. The proposed staffing problems are challenging in the sense that the stochastic constraints have no-closed forms and need to be approximated by simulation. In addition, the QoS functions are typically non-linear and non-convex. We consider staffing optimization problems in different settings and study the proposed models in both theoretical and practical aspects. The methodologies developed are general, in the sense that they can be adapted and applied to other staffing/scheduling problems in queuing-based systems. The thesis consists of three articles dealing with different challenges in modeling and solving staffing optimization problems in multiskill call centers. The first and second articles concern a two-stage staffing optimization problem under uncertainty. While in the first one, we study a general two-stage discrete stochastic programming model to provide a theoretical guarantee for the consistency of the sample average approximation (SAA) when the sample sizes go to infinity, the second one applies the SAA approach to solve the two-stage staffing optimization problem under arrival rate uncertainty. Both papers indicate the viability of the SAA approach in our context, in both theoretical and practical aspects. To be more precise, in the first article, we consider a general two-stage discrete stochastic problem with expected value constraints. We formulate its SAA with nested sampling. We show that under some assumptions that hold in call center examples, one can obtain the optimal solutions of the original problem by solving its SAA with large enough sample sizes. Moreover, we show that the probability that the optimal solution of the sample problem is an optimal solution of the original problem, approaches one exponentially fast as we increase the sample sizes. These theoretical findings are important, not only for call center applications, but also for other decision-making problems with discrete decision variables. The second article concerns solution methods to solve a two-stage staffing problem under arrival rate uncertainty. It is motivated by the fact that the SAA version of the two-stage staffing problem becomes expensive to solve with a large number of scenarios, as for each scenario, one needs to use simulation to approximate the QoS constraints. We develop an algorithm that combines simulation, cut generation, cut strengthening and Benders decomposition to solve the SAA problem. We show the efficiency of the approach, especially when the number of scenarios is large. In the last article, we consider problems with chance constraints on the service level measures. Our methodology proposed in this article is motivated by the fact that the QoS functions generally display ``S-shape'' curves and might be well approximated by appropriate sigmoid functions. Based on this idea, we develop a novel approach that combines non-linear regression, simulation and trust region local search to efficiently solve large-scale staffing problems in a viable way. The main advantage of the approach is that the optimization procedure can be formulated as a sequence of steps of performing simulation and solving linear programming models. Numerical results based on real-life call center examples show the practical viability of our approach. The methodologies developed in this thesis can be applied in many other settings, e.g., staffing and scheduling problems in other queuing-based systems with other types of QoS constraints. These also raise several research directions that might be interesting to investigate. For examples, a clustering approach to mitigate the expensiveness of the two-stage staffing models, or a distributionally robust optimization version to better deal with data uncertainty.