| dc.description.abstract | The current work presents an in-exact solution method used to identify feasible, and less costly inter-array cable layout for offshore wind farms. The solution method developed has been built considering the interests of wind farm developers in mind, and to support them in the planning of large offshore wind projects. The objective of the current study is to develop a fast heuristic based algorithm able to find good (less costly), feasible solution, with a small optimality gap. We are given the positions of the turbines, obstacles, and substations. The optimization problem is to find a cable layout such that there is a unique path from each turbine to one of the substations. All the turbines are connected in a series connection on a cable having a pre-defined capacity limitation. There are few additional constraints such as to prevent two or more cables from crossing each other, and cables from entering any restricted areas in the sea bed. This problem is quite similar to the wellknown Capacitated Minimum Spanning Tree (CMST) problem. The cable layout problem has been proved to be NP hard, thus, an exact algorithm is likely to have a running time that is an exponential function of the size of the input. Most of the available exact models require fast computers, and hours of computation time to find an optimal solution and still, in large instances of the problem, an optimal solution is not achieved. Although our heuristic does not guarantee an optimal solution, it has the ability to reveal good, feasible solutions in short time frame for large as well as small instances. We have implemented the heuristic in Java, and used in-built as well as customized data structures for improving the running time of the algorithm. We have tested our solution method on 8 real wind farm instances with total number of turbines ranging from 30 to 160. We have compared the results of our heuristic with the optimal solutions available for 4 wind farm instances. We achieved near optimal solutions (<1%) in most of the instances. The solution method includes a construction heuristic, which is a modified version of a well established greedy heuristic for CMST problem called Esau Williams’ heuristic. We have adapted this heuristic by introducing a procedure to find a crossing free layout, and also used a shape factor in the heuristic function to improve the solution quality. We have utilized a multiple node exchange neighborhood structure, and used it in a local search framework. The local search method improves the solution quality, and finds locally optimal solutions. In the end , we have used the algorithm on some of the larger instances with more than 100 turbines. These instances are practically impossible to solve using exact methods. We have compared our heuristic results in these instances with the actual installed layout. | en_US |
