CEO @ Traverse
.png)
Product
•
Sep 1, 2021
🚀🚀 WindDesk Discover is Now Available Globally!
WindDesk Discover, a free tool to prospect for wind farms, is now available globally.
CEO @ Traverse
At Traverse we perform micro-siting for wind farms by using IRR, NPV or LCOE as the target optimization variables. If you look at our landing page, it says we help project developers increase greenfield IRR by 0.5%. To fulfill this promise, we have to perform three key tasks.
These 3 topics are intertwined as every time you move a turbine it affects the optimality of all other turbines in a recursive cascade.
This article is a showcase on how we perform B, roads and foundation CAPEX optimization. In particular how we find the best ways to build roads up a mountain. We use two key algorithms in computer science: A* Search and Minimum Spanning Trees (MST) and scaled it to work on up to 500 turbines and a 100km by 100km boundary.
The example wind farm we are working on today has 4 turbines, 1 access point and 2 substations in the Lingayen Gulf of the Philippines. It is situated in complex terrain for the sake of giving this example.
Let’s look at the simplest case of one road connection between an access point and the very first turbine. What is the cheapest way to connect "Access Road" with Turbine 1 (T1)? The road specifications must fulfill:
A* search is an extension of Dijkstra's famous path finding algorithm and is used in many applications to find the shortest path between any two points on a graph. Given two end nodes, the cost of the edges in between are summed and compared in a clever manner. The combination of edges that result in the lowest cost is the shortest / lowest-cost path.
Under certain conditions, you can mathematically prove that A* will provide a globally optimal path between two nodes. A detailed explanation of A* can be found here and here. The video below shows how it works in the trivial case of a small maze:
A visualization of the A* path-finding algorithm, Wgullyn, CC BY-SA 4.0 via Wikimedia Commons
The main attractiveness for using A* is its guarantee to be able to find the lowest cost path with reasonable efficiency (i.e. it won’t take forever). There are many path finding algorithms that are much faster but sacrifice global optima and can only provide local optima. However, A* takes up a very large amount of memory as it needs to keep track of all the nodes it has visited previously in case it needs to backtrack and try new paths.
The Cost of an Edge
In the simplest case, the “cost of an edge” in A* is its distance. However, in the case of wind farm roads, we have to adopt the cost to be a combination of all the following in order of priority:
The rejection criteria are simply edges with infinitely high costs. As for the cost criteria for one edge, it is:
\[\textnormal{Cost Edge} = \textnormal{Dist} * $/m + \textnormal{Excv Vol} * $/m^3\]
The cost of the whole path is the line integral over the scalar field (elevation, geotechnical condition etc.):
\[\textnormal{Cost Path} = \int_{path} \textnormal{Cost Edge}\,dl \]
The distance is simple but how do we know the excavation area and volume? We take at every 50m intervals, a cross section (perpendicular to the direction of the road) of the elevation and standard benching polygons are drawn to estimate the area of earth required to be cut or filled.
During the benching we can apply concepts such as:
By applying these concepts, we get different costs at very high resolution. We then apply the equation above to get each edge’s cost and the A* algorithm evaluates a) which edge is cheaper and b) which combination of edges are cheaper and thereby moves the investigative frontier forward. An example AutoCAD drawing automatically produced by the system is shown below:
The “Graph” of a Wind Farm
The “graph” of a potential wind farm is simply a regularly sized 2D array like a chess board where every cell has quantitative values such as:
The software engineering to manage this graph could get very complicated for large projects or late stage projects that have very high resolution data (such as drone acquired elevation data and geotechnical maps). A* search is computationally intensive and it is preferred if the graph is placed on fast RAM that is closer to the processing cores rather than copied back and forth from a slower hard disk. The largest project we have done to date is a 1.2GW project in India with 218 turbines where the investigative space spanned a 40km by 40km area. Each cell had a 5m resolution which means there are 64,000,000 cells, on top of each of which had 5 quantitative values.
Some of the the strategy we use to manage such large contiguous data is to:
The animation below shows and explains the actual motion of our A* implementation for an actual pair of a turbine point and an access point. This has been slowed down by 20 times. In practice, the whole path-finding takes <1 second for a short distance.
Looking at our reference wind farm with 4 turbines and 1 access point (total 5 points), we want to connect all 5 points continuously in most cases. For N turbines there are:
\[\textnormal{Ways to Pair All Turbines} = n^{n-2}\]
The above formula is called Cayley's formula and the animation below shows all \(5^{5-2} = 125\) possible pairs for our wind farm. Some of them are of course nonsensical intuitively and can be easily dis-regarded as not a plausible candidate.
We now have to apply A* search (what we described in section 1 of this article, the optimal path between two points) to \(^5C_2\) = 10 unique pairs. We can then re-use these 10 pairs and apply them on the 125 combinations. The order of combinations and unique pairs grow at a very fast pace as the number of turbines increase:
It is not possible in human time to calculate all the combinations due to the double exponent nature of Cayley's formula. We use the concept of Minimum Spanning Trees to reduce this to reasonable calculation times.
The Minimum Spanning Tree is the set of edge combinations that results in the lowest cost. For example, Prim's algorithm (a type of MST algorithm) is a well-known algorithm that finds this MST in approximately \(n^2 * \log n\) time, down from the exponential brute force time of \(n^{n-2}\). The table below now has an additional column on how many calculations this is reduced by:
Calculations on the magnitude of 10,000 to 100,000 is manageable with modern hardware.
The total number of points in a wind farm is not just the turbines. In addition there are:
Existing Roads and Pruning the Forest
Existing roads add hundreds of thousands of points to the forest. At any point in time, we would like to upgrade existing roads for both cost and permitting efficiency. Every point along an existing road is the same as a turbine point. Except that existing road points are an optional connection whereas turbine points are a compulsory connection. Our A* search "weaves" in and out of the existing roads as necessary ensuring that all existing roads fulfill slope and turning radii requirements while also optimizing for low excavation costs.
There are several strategies to reduce the total number of points such as:
Road Forks and The Steiner Tree
In real life, turbines are not always connected directly, we always use road forks. In the image below, we can connect \(ABCD\) directly. However, the introduction of points \(S_1\) and \(S_2\) results in a lower cost tree obviously. In an area like our wind farm, there are an infinite number of candidate points \(S_n\) that you can add to see which combination of them might reduce the total cost of your tree.
The identification of the best set of points S such that it results in the lowest cost tree is called the Minimum Steiner Tree Problem. Unfortunately this problem is though to be NP-Hard or its NP class is not known, which in ultra simplified terms means it is mathematically provable that no good algorithm exists that can solve the full problem. However, it is a research level topic to find estimations of potential Steiner points. Here at this stage, the WindDesk system uses a completely human in the loop approach where a civil engineer just "litters the landscape" with Forking Point Clouds. They can draw zones of possible forking areas and let the combination of the MST and A* search evaluate the points in these zones to see if they should bifurcate or trifurcate to eventually produce the minimum cost road network.
When the A* search and MST is put together, this is how it looks like for 4 turbines and an access point:
Because electrical cables are typically buried along the inter-connecting roads (so that they can be dug out and maintained in the future if necessary), optimizing the roads to reduce CAPEX costs inadvertently affects revenue in terms of electrical losses in the inter-array medium voltage cables! Going back to our equation:
\[\textnormal{Cost Edge} = \textnormal{Dist} * $/m + \textnormal{Excv Vol} * $/m^3\]
The $/m cost associated with distance can now be further expanded to not just the physical cost of the cables but the Net Present Value of electrical loss * electricity price. In this way the optimization will attempt to heavily bias towards the shortest possible paths while still fulfilling criteria such as slope and turning radii.
There are multiple other considerations with regards to inter-array electrical cable optimization which we will soon publish in another post.
Traverse provides IRR/LCOE based micro-siting, wind analysis, energy yield assessments, wind engineering and owner's engineer services. We have done over 10GW projects in various stages for IPPs, utilities and developers alike. Check out our website or drop me a line at thet@traverse.ai .
Check out WindDesk Discover where you can prospect for a wind farm with over 10 GIS layers and a layout generator.
Check out our free measurement site monitoring service WindDesk Monitor.
Enjoyed this post? Receive the next one in your inbox!
