This dissertation studies models for locating facilities in time varying demand environments. We describe the characteristics of the time varying demand that motivate the analysis of our location models in terms of total demand and the change in value and location of the demand of each customer. The first part of the dissertation is devoted to the dynamic location model, which determines the optimal time and location for establishing capacitated facilities when demand and cost parameters are time varying. This model minimizes the total cost over a discrete and finite time horizon for establishing, operating, and closing facilities, including the transportation costs for shipping demand from facilities to customers. The model is solved using Lagrangian relaxation and Benders? decomposition. Computational results from different time varying total demand structures demonstrate, empirically, the performance of these solution methods. The second part of the dissertation studies two location models where relocation of facilities is not allowed and the objective is to determine the optimal location of capacitated facilities that will have a good performance when demand and cost parameters are time varying. The first model minimizes the total cost for opening and operating facilities and the associated transportation costs when demand and cost parameters are time varying. The model is solved using Benders? decomposition. We show that in the presence of high relocation costs of facilities (opening and closing costs), this model can be solved as a special case by the dynamic location model. The second model minimizes the maximum regret or opportunity loss between a robust configuration of facilities and the optimal configuration for each time period. We implement local search and simulated annealing metaheuristics to efficiently obtain near optimal solutions for this model.

Nowadays, power systems are dealing with some new challenges raisedby the major changes that have been taken place since 80’s, e.g., deregu-lation in electricity markets, significant increase of electricity demands andmore recently large-scale integration of renewable energy resources such aswind power. Therefore, system operators must make some adjustments toaccommodate these changes into the future of power systems.One of the main challenges is maintaining the system stability since theextra stress caused by the above changes reduces the stability margin, andmay lead to rise of many undesirable phenomena. The other important chal-lenge is to cope with uncertainty and variability of renewable energy sourceswhich make power systems to become more stochastic in nature, and lesscontrollable.Flexible AC Transmission Systems (FACTS) have emerged as a solutionto help power systems with these new challenges. This thesis aims to ap-propriately utilize such devices in order to increase the transmission capacityand flexibility, improve the dynamic behavior of power systems and integratemore renewable energy into the system. To this end, the most appropriatelocations and settings of these controllable devices need to be determined.This thesis mainly looks at (i) rotor angle stability, i.e., small signal andtransient stability (ii) system operation under wind uncertainty. In the firstpart of this thesis, trajectory sensitivity analysis is used to determine themost suitable placement of FACTS devices for improving rotor angle sta-bility, while in the second part, optimal settings of such devices are foundto maximize the level of wind power integration. As a general conclusion,it was demonstrated that FACTS devices, installed in proper locations andtuned appropriately, are effective means to enhance the system stability andto handle wind uncertainty.The last objective of this thesis work is to propose an efficient solutionapproach based on Benders’ decomposition to solve a network-constrained acunit commitment problem in a wind-integrated power system. The numericalresults show validity, accuracy and efficiency of the proposed approach. / <p>The Doctoral Degrees issued upon completion of the programme are issued by Comillas Pontifical University, Delft University of Technology and KTH Royal Institute of Technology. The invested degrees are official in Spain, the Netherlands and Sweden, respectively.QC 20141028</p>

[pt] Esta tese de doutorado é composta de dois artigos científicos com contribuições na área de Smart Grid. Além disso, a tese também contribui para o desenvolvimento de soluções computacionais eficientes para problemas de programação linear mista e inteira. Outra importante contribuição é o desenvolvimento de método de decomposição benders com segundo estágio inteiro e não convexo aplicado ao problema de Transmission Switching. O primeiro artigo científico mostra os benefícios com o advento de uma rede inteligente e o aumento da capacidade do operador do sistema de energia elétrica em tomar ações corretivas em face de ocorrências de contingências. O artigo também analisa consequências práticas na capacidade de self-healing da rede pós-contingência. Em nosso contexto, uma rede self-healing é uma rede com total flexibilidade para ajustar a geração e as linhas de transmissão antes e depois da ocorrência de alguma contingência. Resultados numéricos mostram significantes reduções no corte de carga para cada contingência e no total. Foi considerado um único período que representa a demanda de pico do sistema, comparou-se o novo método com os utilizados em publicações anteriores. O segundo artigo contribui também para a aplicação da tecnologia de Smart Grid, em particular a teoria de Transmission Switching. De fato, desenvolvemos uma estratégia de solução para lidar com a complexibilidade NP-Hard criada pelas variáveis de transmission switching e unit commitment do problema de otimização. Foi desenvolvida uma solução algorítmica baseada na teoria dos grafos. Estudou-se a estrutura topológica desses problemas. Além disso, a maior contribuição foi o desenvolvimento de um novo método de decomposição de benders aplicado para o problema de transmission switching com o segundo estágio inteiro e não convexo. Para lidar com este problema de não convexidade, foi desenvolvido um método de convexificação sequencial, implícito a decomposição de benders. / [en] This PhD Thesis is composed by two papers with contributions on operations research applied to smart grid theory. The first paper highlights the economic and security benefits of an enhanced system operation with the advent of a smart grid technology by introducing a novel model, which is a joint energy and reserve scheduling that incorporates the network capability to switch transmission lines as a corrective action to enhance the system capability to circumvent contingency events. The main goal is to reduce operating costs and electric power outages, by adjusting the network connectivity when a contingency occurs. In such a framework, results show that, with a limited number of corrective switches, the system operator is able to circumvent a wider range of contingencies, while resulting in lower operational costs and reserve levels. In our context, a grid that is capable to adjust its generation and also its topology through post-contingency line switching is called a self-healing grid, and its importance in network security and operating costs is demonstrated in this work. The graph structure is explored in the algorithmic solution of the post-contingency transmission switching problem. Numerical results demonstrate a significant reduction in total load shedding and operating cost. It has been also illustrated an expressive improvement in terms of security and operating cost, in comparison to the transmission switching models previously published. The second paper is an application of a modified Benders decomposition to the post-contingency transmission switching problem. The decomposition is an attempt to deal with the NP-hard optimization problem created by the transmission switching and unit commitment variables. The major contribution is the application of a new benders decomposition approach to the problem of transmission switching, in which the first and second stages problems are a mixed-integer program. To deal with this issue, it is used a Branch and Bound (B&B) procedure for the first-stage problem and a sequential convexification procedure for the second-stage problem.

