Network-based optimization techniques for wind farm location decisions

Abstract

This study aims to find appropriate locations for wind farms that can maximize the overall energy output while controlling the effects of wind speed variability. High wind speeds are required to obtain the maximum possible power output of a wind farm. However, balancing the wind energy supplies over time by selecting diverse locations is necessary. These issues are addressed using network-based models. Hence, actual wind speed data are utilized to demonstrate the advantages of the proposed approach.

Key words： wind energy; wind farm location; network analysis; optimization; clique; s-plex

Introduction

The increasing global demand for energy and growing environmental concerns over the dependence on fossils lead scholars to explore for alternative solutions (^{Pardalos et al., 2013}). Wind is among the most important renewable sources of energy with minimal environmental impact and is abundant in nature. Wind farms do not use fuel and do not emit air pollution, and the energy consumed to manufacture a wind power plant is recovered within a few months only. In addition, the microclimate generated by wind turbines has advantages to corn and soybean crops, such as preventing the late spring and early autumn frosts and reducing pathogenic fungi (^{Takle and Lundquist, 2010}). The disadvantages of harvesting wind energy are minimal compared with traditional sources that involve sound and visual pollution, bird and bat deaths, and interference with radio reception and ground radar systems used for military, weather, and air traffic control.

Globally available wind power over land in locations worldwide with mean wind speeds exceeding 6.9 m/s at 80 m height is approximately 72 TW (630–700 PWh/yr) according to several studies (^{Jacobson, 2009}). As of 2005, this resource was five times the world’s total power production and 20 times the world’s electric power production (^{Archer and Jacobson, 2005}). Hence, recent years have been marked by a rapid development in the wind energy sector, especially in China where wind power has become a key economic growth component. In 2016, China added 19.3 GW of wind power generation capacity, accounting the total capacity of up to 149 GW; the country generated 241 TWh of electricity from the wind, which constituted 4% of the country’s total consumption for the year (^{Global Times, 2017}). Currently, China has the largest capacity of installed wind farms and is ranked second worldwide in the production of wind energy, with the US being first due to their higher capacity factor (^{Vaughan and Kelley, 2016}). The remarkable recent progress in developing wind energy capabilities may be the beginning of a new era because the potential for continuing growth is tremendous. ^{McElroy et al. (2009)} asserted that China could meet all of its electricity demands through wind power by 2030. However, for these projections to materialize, the focus of governmental and private entities involved in the wind energy sector should shift from the domain of landscape assessment and environmental impact to the economic viability and efficiency.

One of the main challenges that should be overcome to maximize fully the wind for energy generation purposes is the high variability of wind speeds (^{Soder, 2004}). Particularly, the distribution of wind speed over time resembles the Weibull function (^{Piacquadio and De la Barra, 2014}). A diverse set of locations for wind farms could be selected to ensure a steady supply of wind energy, such that at least some of the selected locations have sufficiently high wind speed at any time. Specifically, the following question needs to be addressed: Given the wind speed data collected from the potential locations of wind farms, which locations should be selected to maximize the wind power production while balancing the wind speed variability?

Various aspects of wind energy related to this question have been considered in previous studies based on different perspectives (^{Kahn, 1979}; ^{Milligan and Artig, 1999}; ^{Milligan, 2000}; ^{Archer and Jacobson, 2007}; ^{Drake and Hubacek, 2007}; ^{Roques et al., 2010}; ^{Degeilh and Singh, 2011}; ^{Grothe and Schnieders, 2011}; ^{Novoa and Jin, 2011}; ^{Liu et al., 2013}). Different from the existing works on the topic, the present work approaches the issue by using a network representation of the wind energy system. In this study, the nodes correspond to potential sites for wind farm location and the edges connect the pairs of sites characterized by negative correlations of wind speed fluctuations. Hence, the problem of selecting appropriate locations can be reduced to finding tightly knit clusters of nodes corresponding to windy locations. We illustrate the proposed methodology by using a real-life wind speed data set collected from more than 200 locations in Bolivia over a 10-year period.

