Optimization Models in WindFarm Design: The case of a routing-location problem

Optimization Models in WindFarm Design: The case of a routing-location problem Author: Demetra Orthodoxou MSc Research report Universidad de M´alaga in co-operation with Wageningen University Computer Architecture and Operations Research and Logistics Grant TIN2015-66680-c2-2-R from the Spanish state in part financed by the European Regional Development Fund (ERDF) Supervisors: Dr. E.M.T. Hendrix and Dr.G.D.H Claassen May 3, 2016 Abstract Wind energy can lead to a great socio-economic impact in Europe nowadays, while the installed capacity of wind power is estimated to be double by 2030. Therefore, it has gained more attention lately. In order to generate power from the wind, it is needed to have a set of wind turbines which is known as wind farm. The wind turbines have to be connected via cables into a power grid and the generated power is collected at the main power station. Simultaneously, wind farm researchers need to exploit supercomputers, by having the ultimate aim of developing accurate models. Computational models on wind farm design vary in the existing literature and they have been developed by engineers and scientists with different backgrounds in order to meet the requirements. This thesis report investigates the contribution of operations research scientists associated to these mathematical models. A more precise examination goes through a selected Integer Linear Model which aims to minimize the cabling costs of offshore farms. The model follows the capacitated minimum spanning tree structure, which allows branching and prevents crossing paths. The existing model has been modified in order to understand the complexity while more constraints are taken into account. Besides the fact to satisfy the objective of optimizing the cable routing, a sub-problem arose to facilitate the model by relaxing the planarity constraint. The addition of a node in the existing grid has been proven to be beneficial for specific cases, taking into account the fixed costs arising from the installation and maintenance. Contents 1 Introduction 3 1.1 Background............................ 4 1.2 Research Questions . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 General Research Questions . . . . . . . . . . . . . . . 5 1.2.2 Specific Research Questions . . . . . . . . . . . . . . . 5 1.3 What the Reader can Expect . . . . . . . . . . . . . . . . . . 7 1.4 Existing Literature . . . . . . . . . . . . . . . . . . . . . . . . 7 2 The Model 10 2.1 OriginalModel .......................... 10 2.2 ModifiedModel.......................... 13 2.2.1 Missing constraints . . . . . . . . . . . . . . . . . . . . 17 2.2.2 Numerical Examples . . . . . . . . . . . . . . . . . . . 19 2.3 Conclusion ............................ 22 3 Additional node 23 3.1 Analytical examination . . . . . . . . . . . . . . . . . . . . . . 24 3.1.1 Symmetric case-2 wind turbines . . . . . . . . . . . . . 24 3.1.2 Non-Symmetric case-2 wind turbines . . . . . . . . . . 29 3.1.3 Semi-Symmetric case-3 wind turbines . . . . . . . . . 32 3.1.4 Symmetric case-4 wind turbines . . . . . . . . . . . . . 36 3.2 More: Crossing Routes . . . . . . . . . . . . . . . . . . . . . . 38 3.3 UpdatedModel.......................... 39 4 Discussion 41 4.1 Conclusion ............................ 42 4.2 FurtherResearch......................... 44 Appendix A Additional Knowledge 46 A.1 Combinatorial optimization . . . . . . . . . . . . . . . . . . . 46 A.2 BranchandBound........................ 46 A.3 Minimum Spanning Tree . . . . . . . . . . . . . . . . . . . . . 47 A.4 WeberProblem.......................... 47 A.5 Voronoidiagram ......................... 47 1 Appendix B GAMS modelling 48 B.1 MyGAMSModel......................... 48 B.2 WeberProblem.......................... 51 B.3 My GAMS Model-The additional node . . . . . . . . . . . . 52 2 Chapter 1 Introduction ”The best way to predict your future is to create it”(Covey S.) Fashion always comes and goes, what really remains untouched is the meeting of needs. Thanks to latter generations and the consequences of their reckless actions concerning the planet safety, it seems that the current generation has realized the importance of being proactive and ensuring their future. A perpetual desire for saving costs, has lately forced people to seek creative ways to achieve it without harming the nature. So, the anxiety is decreasing when we realize the connection between economic growth and natural resources from earth. The fastest renewable energy production is wind energy and it is a key for social well-being and a source for cost reductions. The real challenge, that intrigues many researchers to innovate and exchange ideas, is how to balance this usage in a social, economic and environmental way by the pursuit of a common ideal. And this is how a trend of lifestyle, sustainability has started spreading over the world. Apparently, nowadays more people are becoming educated and they are looking for jobs and opportunities to improve products/services that thus can lead to a great socio-economic impact. It is important to mention the European position on project foundation and their funding to contribute towards a sustainable world development [1]. According to the EWEA scenario (European Wind Energy Association), the wind energy industry will provide around 334,000 jobs in Europe by 2030 and the installed wind power capacity could reach 320GW. Europe is required to provide at least 20% of European electricity consumption from wind by 2020 and even better 27% by 2030 (European Wind Energy Association, 2015). This can be achieved by exploiting offshore wind farms (European Commission, 2015). Aeolic energy can commit to secure European energy independence [1] since Europe is the leader of the global wind market [1]. 3 Figure 1.1: Total capacity of EU wind energy installation At the same time, computational science is exploding while the supercomputers can perform to a quadrillion of FLOPS (floating-point operations per second) and handle multiple components. Although computers will never be able to think at the same level as human brain [10], people can hardly understand the advantage of the performance outcome. 1.1 Background Wind energy researchers create opportunities for potential investigations and individual contributions from conventional technologies by optimising wind farm design and developing accurate models. In order to achieve an integrated tool, aspects from multiple disciplines should be taken into account. Every discipline has a different contribution and adds data which can lead research to a highly complex level. The proper use of computers can promote the development of those models. Wind energy cannot be stored [14] and therefore we are looking for more accurate and predictable models. In the wind farms case, the computational procedure can be based on a very large number of design objectives and constraints. With regards to objectives, the main goal of a wind farm is to maximize the benefits by maximizing energy generation and minimizing the costs [12]. Constraints are related to environmental aspects, technical and electrical specifications, design effects and setback restrictions ([8], p.372). Furthermore, it is worth to mention the distinction between on-shore and off-shore wind farms which can diversify the constraints of the models. 4 A large number of software programs is available to facilitate these models, but human intervention is still required in order to solve complex optimization problems using approximation algorithms ([8], p.371). And here is where my interest starts. As a computer scientist, who has dealt with NP-hard problems in the past, I have been attracted by the complexity of wind farm layout design problems since they need computational intelligence techniques to be solved. Furthermore, my interest has been increased due to my postgraduate knowledge on heuristic algorithms, which can solve these problems more efficiently. In order to capture physical phenomena, mathematical models involved in the design of a wind model could rely on dynamical numerical representation for a better understanding of the behaviour of wind farm effects. With a stochastic model, we can repeatedly simulate outcomes using suitable approaches to generate random numbers to measure the probability that they will occur for any choice. However, these simulations are based on large computers due to the complexity of the model and further work should focus on creating accurate and comprehensive models [7], p.14). 1.2 Research Questions 1.2.1 General Research Questions Why is Wind Farm Design interesting from an operations research perspective? 1.2.2 Specific Research Questions 1. What kind of investigation has already been done? And at what point? 2.Which models requires higher computational effort? How can we deal with this type problems? Approach Section 1.4 gives an overview of different computational models involved in wind farm design based on existing literature. Each researcher has presented the wind farm design from a different point of view. Indeed, they mentioned some similar important issues needed to be taken into account, according to the results. At the end of this section, Table 1.1 presents a short overview in order to answer the first specific research question. After the examination of existing literature, I have selected an integer programming model for minimizing cable lengths. The model is presented in the paper ”An Integer Programming Model for Branching Cable Layouts in Offshore Wind Farms” [9]. I found this model extremely interesting because 5 of its complexity level. Section 2.1 introduces the notations of the original model using graph theory. The researchers, who developed this model, achieve to generate the minimum total cable length in a wind farm by taking the required constraints into account. In order to understand the above model and prove the high computational effort that is required to answer the second specific question, I implemented the model in GAMS: General Algebraic Modelling System (Appendix B1). During the implementation, a modification of the original model has been achieved and it is presented in Section 2.2, in the same graph theory form as the original. Next to this, three numerical examples are presented to show the efficiency of the model. Through the examination of the above problem, a bi-level problem arose. Bi-level optimization is a special kind of optimization where one problem is embedded (nested) within another. This problem has been considered complex so it has been investigated as a subproblem. The configuration of the model is given in details in Chapter 3 and it refers to adding a node on the power grid which is explained in detail in Section 3.1. Questions of the additional node problem: 1. Is the addition of a node beneficial? If yes, for which instances? 2. How can continuous optimization give the optimal location of the additional node in the grid? The adjustment of the original model is embodied to answer the first question. In order to compare the results of the potential usage of an additional node, more calculations are required. The second question has been answered in a more analytical way. Firstly, the case of two wind turbines, has been implemented by studying the corresponding Weber problem [16] (Appendix A.4). The above case has been examined twofold, i.e. in a symmetric and a non-symmetric way (Section 3.1.1/3.1.2). In addition, the case of three wind turbines has been proven more complex since it alters the results of the two wind turbines case (Section 3.1.3). As a result, a complete figure has been added for visual illustration and better understanding. The investigation has been ended with the symmetric case of four wind turbines, which has the same results as two wind turbines symmetric case (Section 3.1.4). Section 3.2 includes the consideration of planarity constraint. The updated model embedding Weber problem can be found in Section 3.3 and the implementation of the model in GAMS is presented in Appendix B2-B3. Chapter 4 discusses the findings of the thesis research as a conclusion chapter, based on reasoning and evidence. It aims to carry the reader to a new level of perception while summarizing the overall content, and it offers answers to the questions raised in the research. 6 1.3 What the Reader can Expect This thesis report aims to intrigue the operations research scientists to explore the opportunity of combining multiple aspects in wind farm design problems. The short description of the existing literature in wind farm field, Section 1.4, gives a clear idea of how different researchers have tried to contribute to the development of accurate and precise models. In my turn, I tried to prove the complexity of an existing model by analyzing and breaking down every single equation. In addition I have simply visualized the constraints, in order to give the picture to readers and potential wind energy field researchers and show the purpose of each equation. Furthermore, I gave some graphical representations as examples, by comparing the expected with the real result. As an additional section in this report, the reader can find a description of an optimization subproblem, which arose during the examination of the modified model. The introduction of an additional node to an existing model has facilitated the formation of the problem and the solution method. In order to prove and illustrate the extended model, I have followed a more analytical method by creating simple and small cases with different graphical examples. Finally, I end the report with a general conclusion arguing that wind farm design can be interesting from an operations research perspective, due to the complexity of models. Also the discussion includes a summary of the examined model, interpretation of findings and recommendations for further research. At the end of this report, the reader can find information about additional general knowledge and the GAMS code. 1.4 Existing Literature My research questions have been raised by examining existing publications and articles. As I mentioned before, there are multiple aspects that should be taken into account in order to develop a comprehensive model. According to the existing literature, a lot of researchers with different backgrounds have achieved to develop and/or contribute to computational models for wind farm design up to a level so far. First of all, it would be wise to introduce the definition of the popular wake effect. This phenomenon is relevant to the power loss caused by the reduction of wind velocity behind the turbine. The velocity deficit depends mainly on the closest turbine and this is the reason why it is important to position the turbines in a way of minimizing the effect [13]. In other words, the optimization of turbine location can be considered as the most important aspect. Currently, according to the WFLOP-Wind Farm Layout Optimization 7 Minimize the total cost plus a penalty to avoid non-integer alternatives min pCOST =COST + 0.0001 X (i,j)∈AE C−1 X h=1 h2xh ij (9) The penalty cost has been added to the objective function. The penalty weight aims to force integer solutions for xin the linear programming relaxation and prioritizes the sequence of nodes and the intensity of cables consequently. Every time that a single connection is created, the cost of the intensity of cables is considered. In order to minimize the total cost, an arbitrary value of 0.0001 is multiplied by the squared number of h. A small penalty is included to prevent alternative solutions that do not represent an adjacent choice for the intensity of cables. Convex quadratic minimization penalty method: In the right hand side of the Equation 9, the intensity of cables is squared and it creates a convex quadratic function which can be divided into four pieces called breakpoints where haddressed to (1,1),(2,4),(3,9),(4,16) points as is shown in Figure 2.2. The secant line lies above the graph of the function between the h2 1= 1 and h2 4= 16 and it forces to give a solution in between due to the weight of the function. Figure 2.2: Penalty Weight 14 Subject to: Connection X (i,j) C−1 X h=1 xh ij +yi= 1 ∀i∈Vc(10) The first constraint which defines the creation of a connection between a turbine with another turbine or substation, remains the same as defined in the original model (Section 2.1). It ensures that each turbine has exactly one outgoing cable which ends in another node. Figure 2.3: Connection of nodes Direction X (i,j) C−1 X h=1 xh ij +X (j,i) C−1 X h=1 xh ji ≤1∀(i, j)∈Vc(11) The next constraint has been developed in order to avoid multi directional connections. Once a connection has been created, then it should be saved as one direction connection, preventing the creation of the same connection backwards. Figure 2.4: Single direction of two node connection 15 Origin X (k,i) C−1 X h=1 xh ki +X (i,j) x1 ij +yi≥1∀i∈Vc(12) An important consideration that became clear while testing the model was the definition of the origin turbine. An origin turbine is the first turbine on the arc, but in reality, it is the one which sends the electrical power last, since it is the farthest turbine starting from the power station. So, it is the first node considering the intensity of cables and this number is increasing while the turbines are approaching the station. Figure 2.5: Definition of the first node of route The importance of this constraint is based on the next inequality. Inequality Cyj+X (j,k)∈AE C−1 X h=1 hxh jk −X (i,j)∈AE C−1 X h=1 hxh ij ≥1∀j∈Vc(13) The development of this certain inequality is the reason that makes this model differ from the original. The first part defines the possibility of the direct connections of turbines to the substation without any intermediate node turbine. Otherwise, if a turbine is connected with another turbine then the number of cables should be increased by one in order to afford the electrical transport through the cable. 16 Figure 2.6: Intensity of turbine cables 2.2.1 Missing constraints In the original model, the following constraints have been introduced: Branching Branching defines the maximum number of branches per turbine. In Figure 2.7: Number of turbine branches this computational model the branching has not been taken into account, because of the lack of data. Reasons which determine the maximum number of branches could be relevant to turbines and cable types (size and capacity) or to topography of territory. However, as can be seen in the numerical examples 2 and 3 in Section 2.2.2, the branching is applied, because the specific constraint is relaxed. 17 Crossing Routes It is very important to prevent the crossing of cables. Crossing cables can cause high voltage power that leads to generate heat, so they may burn. Also, in order to protect the cables, the wind farm developers bury the cables into the seabed. In the case where the lowest one fails, then both have to be dug up in order to replace the deeper one. Both cases, the cost is really high, so it is more profitable to avoid crossing cables. Figure 2.8: Intersection/crossing points In this computational model, the crossing routes have been developed in an explicit way for reasons of convenience. 18 2.2.2 Numerical Examples Example 1 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 A B C D E S Figure 2.9: Graphical Example 1 The wind turbines in Figure 2.9 are located in a continuous path and the power station appears at the end of this route. Before the execution of the computational model, we can assume that the wind turbines which are located at the same row would be connected by a single arc. There is an uncertainty about turbine D, whether it would be connected on the same arc or it would connect directly to the power station. Coordinates of elements in the grid: Wind turbine locations: A: (0.0,6.0), B: (2.0,6.0), C: (4.0,6.0), D: (5.0,5.0), E: (6.0,6.0) Power Station: S: (8.0,6.0) As shown below, the solution of GAMS appears as follow: x1 AB = 1, x2 BC = 1, x3 CD = 1, x4 DE = 1, yE= 1 and all turbines are connected to the power station with a single arc. Due to the intensity of cables, wind turbine D is connected to the same arc instead of directly to the power station. 19 Example 2 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 A B C D E S Figure 2.10: Graphical Example 2 The wind turbines in Figure 2.10 are located in two continuous paths and the power station appears in between the two route endpoints. Before the execution of the computational model, we can assume that the wind turbines which are located at the same row would be connected by a single arc. So, two arcs would be created. However, we need to take the branching capacity into consideration, where the model allows branching of the cables at the wind turbine locations. Coordinates of elements in the grid: Wind turbine locations: A: (1.0,5.0), B: (2.0,3.0), C: (3.0,5.0), D: (5.0,5.0), E: (6.0,3.0) Power Station: S: (8.0,4.0) As shown below, the solution of GAMS appears as follows: x1 AC = 1, x1 BC = 1, x3 CD = 1, x4 DE = 1, yE= 1 and there is a branching at turbine C. 20 Example 3 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8A B C S D E Figure 2.11: Graphical Example 3 The wind turbines in Figure 2.11 are located around the power station. Before the execution of the computational model, we can assume that the wind turbines would connect directly to the station by creating a star shape. So, each individual wind turbine would send energy directly to the station and no penalty weight would be added for the intensity of cables. However the distances between the wind turbines and the power station vary and this is crucial reason to falsify the above assumption. Coordinates of elements in the grid: Wind turbine locations: A: (0.0,8.0), B: (3.0,3.0), C: (4.0,7.0), D: (5.0,3.0), E: (6.0,2.0) Power Station: S: (6.5,5.0) As shown below, the solution of GAMS appears as follows: x1 AC = 1, x2 CE = 1, yB= 1, yD= 1, yE= 1 and the connection of turbines A, C and E is merged in a single arc while it creates a star shape with the rest of the arcs. 21 2.3 Conclusion In the paper ”An Integer Programming Model for Branching Cable Layouts in Offshore Wind Farms” [9], the researchers refer to the terminology of capacitated Minimum Spanning Tree(MST) under the condition of satisfying some specific restrictions. Firstly, the definition of capacitated refers to the cable capacity of each subtree in the graph and the restriction requires not to be exceeded by the number of connected nodes as Equation 3 implies. For each subtree the cable installation can be calculated by choosing the optimal cable connection from the origin to terminal node in order to transport the power along its edge. In graph theory, there is a possibility where every spanning tree can be minimum if the edges have the same weight. On the other hand, when each edge has a distinct weight, then there is only one unique spanning tree, such as in the numerical examples of Section 2.2.2. Both cases are likely to occur in the case of a wind farm. In addition, the branching property of MST which is described in Equation 4, is included in this optimization problem and it implies to predefine the maximum number of branches at each node. The modified model in Section 2.2 relaxes this restriction by allowing any number of branches at the nodes, as shown in Figures 2.10 and 2.11. However, Figure 2.9 seems to be unsuitable for branching since the result shows that it is optimal to connect the turbines sequentially. Minimum Spanning Trees were first invented for the design of networks such as computer, telecommunication transportation, electrical grid, such as this, and more [18]. So another important property of MST and the wind farm case is to prevent creating cycles/loops in the network by connecting each node only once. The model has been implemented in GAMS, see AppendixB.1, and Equation 13 which is presented as unique in Section 2.2 has been developed due to the consideration of the intensity of cables to ensure the electrical transportation. The modified model has been solved using Combinatorial Optimization techniques (Appendix A.1) and Branch and Bound method has been elaborated to eliminate continuous solutions (Appendix A.2). 22 Chapter 3 Additional node The title of this chapter refers to an additional node that can be added to the network as a power substation. It is very likely that an additional node into the existing grid network can relax other limitations, such as crossing routes and it can also reduce the intensity of cables. We assume that this can lead to a reduction of cable cost significantly. The initial assumption was that the additional node should not necessarily be directly connected with the main power station in order to transport energy. This implies that it can also be connected with an intermediate turbine which must be connected to the main power station later. But this is not the case, because if we use an additional node to connect some wind turbines which are close to it, then the power substation works/acts exactly like an additional turbine which needs to transfer the receiving energy to the next turbine. After several trials, it turns out that is more wise to connect the additional node directly to the main power station. Needless to mention that some wind turbines can be connected directly to the main power station. The questions are, for which instances it is optimal to add a node, and if yes, where is the optimal location for this power substation. Using the Weber problem property [16], it is possible to find an optimal point by minimizing the distances of the elements in the grid in order to tackle the problem. This point can be considered as the location of the additional node. Section 3.1 examines the potential cost reduction for four different cases while a node is added in the grid. Crossing routes have been developed in an explicit way, as in Section 2.2. Section 3.2 includes the description of possible occurrence of crossing routes based on scenarios. In addition, the idea of adding a node on existing crossing points is introduced, when the planarity constraint is disregarded. The updated model which includes the Weber problem presented in Section 3.3 and it has been used for the following analytical examination. 23 S= (0,0), A = (1,0), B = (β1, β2) Again, from the geometric point of view, in the non-symmetric case, the optimal location of the additional node is determined by the angle 120◦ between the wind turbine A located at (1,0) and the main power station S= (0,0). Figure 3.6: Set of locations of wind turbine B, where the additional node is optimal The shaded area in Figure 3.6 shows the potential location of the wind turbine B, where the addition of a node is optimal. Otherwise, the wind turbines are connected directly to turbine A or to the main power station. Equation 4 is modifies as follow: f(x∗,(β1, β2)) (5) where x∗(β1, β2) = argxmin{d(A, x) + d(B, x) + d(S, x)} and drepresents the Euclidean distance between the two points. An important issue to consider are the fixed costs of adding a node. In this paper, these costs have been considered as negligible. But, in the real case field, this may not be optimal. This can be investigated by wind farm developers and engineers. The advantage of adding a substation is the difference between the installation and maintenance cost of the additional node and the saving costs of using it. Figure 3.7 incorporates the contour lines to emphasize the advantage of the added node in the grid, if and only if the wind turbine B is placed inside the white area. The label number shows the benefit of using the 30 Figure 3.7: Contour lines showing the advantage of adding a node given the location of the wind turbine B= (β1, β2) additional node. The addition of a substation involves the installation and maintenance costs which can be high in relation with the benefit that can be reached. Therefore the decision can be made based on realistic numbers. When the fixed costs are less than the advantage, the number shown in the label, then the installation of a node is beneficial. Recall, when the wind turbine B is placed inside the red area then the addition of a node is not optimal anymore. Figure 3.8: 3D-Surface visualisation of the advantage of adding a node 31 3.1.3 Semi-Symmetric case-3 wind turbines The semi-symmetric case can be considered as an extended case of the symmetric case, where the two wind turbines have been set in symmetric position and the location of the third turbine is varied in a systematic way again. Depending on the third wind turbine position, the optimal configuration and location of a possible additional node varies in order to satisfy the general objective. Assume that S is the main power station, A is the first wind turbine, B is the second wind turbine and now C is the third turbine with the undetermined position: S= (S1, S2), A = (α1, α2), B = (β1, β2), C = (γ1, γ2) Consider that the coordinates of elements are as follow: S= (0,0), A = (1,1), B = (α1,−α2)), C = (γ1, γ2) The question is now for which instances of the location of C it is optimal to have an additional node H= (η1, η2) and which configurations are optimal. By the meaning of that, the addition of a node can be considered as optimal, when the total length of the cable is reduced. Recall, the additional node should be connected directly towards the main power station and the location of the additional node between the symmetric wind turbines A and B is H= (√2−1,0), as has been proved in Section 3.1.1. 1. The alternative where the C= (γ1,0): a) 0 < γ1≤(√2−1) The addition of a node is not considered as optimal. Both symmetric wind turbines are connected to wind turbine C. b) (√2−1) < γ1≤1 The addition of a node is optimal. All of the wind turbines are connected to it. c) γ1≥1 The addition of a node is optimal and it is always placed at point H= (1,0). d) γ1<0 The addition of a node is optimal at point H= (√2−1,0) and the third turbine is now connected directly to the main power station. 2. The alternative where C= (γ1, γ2). a) γ1>1 The additional node is always optimal and there are two possible configurations: •In the case where wind turbine C is closer to one of the fixed tur32 bines, C connects to the closest one and the two symmetric turbines are connected to the additional node H= (√2−1,0). •In the case where wind turbine C is located somewhere in between the two fixed turbines then a new position for the additional node H= (η1, η2) is defined and all the turbines are connected to it. b) 0 < γ1<1 The addition of a node is optimal for two different configurations: •In the case where wind turbine C is closer to one of the fixed turbines, C connects to the closest one and the two symmetric turbines remain connected at H= (√2−1,0), such as in first case of 2a. •In the case where third turbine is located somewhere in between the two turbines then a new position for the additional node H= (η1, η2) is defined and all the turbines are connected to it, such as in second case of 2a. The addition of a node is not optimal for two different configurations: •In the case where either the turbine A or B, depending on which one is closest, is connected directly to turbine C. Wind turbines C and the remaining one are now connected to main station S. •In the case where the third turbine is located between the main power station and the additional node at H= (√2−1,0), then the fixed wind turbines are connected directly to the third turbine and towards the main power station. c) γ1<0 The addition of a node is optimal for two different configurations: •In the case where the third turbine is connected either to turbine A or B, depending on which one is closest, and the two symmetric wind turbines are connected to the additional node H= (√2−1,0), such as in first case of 2a. •In the case where the wind turbine C is connected directly to the main power station S and the connection of the symmetric turbines to additional node at H= (√2−1,0). Furthermore, there is a case where the addition of a node is not optimal, such as in third case of 2b. The connection of the closest fixed turbine to turbine C and the connection of turbine C and the remaining turbine to main power station has been proven more beneficial, such as in third case of 2b. In order to prove the above statement analytically, we have tried to define the boundaries of the position of the third turbine, as is shown with 33 dots in Figure 3.9. Figure 3.9: Positive side of grid where different scenarios are optimal depending on the third turbine location In general, Figure 3.9 defines whether the additional node is optimal or not, depending on location of turbine C in the positive area of grid based on the following scenarios: •The green line αshows that if the third turbine is located at this line, then the additional node is always optimal at point H= (1,0), where the rest of the turbines are connected there as well. •The yellow shadow area Bdefines that the addition of a node is optimal as in the symmetric case (Section 3.1.1), at point H= (√2−1,0), if the wind turbine C is located inside there. Although, the third turbine is connected to the closest turbine, which is turbine A, the wind turbines A and B remain connected to the additional node. •The additional node can be optimal and vary when the third wind turbine is placed in the blue area Γ or lines γand all of the wind turbines are connected to it. •The orange area ∆ shows the area where the additional node is not optimal, while the closest fixed turbine A is connected to turbine C and then, turbine C and B are connected to the main station. 34 •At the orange line δthe distance between the wind turbines C and A and the distance between the turbine C and the main power station are equal. So, the turbine C can either connected to turbines A or to the main power station, while the symmetric turbines remain connected to additional node at H= (√2−1,0). •The red area Eand the line εdefine the area where the third turbine can be connected directly to main power station while the symmetric turbines remain connected to additional node at H= (√2−1,0). •The black line ζshows that if turbine C is located at this line, then the symmetric turbines are connected to third turbine and towards the main power station. So, the addition of the node is not optimal. Figure 3.10: Contour lines showing the advantage of adding a node by given the location of the third wind turbine Figure 3.10 incorporates the contour lines, such as Figure 3.7, to emphasize the advantage of the added node in the grid. Recall, the addition of a substation involves the fixed costs which can be higher than the benefit that it provides. So, the decision will be made based on realistic numbers. 35 Figure 3.11: 3D-Surface visualisation of the advantage of adding a node varying the location of the third turbine C 3.1.4 Symmetric case-4 wind turbines In the case of two symmetric turbines the addition of a node have been proven optimal while the location of the additional node has been placed towards the main power station. An interesting extended case arose, which is based on the symmetric case (Section 3.1.1). In this case, the total number of wind turbines are four and the last two turbines are symmetric with the two initial wind turbines, in a sense of the vertical axis y. Assume again that S is the main power station, A is the first wind turbine and B is the second wind turbine: S= (S1, S2), A = (α1, α2), B = (β1, β2), C = (γ1, γ2), D = (δ1, δ2) Now consider that the coordinates of elements are as follow: S= (0,0), A = (1,1), B = (α1,−α2)), C = (γ1, α2), D = (γ1,−α2) (a) The alternative where the last two turbines are connected to the two turbines which are already connected to the optimal additional node H= (√2−1,0) as has been found for the symmetric case of two turbines (Section 3.1.1). (b) The alternative where the last two turbines have been set as the only ones in the grid in order to define a new position for the additional node H2=(γ1−1/√3,0). Thanks to the analytical expression in Section 3.1.1 the location of the additional node is now known and all the turbines are connected to it. 36 (c) The alternative where all of the four turbines are entered. So, the Weber problem now tries to minimize the distances between the 5 total elements in the grid and defines a new location for the additional node H= (η1,0). Consider the following graphical example: 0 0.511.522.533.544.5 5 −1.5 −1 −0.5 0 0.5 1 1.5 S A C HH1H2 Figure 3.12: Three scenarios of the case of 4 symmetric wind turbines Assume again that S is the main power station, A is the first wind turbine, C is the third wind turbine, while Hs is the additional node: S= (S1, S2), A = (α1, α2), C = (γ1, γ2), H = (η1, η2) Now consider that the coordinates of elements are as follow S= (0,0), A = (1,1), C = (5, α2), H = (√2−1,0), H1 = (1.5,0), H2 = (5 −1/√3,0) Figure 3.12 represents graphically the potential connection of the elements in the grid. The alternative (a) describes the scenario where the wind turbine C can be connected direct to A and then to the main power station. Alternative (b) suggests the connection of wind turbines A and C are with the additional point H1 and then to the main power station, as shown in Figure 3.12 using dotted lines. The last alternative describes the connection of wind turbines A and C to the new position of the additional node H2 and towards the main station, as is shown using dashed lines. The outcome of the above alternatives has been compared with each other. The minimum cable length is given for the first alternative, and the optimal location of the additional node remains the same in the symmetric case in Section 3.1.1. 37 3.2 More: Crossing Routes In the previous section, the placement of an additional node into the electrical grid has been examined using the Weber property. The restriction/constraint that the Weber problem does not take into account is the crossing of cables. Although, it can give a point which indeed minimizes the distance, this point is the location of the additional node where more cable connection paths exist. So, it is very likely that for cases with more turbines, some crossing points will be created between the turbines which are connected to the substation and the turbines which are connected to the main power station. The connection paths can create the following possible scenarios: 1. Intersection: The intersection point is created when the paths that connect the elements are crossed. The intersection point can be found by the solving the linear functions. 2. Align: •Overlapping: This occurs when the edges are aligned. In the case of wind farm design, it may be assumed that this is not likely to occur because the aim is to minimize the distances between the elements. So, the element which is located in between two others, will not connect with an element which is further. •Non-overlapping: The possibility where the two connection paths are aligned, but not overlap. 3. Parallel: The possibility where the two connection paths are in parallel, then the creation of crossing points is unlikely. 4. Non of the above: The case where the elements are connected in a more random way and non of the above cases occur. At the point, where the Weber problem has been proved inadequate, the investigation has been gone through the idea of adding a node, where the crossing point will be created. At the beginning, we can assume that the planarity constraint is not necessary anymore and we can compute the optimal cable layout connection. In that case should be checked, whether the optimal solution is creating paths with intersection points and it is necessary to repeat the calculation by placing the additional node on those crossing points. But after that, the planarity constraint should be added to prevent the crossing between the connection of the node and the power station with any other path. Otherwise, this can lead to a loop where we will have to add substations every time that a crossing point exists. The above hypothesis has not been examined and it can be considered as future research. In the next section, an updated version of the modified model (Section 2.2), is shown. The updated model which includes the Weber problem, has been used for the examination of the cases in Section 3.1. 38 3.3 Updated Model Consider a graph with node set V=(Vc∪Vd), where Vcrepresents a given set of wind turbine locations and Vdrepresents the station locations, Vd=|2|. The edge set E ⊆V2represents the possible connections between the turbines and the power stations. The arc set AE={(i, j) : {i, j} ∈ E}which has an associated symmetric cost which is relevant to the distance between the end nodes of the edge. As has been mention before, the difference between the arc and the edge is based on the direction of connection betweens the nodes. The following notation is used: Indices hnumber of sources connected to an arc h∈ {1,2, .., |Vc|} isource index i∈V sstation index s∈ {S} j,k alias indices for nodes Vd Data caij symmetric cost/distance between turbines on arc (i, j)∈AE cbicost/distance on arc from wind turbine to power station i∈Vc cdicost/distance on arc from wind turbine to additional node i∈Vc dwscost/distance on arc between power station and additional node s∈V χset of crossing routes χ∈E2 Variables xh ij connection between iand jwith intensity of cables h xij ∈R yn iconnection between iand main power station yi∈ {0,1} zn iconnection between iand additional node zi∈ {0,1} wconnection between main power station and additional node w∈ {0,1} COST total cost COST ∈R+ Objective Function: Minimize the total cost COST =X (i,j)∈AE C−1 X h=1 caijxh ij +X i cdizi+X i cdijyi+X s dwsw(6) Minimize the total cost plus a penalty to avoid non-integer alternatives min pCOST =COST + 0.0001 X (i,j)∈AE C−1 X h=1 h2xh ij +X s dwsw(7) 39 Appendix A Additional Knowledge A.1 Combinatorial optimization Combinatorial optimization is a branch of optimization. Its domain is optimization problems where the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution. To deal with problems of combinatorial optimization, the objective is to find the best solution or optimal solution, one that minimizes a given cost function. There are some techniques to solve not complex problems, such as Branch and Bound [15]. A.2 Branch and Bound All the solutions of the wind farm cases studied in this report, have been declared automatically in an integer form due to the Branch and Bound method. All the variables are required to be 0 or 1 (binary), so the problem can be considered as MILP: Mixed Integer Linear Program. This problem is also classified as NP-hard problem and it is hard to solve. So, the elaboration method of B&B is used for MIP models in order to give an integral value as a solution. While the current solution is not integer then two new continuous LP problems are added as constraints. In fact, it calculates the bounds of the best integer solution to determine whether it is useful to branch the generated sub-problems [4]. It is worthwhile to mention, that at the beginning, before the penalty weight was added as convex quadratic method (Equation 9 in Section 2.2), the solver of GAMS was giving decimal solutions, by splitting the number of 1 to several solutions along the connections. The B&B method has been elaborated in order to eliminate the continuous solutions and now it creates a logical continuous cable solution. 46 A.3 Minimum Spanning Tree A minimum Spanning Tree (MST) is an undirected graph which connects all the nodes with the minimal total weight on its edges. A single graph can have different spanning trees. In the case of wind farm design, the weight of edges can be consider as the distance of the nodes. Since we aim to minimize the sum of the edge lengths and the total cost consequently, it is very important to include the minimum cable cost in the final route [18]. A.4 Weber Problem In general, the Weber Problem is a problem in location theory and it aims to find a point that minimizes the sum of transportation costs [16]. In the case of wind farm design, it minimizes the distances between the wind turbines and the main power station, in order to locate (or not) the additional node in the best possible position in the grid and minimize the total cable cost. Given a set of points {Pi...Pn} min x n X i=1 d(xiPi) (1) where drepresents the Euclidean distance between the elements. A.5 Voronoi diagram A Voronoi diagram consists of a set of points in a plane which define the region of the nearest point. The distances of these points can be found using the Euclidean and the Manhattan distance formulas. In this report, the Euclidean distance formula has been used in order to calculate the distances between the elements. The concept of Voronoi diagram has been proven useful for the creation of the geometric statement [19]. 47 Appendix B GAMS modelling B.1 My GAMS Model Set isource index /A*E/ harc states /1*4/ Alias (i,j,k); Table a(i,j) arc of connection A B C D E A ab ac ad ae B ba bc bd be C ca cb cd ce D da db dc de E ea eb ec ed Parameters b(i) arc of connection /A as, B bs, C cs,D ds, E es/ nrcable(h) number of cables /1 1, 2 2, 3 3, 4 4 / ca(i,j) cost of connection cb(i) cost of connection; ca(i,j)= a(i,j)*10; cb(i)= b(i)*10; 48 Variables x(i,j,h) continuous variable y(i) binary variable pCOST penalty cost COST cost Positive Variables x; Binary Variables y(i); Equations Eq COST Total cost Eq pCOST Penalty cost Eq Connection(i) Connection constraint Eq Direction(i,j) Direction constraint Eq OriginCon(i) Origin Connection Eq Load(j) Load Eq pCOST.. pCOST =e= sum((i,j), ca(i,j)*sum(h,x(i,j,h)))+sum(i, cb(i)*y(i))+0.0001* *sum((i,j,h), nrcable(h)*nrcable(h)*x(i,j,h)); Eq COST.. COST =e= sum((i,j), ca(i,j)*sum(h,x(i,j,h))) +sum(i, cb(i)*y(i)); Eq Connection(i).. sum((j,h), x(i,j,h))+y(i)=e=1; Eq Direction(i,j).. sum((h), x(i,j,h)+x(j,i,h))=l=1; Eq OriginCon(i).. sum((k,h), x(k,i,h)) +sum(j, x(i,j,’1’))+y(i) =g= 1; Eq Load(j).. 5*y(j)+sum((k,h), nrcable(h)*x(j,k,h))-sum((i,h),nrcable(h)*x(i,j,h)) =g= 1; *Crossing Routes between turbines x*x example Eq ABCD.. sum(h,x(’A’,’B’,h)+ x(’B’,’A’,h)+x(’C’,’D’,h)+x(’D’,’C’,h)) =l= 1; *Crossing Routes between depot x*y example Eq ABCS.. sum(h,x(’A’,’B’,h)+x(’B’,’A’,h))+ y(’C’)=l= 1; 49 x.fx(i,i,h)=0; MODEL Branching /all/; SOLVE Branching using mip minimizing pCOST; Display COST.l; 50 B.2 Weber Problem Set iturbines /A,B/ Parameters x(i) x coordinate of turbine /A xA,B xB/ y(i) Y coordinate of turbine /A yA,B yB/ Variables ax coordinate of turbine bY coordinate of turbine dist(i) distance of turbines di distance to station dis total distance; Equations Eq dis Total distance Eq di Distance to station Eq dis(i) Distance Eq dis..dis =e= sum((i), dist(i)+di; Eq dist(i)..dis(i) =e= sqrt(sqr(x()i)-a)+sqr(y(i)-b); Eq di(i)..di=e= sqrt(sqr(a)+sqr(b)); MODEL Branching /all/; SOLVE Branching using nlp minimizing dis; Display dis.l; 51 B.3 My GAMS Model-The additional node Set isource index /A*E/ sarc states /S/ harc states /1*4/ Alias (i,j,k); Table a(i,j) arc of connection A B C D E A ab ac ad ae B ba bc bd be C ca cb cd ce D da db dc de E ea eb ec ed Parameters b(i) arc of connection from power station /A as, B bs, C cs,D ds, E es/ d(i) arc of connection from hub /A as, B bs, C cs,D ds, E es/ cw(s) arc of connection between power station and hub /S hs/ nrcable(h) number of cables /1 1, 2 2, 3 3, 4 4 / ca(i,j) cost of connection between turbines cb(i) cost of connection between turbine and power station; cd(i) cost of connection between turbine and hub station; dw(s) cost of connection between power and hub station; ca(i,j)= a(i,j)*10; cb(i)= b(i)*10; cd(i)= d(i)*10; dw(s)= cw(s)*10; 52 Variables x(i,j,h) continuous variable z(i) binary variable wbinary variable y(i) binary variable pCOST penalty cost COST cost Positive Variables x; Binary Variables z(i); Binary Variables w; Binary Variables y(i); 53 Equations Eq COST Total cost Eq pCOST Penalty cost Eq Connection(i) Connection constraint Eq Direction(i,j) Direction constraint Eq OriginCon(i) Origin Connection Eq Load(j) Load Eq Connection Hub(i) Connection Hub ; Eq pCOST.. pCOST =e= sum((i,j), ca(i,j)*sum(h,x(i,j,h))) +sum(i, cd(i)*z(i)) +sum(i, cb(i)*y(i))+0.0001 *sum((i,j,h), nrcable(h)*nrcable(h)*x(i,j,h)) *sum(s), dw(w)); Eq COST.. COST =e= sum((i,j), ca(i,j)*sum(h,x(i,j,h)))+sum(i, cd(i)*z(i));+sum(i, cb(i)*y(i)); Eq Connection(i).. sum((j,h), x(i,j,h))+y(i)+z(i)=e=1; Eq Direction(i,j).. sum((h), x(i,j,h)+x(j,i,h))=l=1; Eq OriginCon(i).. sum((k,h), x(k,i,h)) +sum(j, x(i,j,’1’))+y(i)+z(i)=g= 1; Eq Load(j).. 5*y(j)+5*z(j)+sum((k,h), nrcable(h)*x(j,k,h))-sum((i,h),nrcable(h)*x(i,j,h)) =g= 1;, Eq Connection Hub(i).. z(i)-w =l= 0; *Crossing Routes between turbines x*x example Eq ABCD.. sum(h,x(’A’,’B’,h)+x(’B’,’A’,h)+x(’C’,’D’,h)+x(’D’,’C’,h)) =l= 1; *Crossing Routes between depot and hub h*y example Eq BHCS.. z(’B’)+ y(’C’)=l= 1; x.fx(i,i,h)=0; MODEL Branching /all/; SOLVE Branching using mip minimizing pCOST; Display COST.l; 54 Bibliography [1] European Wind Energy Association. Large Scale Integration of Wind Energy in the European Power Supply: Analysis, Issues and Recommendations : a Report. European Wind Energy Association, 2005. [2] Joanna Bauer and Jens Lysgaard. The offshore wind farm array cable layout problem: a planar open vehicle routing problem. Journal of the Operational Research Society, 66(3):360–368, 2014. [3] Souma Chowdhury, Jie Zhang, Achille Messac, and Luciano Castillo. Optimizing the arrangement and the selection of turbines for wind farms subject to varying wind conditions. Renewable Energy, 52:273 – 282, 2013. [4] G.D.H Claassen, Hendriks Th.H.B, and Eligius M.T Hendrix. Decision Science. Wageningen Academic Publishers, 2007. [5] G. Ghiani, G. Laporte, and R. Musmanno. Introduction to Logistics Systems Management. WILEY, 2013. [6] Jan Kristian Haugland and Dag Haugland. Computing the optimal layout of a wind farm. 2012. [7] Stefan Ivanell, Jens N Sørensen, and Dan Henningson. Numerical computations of wind turbine wakes. Springer, 2007. [8] Salman A Khan and Shafiqur Rehman. Iterative non-deterministic algorithms in on-shore wind farm design: A brief survey. Renewable and Sustainable Energy Reviews, 19:370–384, 2013. [9] Arne Klein, Dag Haugland, Joanna Bauer, and Mario Mommer. An integer programming model for branching cable layouts in offshore wind farms. In Modelling, Computation and Optimization in Information Systems and Management Sciences - Proceedings of the 3rd International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences - MCO 2015, Metz, France, May 11-13, 2015, Part I, pages 27–36, 2015. 55