No description available.

Les méthodes de décomposition sont une application du concept de diviser pour régner en optimisation. L'idée est de décomposer un problème d'optimisation donné en une séquence de sous-problèmes plus faciles à résoudre. Bien que ces méthodes soient les meilleures pour un grand nombre de problèmes de recherche opérationnelle, leur application à des problèmes réels de grande taille présente encore de nombreux défis. Cette thèse propose des améliorations méthodologiques et algorithmiques de méthodes de décomposition. Notre approche est basée sur l'analyse convexe et l'optimisation non-différentiable. Dans la décomposition par les contraintes (ou relaxation lagrangienne) du problème de planification de production électrique, même les sous-problèmes sont trop difficiles pour être résolus exactement. Mais des solutions approchées résultent en des prix instables et chahutés. Nous présentons un moyen simple d'améliorer la structure des prix en pénalisant leurs oscillations, en utilisant en particulier une régularisation par variation totale. La consistance de notre approche est illustrée sur des problèmes d'EDF. Nous considérons ensuite la décomposition par les variables (ou de Benders) qui peut avoir une convergence excessivement lente. Avec un point de vue d'optimisation non-différentiable, nous nous concentrons sur l'instabilité de l'algorithme de plans sécants sous-jacent à la méthode. Nous proposons une stabilisation quadratique de l'algorithme de Benders, inspirée par les méthodes de faisceaux en optimisation convexe. L'accélération résultant de cette stabilisation est illustrée sur des problèmes de conception de réseau et de localisation de plates-formes de correspondance (hubs). Nous nous intéressons aussi plus généralement aux problèmes d'optimisation convexe non-différentiable dont l'objectif est coûteux à évaluer. C'est en particulier une situation courante dans les procédures de décomposition. Nous montrons qu'il existe souvent des informations supplémentaires sur le problème, faciles à obtenir mais avec une précision inconnue, qui ne sont pas utilisées dans les algorithmes. Nous proposons un moyen d'incorporer ces informations incontrôlées dans des méthodes classiques d'optimisation convexe non-différentiable. Cette approche est appliquée avec succès à desproblèmes d'optimisation stochastique. Finalement, nous introduisons une stratégie de décomposition pour un problème de réaffectation de machines. Cette décomposition mène à une nouvelle variante de problèmes de conditionnement vectoriel (vectorbin packing) où les boîtes sont de taille variable. Nous proposons des heuristiques efficaces pour ce problème, qui améliorent les résultats de l'état de l'art du conditionnement vectoriel. Une adaptation de ces heuristiques permet de construire des solutions réalisables au problème de réaffectation de machines de Google. / Decomposition methods are an application of the divide and conquer principle to large-scale optimization. Their idea is to decompose a given optimization problem into a sequence of easier subproblems. Although successful for many applications, these methods still present challenges. In this thesis, we propose methodological and algorithmic improvements of decomposition methods and illustrate them on several operations research problems. Our approach heavily relies on convex analysis and nonsmooth optimization. In constraint decomposition (or Lagrangian relaxation) applied to short-term electricity generation management, even the subproblems are too difficult to solve exactly. When solved approximately though, the obtained prices show an unstable noisy behaviour. We present a simple way to improve the structure of the prices by penalizing their noisy behaviour, in particular using a total variation regularization. We illustrate the consistency of our regularization on real-life problems from EDF. We then consider variable decomposition (or Benders decomposition), that can have a very slow convergence. With a nonsmooth optimization point of view on this method, we address the instability of Benders cutting-planes algorithm. We present an algorithmic stabilization inspired by bundle methods for convex optimization. The acceleration provided by this stabilization is illustrated on network design andhub location problems. We also study more general convex nonsmooth problems whose objective function is expensive to evaluate. This situation typically arises in decomposition methods. We show that it often exists extra information about the problem, cheap but with unknown accuracy, that is not used by the algorithms. We propose a way to incorporate this coarseinformation into classical nonsmooth optimization algorithms and apply it successfully to two-stage stochastic problems.Finally, we introduce a decomposition strategy for the machine reassignment problem. This decomposition leads to a new variant of vector bin packing problems, where the bins have variable sizes. We propose fast and efficient heuristics for this problem that improve on state of the art results of vector bin packing problems. An adaptation of these heuristics is also able to generate feasible solutions for Google instances of the machine reassignment problem.

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