The network-based data mining approach explored in this work is based on observation that big data arising in various complex systems can be conveniently modeled by using networks or graphs. The components of the complex system are represented as vertices (nodes), and the pairwise interactions among different components are described by edges (arcs) that link pairs of vertices. This simple and intuitive modeling technique can maximize the rich and powerful network analysis tools to reveal several global structural properties of the underlying system and predict the overall trends in its dynamics. This approach has been successfully used to analyze several other complex systems involved in various applications (^{Boginski et al., 2003}), including phone call records in telecommunications (^{Abello et al., 1999}), social networks (^{Pattillo et al., 2012}), and stock market data (^{Boginski et al., 2006}).

The remaining sections of this paper are organized as follows. Section 2 provides some preliminaries from graph theory and network analysis. Section 3 describes the process used to construct a wind speed graph by using the wind speed time series. Section 4 presents the results obtained by applying the proposed approach to the available data set. Finally, Section 5 elaborates the conclusion of the study.

Preliminaries

Before describing the process of constructing the wind speed graph, we introduce the necessary definitions, notations, and other preliminaries from the graph theory and network analysis.

A simple undirected graph (network) is provided as G=(V,E), where V is the set of n vertices (nodes), and E is the set of m edges (arcs) that connect the pairs of vertices. The edge between vertices i,j\in V is denoted by i,j\in E. If the edge (i,j) exists in the graph, then the two vertices, i and j, defining the edge are the endpoints of this edge, also said to be neighbors and adjacent to each other. The number of neighbors of a vertex is called the degree of that vertex. A graph is regarded as complete if it contains all possible n(n−1)/2 edges. For a subset S\subseteq V, the subgraph induced by S, denoted by G(S)=(S,E(S)), uses S as its set of vertices and E(S) as its set of edges, where E(S) consists of all edges in E that have both endpoints in S. A subset C of vertices is called a clique if the induced subgraph G(C) is a complete graph, that is, all vertices in C are pairwise adjacent.

Cliques can be considered an idealistic model of a tightly knit cluster of nodes in a network, where all possible pairwise connections are present. On the one hand, the “perfect” nature of a clique makes it an attractive cluster model, on the other hand it is the reason cliques are considered overly restrictive in several applications, especially when the studied network model is only an approximation of the actual complex system under investigation. As a result, many alternative cluster models have been introduced in the literature, aiming to overcome this drawback by allowing missing edges while preserving certain cohesiveness characteristics of cliques. Such models, referred to as clique relaxations (^{Pattillo et al., 2013}), often provide a better description of clusters than the cliques. In this study, we will use a clique relaxation called s-plex to model clusters in wind speed graphs. Specifically, a subset of vertices C is called an s-plex if each vertex from C is a neighbor of all but at most s vertices from C , where s is a given positive integer constant. Note that for s =1, s-plex is equivalent to a clique (i.e., the only non-neighbor of each vertex is the vertex itself). For low s values (2,3), s -plexes provide extensively cohesive clusters that retain the properties of a clique, such as high connectivity and low diameter, in a slightly relaxed form (^{Balasundaram et al., 2011}; ^{Verma et al., 2015}).

Large tightly knit clusters in a network constitute several most important building blocks that fully influence the network’s overall structure. Particularly, the size of the largest clique and s-plex can be used to characterize the global cohesiveness properties of the network. The problems of finding the largest clique and s-plex in a graph are referred to as the maximum clique and maximum s-plex problems, respectively. Both problems are NP-hard (^{Garey and Johnson, 1979}; ^{Balasundaram et al., 2011}). Nevertheless, effective methods that can successfully address practical occurrences of these problems are available (^{Trukhanov et al., 2013}; ^{Verma et al., 2015}).

Construction of the wind speed graph

In constructing the wind speed graph, we consider a number of geographically diverse locations to be the potential places for harvesting wind energy and represent each location as a node in the graph. In the case study presented in the subsequent section, we use a data set based on a 10-year study in Bolivia (^{GeoBolivia, 2008}). The data set contains the wind speed data at a height of 10 m for 201 potential wind mill locations recorded every 10 min. The information collected is represented in monthly charts, correcting the variation of the data in air density, height, and temperature depending on the location, due to the altitude in comparison with the sea level. Figure 1 shows a map of the 201 locations with their corresponding average wind speed. Different ranges of velocities are denoted by various radii of blue disks in the figure.

Although the measurements are obtained at the height of 10 m, a typical wind turbine is operated at a height of 80 m or 100 m, where the wind speeds are typically higher. In accordance with the wind profile power law relationship (^{Touma, 1977}), we have

Fig.1 Geographical locations considered in the study

Full size|PPT slide

u={{\displaystyle u}}_r{{\displaystyle \left({\displaystyle \frac{z}{{{\displaystyle z}}_r}}\right)}}^{\alpha },

where u is the wind speed (m/s) at height z (m), and u_r is the known wind speed at a reference height z_r. The friction coefficient \alpha depends on the type of the location and ranges between 0.1 for lakes, ocean, and smooth hard ground and 0.4 for city areas with high-rise buildings (^{Bañuelos-Ruedas et al., 2011}).

Figure 2 shows the average wind speed for each of the investigated sites over a considered period at a height of 10 m. Here, the X- and Y-axes correspond to the order index of the locations and the average wind speed, respectively. The overall average speed for all the locations is 2.70 m/s.

Fig.2 Average wind speed for each of the 201 sites

Full size|PPT slide

Figure 3 shows the cumulative average wind speeds for all the investigated sites. From the figure, the X-axis is the set of locations sorted in decreasing order of the average wind speeds, and the Y-axis corresponds to the average (left) and cumulative average wind speeds (right, indicated by the orange line). The variance of the average wind speeds is 2.2867, and the standard deviation is 1.5122.

Fig.3 Cumulative average wind speeds for the considered sites

Full size|PPT slide

The edges in the wind speed graph are constructed on the basis of the pairwise correlations of wind speed fluctuations of the considered sites. Let S_i(t) denote the wind speed in location i at time t. Moreover, the fluctuation of the wind speed for the ith site at time t is expressed as {{\displaystyle R}}_i(t)=\ln \left({\displaystyle \frac{{{\displaystyle s}}_i(t)}{{{\displaystyle s}}_i(t-\mathrm{1})}}\right), whereas the correlation coefficient between sites i and j can be calculated as follows (^{Mantegna and Stanley, 2000}):

{{\displaystyle C}}_{ij}={\displaystyle \frac{({{\displaystyle R}}_i{{\displaystyle R}}_j)-({{\displaystyle R}}_i)({{\displaystyle R}}_j)}{\sqrt{(R_i^2-{\left(R_i\right)}^2)(R_j^2-{\left(R_j\right)}^2)}}},i,j\in V,

where V denotes the set of the considered sites, which is also the set of vertices of the constructed wind speed graph. Given that \left|V\right|=\mathrm{201} for our working data set, we have 20100 pairs of correlation coefficients. Figure 4 shows the distribution of the computed correlation coefficient values. Here, the X-axis corresponds to the correlation value and the Y-axis is the frequency of pairs of sites with the correlation coefficient value in the corresponding interval. The most frequently occurring correlation coefficient values are around 0.33, the average correlation coefficient value is approximately 0.27, and the median is around 0.3.

Fig.4 Distribution of the correlation coefficient values

Full size|PPT slide

Two versions of the wind speed graph can be considered on the basis of the correlation coefficients, that is, the complete edge-weighted version (where all possible edges are present with the weights given by the corresponding correlation coefficients) and a threshold-based version constructed as follows. The correlation threshold \theta is selected and the edge (i,j) in the wind speed graph is included if and only if . In this work, we focus on the latter version. Selecting an appropriate correlation threshold is an important consideration in constructing a threshold-based wind speed graph. The wind farms must be located in places that have negative pairwise correlations of wind speed fluctuations to minimize the effects of wind speed variability. Hence, \theta =\mathrm{0} is used as the threshold correlation value in this work. The number of edges in the corresponding wind speed graph is 4811 out of possible 20100 edges, corresponding to the edge density of 0.239353. The edge density is expressed as 2m/(n(n−1)), where m is the number of edges and n is the number of vertices.

Figures 5 and 6 show the wind speed graph and its degree distribution, respectively. The average degree of a vertex is around 47.87.

Fig.5 Threshold-based wind speed graph with \theta =\mathrm{0}

Full size|PPT slide

Fig.6 Degree distribution for the threshold-based wind speed graph with \theta =\mathrm{0}

Full size|PPT slide

Case study

In this section, we present the network analysis results obtained from the wind speed graph constructed in the previous section based on the data set of the 10-year study in Bolivia (^{GeoBolivia, 2008}). Then, we solve the maximum clique and the maximum s-plex problems for s=2,3, as well as their vertex-weighted versions. Given the nonnegative weight {{\displaystyle w}}_i associated with each vertex i|V, the maximum weight clique (s-plex) is utilized to find a clique (s-plex) C that maximizes {\displaystyle {\sum }_{i\in C}{{\displaystyle w}}_i}. The weight of a vertex in the wind speed graph is defined as the average wind speed in the corresponding location. To address the investigated optimization problems, we use the combinatorial branch-and-bound approach called the Russian Doll Search (^{Trukhanov et al., 2013}).

In the first set of experiments, we consider all the 201 locations to be the potential wind farm sites, independent on the attractiveness of their wind speed profile. Table 1 summarizes the results of these experiments. The maximum clique in this case consists of six vertices that correspond to the locations as follows (with their average speeds in parentheses): Mendoza (3.8 m/s), Santa Ana (3.7 m/s), Colquechaca (2.8 m/s), Taquiri (1.9 m/s), Tariquia (1.3 m/s), and El Puente (0.4 m/s). The maximum weight clique has five vertices, namely, Huacullani (6.9 m/s), Redencion (4.9 m/s), Robore (4.3 m/s), Santa Ana (3.7 m/s), and Chilcara (2.7 m/s). Evidently, some of the locations suggested by these solutions (especially in the unweighted case) are unacceptable due to their rather low average wind speed. The maximum weights of the 2-plex and 3-plex models yield slightly highly attractive solutions. Particularly, the six sites selected by the maximum weight 2-plex solution have the average speeds of 2.8, 3.8, 4.5, 6.0, 6.4, and 8.1 m/s, respectively, with an overall average of 5.25 m/s. Figure 7 illustrates the monthly average wind speeds for these locations in comparison with the locations included in the optimal solutions of the other considered problems (i.e., weighted and unweighted), as well as all the 201 locations (denoted by “Bolivia” in the plot). Noticeably, the maximum weight 2-plex solution is relatively attractive with regard to the overall wind speed average and the balanced wind speeds over time.

Tab.1 Summary of the results for the entire wind speed graph

Solution	Number of vertices	Average speed (m/s)
Wind speed graph	201	2.70
Max clique	6	2.36
Max weight clique	5	4.53
Max 2-plex	9	2.22
Max weight 2-plex	6	5.25
Max 3-plex	12	2.67
Max weight 3-plex	9	4.60

Fig.7 Average monthly wind speeds for the maximum clique, 2-plex, and 3-plex and their weighted versions

Full size|PPT slide

Although the results of the investigated case are rather encouraging, we can further improve them by disregarding the locations that are clearly unattractive due to their low average wind speeds. By performing such a feasibility study, we only have 39 locations to consider for placing the wind power plants with the average wind speeds of more than 4 m/s. (The complete list of locations, their geographical coordinates, and average wind speeds are presented in Table A1 of Appendix) Subsequently, we proceed to solving the considered weighted optimization problems of this reduced wind speed graph (hereinafter referred to as the feasible wind speed graph). Solving the maximum weight clique problem in this graph yields an optimal solution consisting of only two sites, that is, Villa Puni (5.98 m/s) and Calamarca (8.12 m/s), with an overall average wind speed of 7.05 m/s. The maximum weight 2-plex solution adds two locations, that is, Chorocona (6.19 m/s) and Tacagua (8.12 m/s), to the maximum weight clique solution. Similarly, the maximum weight 3-plex solution adds two sites, namely, Huaraco (5.66 m/s) and Tinquipaya (4.92 m/s). Table A1 summarizes the corresponding results. Figure 8 shows the maximum weight 3-plex solution on a geographical map, and Fig. 9 presents the plot of the average monthly wind speeds for the optimal solutions obtained for the weighted versions of all the considered optimization problems of the reduced wind speed graph. From the figure, all the weighted solutions considerably outperform the overall average. In addition, although the maximum weight clique solution seems to be superior with regard to the average monthly wind speeds, the solution only consists of two locations and may not be robust in the long run. Meanwhile, the maximum weight 3-plex solution includes a further geographically diverse set of six locations.

Tab.2 Summary of the results for the feasible wind speed graph

Solution	Number of vertices	Average speed (m/s)
Feasible wind speed graph	39	5.19
Max weight clique	2	7.05
Max weight 2-plex	4	7.10
Max weight 3-plex	6	6.50

Fig.8 Maximum 3-plex solution for the feasible wind speed graph

Full size|PPT slide

Fig.9 Average monthly wind speeds for the maximum weight clique, 2-plex, and 3-plex in the reduced wind speed graph

Full size|PPT slide

Conclusions

This study presents a network-based approach for determining the optimal locations for wind farms among the given sites on the basis of the wind speed information available for each site. We conclude that the network models provide a convenient, intuitive, visual description of wind power systems. On the basis of the results, the weighted-plex approach seems to be particularly useful for balancing the energy output and wind speed variability.

One of the possible future research directions to explore is to find other clique relaxations, such as s-defective clique and \gamma-quasiclique (^{Pattillo et al., 2013}), as alternative models for selecting useful wind farm locations. Considering the fractional objective function, which would maximize the energy output per dollar invested, could also be interesting. Given a simple undirected graph G=(E,V), where each vertex i\in V is assigned two nonnegative rational weights, a_i and b_i, the maximum ratio clique problem (MRCP) is to find an inclusion-wise maximal clique C in G that maximizes the quantity {\displaystyle {\sum }_{i\in C}{{\displaystyle a}}_i}/{\displaystyle {\sum }_{i\in C}{{\displaystyle b}}_i} (^{Sethuraman and Butenko, 2015}). Moreover, the proposed approach can be extended to other types of renewable energy sources, such as solar. Generally, the renewable sources must be optimally integrated into a broad power grid. Hence, a combination of all available types of energy sources rather than an independent one must be considered (^{Jaramillo et al., 2004}). However, the corresponding optimization problems in this case become increasingly complex; therefore, effective heuristic algorithms may be necessary (e.g., ^{Pei et al. (2017)} and ^{Yang et al. (2018)}).

Acknowledgments

We would like to thank the anonymous reviewers for their insightful comments. The partial support of the Ministny of Education of Bolivia Texas A&M Energy Institute is also gratefully acknowledged.

References

1 Abello J, Pardalos P M, Resende M G C (1999). On maximum clique problems in very large graphs. In: Abello J, Vitter J, eds. External Memory Algorithms and Visualization. Providence: American Mathematical Society

2 Archer C, Jacobson M (2005). Evaluation of global wind power. Journal of Geophysical Research, 110: 148–227

3 Archer C L, Jacobson M Z (2007). Supplying baseload power and reducing transmission requirements by interconnecting wind farms. Journal of Applied Meteorology and Climatology, 46: 1701–1717

4 Balasundaram B, Butenko S, Hicks I V (2011). Clique relaxations in social network analysis: The maximum k-plex problem. Operations Research, 59(1): 133–142

5 Bañuelos-Ruedas F, Rios-Marcuello S, Camacho C Á (2011). Methodologies used in the extrapolation of wind speed data at different heights and its impact in the wind energy resource assessment in a region. In: Suvire G O, eds. Wind Farm – Technical Regulations, Potential Estimation and Siting Assessment. Rijeka: InTech

6 Boginski V, Butenko S, Pardalos P M (2003). Modeling and optimization in massive graphs. In: Pardalos P M, Wolkowicz H, eds. Novel Approaches to Hard Discrete Optimization. Providence: American Mathematical Society

7 Boginski V, Butenko S, Pardalos P M (2006). Mining market data: A network approach. Computers & Operations Research, 33: 3171–3184

8 Degeilh Y, Singh C (2011). A quantitative approach to wind farm diversification and reliability. International Journal of Electrical Power & Energy Systems, 33: 303–314

9 Drake B, Hubacek K (2007). What to expect from a greater geographic dispersion of wind farms? A risk portfolio approach. Energy Policy, 35: 3999–4008

10 Garey M, Johnson D S (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman and Co

11 GeoBolivia (2008). Mapa eolico republica de Bolivia. https://geo.gob.bo/geonetwork/srv/spa/catalog.search#/metadata/f1ea9466-7b18-4f69-92ea-b625a3e4e6ce, 2018-11-11

12 Global Times (2017). China’s wind power capacity continues to grow. http://www.globaltimes.cn/content/1030911.shtml, 2018–2-27

13 Grothe O, Schnieders J (2011). Spatial dependence in wind and optimal wind power allocation: A copula based analysis. Energy Policy, 39: 4742–4754

14 Jacobson M (2009). Review of solutions to global warming, air pollution, and energy security. Energy & Environmental Science, 2: 148–173

15 Jaramillo O, Borja M, Huacuz J (2004). Using hydropower to complement wind energy: A hybrid system to provide firm power. Renewable Energy, 29(11): 1887–1909

16 Kahn E (1979). The reliability of distributed wind generators. Electric Power Systems Research, 2: 1–14

17 Liu S, Jian J, Wang Y, Liang J (2013). A robust optimization approach to wind farm diversification. International Journal of Electrical Power & Energy Systems, 53: 409–415

18 Mantegna R N, Stanley H E (2000). An Introduction to Econophysics: Correlations and Complexity in Finance. Cambridge: Cambridge University Press

19 McElroy M B, Lu X, Nielsen C P, Wang Y (2009). Potential for wind-generated electricity in China. Science, 325(5946): 1378–1380

PMID

20 Milligan M (2000). Optimizing the geographic distribution of wind plants in Iowa for maximum economic benefit and reliability. Wind Engineering, 24: 271–290

21 Milligan M, Artig R (1999). Choosing wind power plant locations and sizes based on electric reliability measures using multiple-year wind speed measurements. US Association for Energy Economics Annual Conference

22 Novoa C, Jin T (2011). Reliability centered planning for distributed generation considering wind power volatility. Electric Power Systems Research, 81(8): 1654–1661

23 Pardalos P M, Rebennack S, Pereira M V F, Iliadis N A, Pappu V (2013). Handbook of Wind Power Systems. New York: Springer

24 Pattillo J, Youssef N, Butenko S (2012). Clique relaxations in social network analysis. In: Thai M T, Pardalos P M, eds. Handbook of Optimization in Complex Networks: Communication and Social Networks. New York: Spinger

25 Pattillo J, Youssef N, Butenko S (2013). On clique relaxation models in network analysis. European Journal of Operational Research, 226: 9–18

26 Pei J, Liu X B, Fan W J, Pardalos P M, Lu S J (2017). A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers. Omega,

27 Piacquadio M, De la Barra A (2014). Multifractal analysis of wind velocity data. Energy for Sustainable Development, 22: 48–56

28 Roques F, Hiroux C, Saguan M (2010). Optimal wind power deployment in Europe – a portfolio approach. Energy Policy, 38: 3245–3256

29 Sethuraman S, Butenko S (2015). The maximun ratio clique problem. Computational Management Science, 12: 197–218

30 Soder L (2004). Simulation of wind speed forecast errors for operation planning of multiarea power systems. In: Proceedings of the 8th International Conference on Probabilistic Methods Applied to Power System, Ames, Iowa. IEEE: 723–728

31 Takle G, Lundquist J (2010). Wind turbines on farmland may benefit crops. https://www.ameslab.gov/node/8364

32 Touma J (1977). Dependence of the wind profile power law on stability for various locations. Journal of the Air Pollution Control Association, 27: 863–866

33 Trukhanov S, Balasubramaniam C, Balasundaram B, Butenko S (2013). Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations. Computational Optimization and Applications, 56: 113–130

34 Vaughan E, Kelley P (2016). U.S. number one in the world in wind energy production. Washington, DC: American Wind Energy Association

35 Verma A, Buchanan A, Butenko S (2015). Solving the maximum clique and vertex coloring problems on very large sparse networks. INFORMS Journal on Computing, 27: 164–177

36 Yang T, Fu C, Liu X, Pei J, Liu L, Pardalos P M (2018). Closed-loop supply chain inventory management with recovery information of reusable containers. Journal of Combinatorial Optimization, 35(1): 266–292