Balanced and unbalanced networks in offshore wind farms
D. Cazzaroa,b,∗ , D. F. Kozab , D. Pisingera
a DTU Management, Technical University of Denmark, Kgs. Lyngby, Denmark

dacaz@dtu.dk, dapi@dtu.dk

b Vattenfall BA Wind, Kolding, Denmark

davidfranz.koza@vattenfall.com∗ Corresponding author

Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

April 12, 2022
Keywords: network, cables, routing, obstacles, wind farm

1

INTRODUCTION

The cable routing problem in offshore wind farms consists in designing a transportation network
to transfer the electricity generated by wind turbines to a central hub (substation) which isconnected to shore. The submarine electrical cables are expensive, comprising about 5% of thetotal capital expenditure (CAPEX) of an offshore wind farm (BVG Associates, 2019). For thisreason, the optimization of cable routing has been investigated in literature, with the objectiveof finding the cable routing of minimum cost (Bauer & Lysgaard, 2015).
One important constraint for the cable routing problem is that cable crossings are forbidden,
due to the increased installation costs and difficult maintenance. Another constraint is thatthe routing must avoid all obstacles in the wind farm sea area. These obstacles may be due tounsuitable seabed conditions, to ship wrecks, and to regulations, such as fishing corridors andnatural reserves. Cables must not cross any of these areas for the routing solution to be feasible.
A cable routing allows only one electrical cable to exit from each turbine, and multiple cables
to enter turbines and the substation. Each sub-tree leaving the substation is denoted a rootbranch. A property of cable routing solution is related to how many turbines are present in eachroot-branch. If the number of turbines in each root-branch is the same or differs at most by one,we denote the solution balanced.
While literature mainly has focused on the general unbalanced cable routing problem, inindustry the wind farm developers favor balanced cable routing solutions. As the solutions tothe balanced problem are a subset of the solutions to the unbalanced formulation, unbalanced
solutions may be cheaper than balanced. The drawbacks of the unbalanced routing are related tothe additional electrical equipment cost that needs to be installed in the offshore substation. In
particular, the cost of installing a spare Offshore Transformer Module (OTM) on the substation
is about 5M€ (Walling & Ruddy, 2005), depending on its rating. In the case of a balanced cablerouting, a single type of transformer is needed as spare in case of failures (online spare), since thetransformer share the same electrical loads and can substitute any of the transformers in case offailure. For the unbalanced case instead, different transformer ratings and different spares would
be needed, making this option less attractive in the industry.
The contributions of this work are:
TRISTAN XI Symposium

Original abstract submittal

D. Cazzaro, D. F. Koza, D. Pisinger

2• We develop a matheuristic that uses different neighborhoods to optimize the cable routing
problem, for both balanced and unbalanced networks.
• We present a technique to handle obstacles in the cable routing based on a visibility graph.
• We quantify the difference between balanced and unbalanced cable routing on a set ofrealistic wind farm instances, taking into account the additional OTM costs.

2METHODOLOGY

We use a matheuristic to solve the cable routing problem for both the balanced and the unbalanced cases. The technique is based on the work of Cazzaro & Pisinger (Submitted 2021). As afirst pre-processing step, we compute and store all the shortest paths using a so-called visibility
graph in order to avoid obstacles. Then we use a technique called Sweep to generate an initialsolution without crossings. Finally, we use a Large Neighborhood Search (LNS) to improve thecable routing, using a mix of heuristic and exact methods. We outline in the following sections
an approach to deal with obstacles in the wind farm, the strategies used in the heuristic, andthe changes needed to consider the two network designs.

2.1

Obstacles

Let V be the nodes of turbines and of the substation in the wind farm that we want to connect
with electrical cables to transport the generated electricity. There are O(V 2 ) possible connections
to be used in the network.
Due to obstacles, some of these direct connections will cross the obstacles in the wind farm,and thus cannot be used. We are interested in computing the shortest paths from each node to
every other node by routing each connection around obstacles. To this end, we use a visibility
graph, similarly to Yi et al. (2019). A visibility graph contains only edges that have visible
nodes, meaning that two nodes have a direct connection that does not cross any obstacle. We
first add to the visibility graph all the nodes of V plus all the nodes that define obstacles (aspolygons). Then, we use the Dijkstra algorithm to compute the shortest paths from each node to
all others. The Dijkstra algorithm is called V times, and we store V 2 shortest paths in an ad-hoc
data structure. The advantage of this procedure is threefold. First, it can be computed in a
pre-processing step, so it does not impact the subsequent optimization time. Second, it allows us
to consider the whole solution space of the problem and possibly reach better solutions. Third, it
can be adopted by existing optimization techniques that do not include obstacles with minimaloverhead.

2.2

Initial solution

We use a Sweep algorithm to generate an initial solution without cable crossings. The ideaof Sweep takes inspiration from Gillett & Miller (1974), which used it for the Vehicle Routing
Problem. In Sweep, we divide the turbines in groups, that are then connected together withthe substation. These groups are formed by considering the angle that turbines form with thesubstation. The turbines are thus partitioned in sectors around the substation, making it unlikelythat crossings are generated between different groups. Thanks to the visibility graph, obstacles
are accounted for when forming groups. The Minimum Spanning Tree is then computed for eachgroup, using the Prim-Dijkstra algorithm, so that the turbines are connected together with thesubstation. For the balanced case, the groups will be formed with the same amount of turbines,
while for the unbalanced case a wider set of partitions can be considered. In our implementation,
the Sweep is implemented as a multi-start procedure: we try many different partitions and keep
the one with lowest cost.
TRISTAN XI Symposium

Original abstract submittal

D. Cazzaro, D. F. Koza, D. Pisinger

2.33Matheuristic

After the Sweep procedure, we use Large Neighborhood Search (LNS) to improve the solution.
The method operates on neighborhoods of increasing complexity and uses both heuristic andexact methods to repair solutions.
• Swap: this method exchanges two turbines between a pair of root-branches to improve thecable routing. After the move, we recompute the Minimum Spanning Tree to connect theturbines in each group and we re-evaluate the solution. If the cost improves, we move tothe new solution, otherwise we revert the root-branches to the original configuration andcontinue the search. For the balanced network, the Swap move is symmetric to preserve
the number of turbines in each root-branch. For the unbalanced network, instead, we canconsider an additional move: a single turbine can move from its own branch to another.
• Double Swap: we extend the Swap move by considering two moves at a time, before reevaluating the solution. In this way, we allow a temporary worsening of the solution in thefirst move to reach a better solution with the second swap. In addition, we can perform theDouble Swap between two branches but also among three of them, which helps to improve
the solution.
• Cycle Swap: we use a MIP formulation to allow the exchange of turbines between several
branches at a time, in particular for the balanced case. We compute a move matrix and an
associated cost vector for each turbine. This vector estimates the cost of moving a turbine
to its best improvement in a nearby branch. Each turbine leaving a branch needs to be
replaced by another one to maintain a balanced solution: this makes the formulation of
the move matrix totally unimodular, which can be solved efficiently with a LP solver.
• Re-partition: we use a MIP formulation of the cable routing problem to improve thesolution. Differently from usual exact approaches in literature, we do not solve the wholecable routing problem but only a subset, limited to two branches at a time. In this way,
the MIP model is small and can be solved to optimality in a short time. For the balanced
case, we add the balancing constraint to the MIP, which is omitted for the unbalanced
network.
All different neighborhoods explored in the LNS contribute to improving the initial solution
obtained with the Sweep heuristic. For more details on the LNS heuristic, we refer to Cazzaro& Pisinger (Submitted 2021).

3RESULTS AND DISCUSSION

We compare the two network designs on a set of synthetic instances published in Cazzaro &Pisinger (2022). These 10 instances have a high number of turbines to connect together andmany obstacles in the area, as in real wind farms. We assume a set of two cables is available toconnect the turbines, based on Das & Cutululis (2017). The first cable costs 240€/m and cansupport 6 turbines (of 10MW capacity), while the second cable costs 336€/m and can support 8turbines. As mentioned in the first section, the total cost of an additional OTM is about 5M€,
including installation (Walling & Ruddy (2005)).
We quantify the difference of costs between the balanced cable routing and the unbalanced
case, taking into account the cost due to one additional OTM. We report the results of the two
cable routing networks in Table 1.
Considering the cable costs alone, the unbalanced network reaches lower cost solutions in all
the tested instances. When we add the cost of an extra OTM, though, the situation is reversed:
because of the reduced installation costs, the balanced case is strongly preferable. Indeed, this is
TRISTAN XI Symposium

Original abstract submittal

D. Cazzaro, D. F. Koza, D. Pisinger

4

Table 1 – Comparison of cable routing costs for balanced and unbalanced networks on the synthetic
instances. The cheaper the better.
InstanceAB
C
D
EF
G
H
IJ

Unbalanced
(M€)
20.79
54.08
51.83
96.07
71.98
94.09
75.41
114.1
202.51
127.2

Unbalanced+ OTM (M€)
25.79
59.08
56.83
101.07
76.98
99.09
80.41
119.10207.51132.20

Balanced
(M€)
21.62
54.74
53.49
97.14
74.36
95.43
78.15
117.41205.9
130.02

Delta(M€)
4.17
4.34
3.34
3.93
2.62
3.66
2.26
1.69
1.61
2.18

Delta
(%)
16.17
7.35
5.88
3.89
3.40
3.69
2.81
1.42
0.78
1.65

due to the relatively low savings between the two network designs, which are not large enough tooffset the additional electrical components. This is the main reason why the balanced network ispreferred by wind farm developers, and also a motivation to further study this network option.
Even if the cost of an OTM was reduced to 3 M€ instead of 5 M€, all but instances I and J
would still be more economic when using a balanced routing.

4CONCLUSIONSIn the presented work, we quantified the cost difference between two networks: the balanced andthe unbalanced cable routing. In addition, the visibility graph technique we proposed can beapplied in general to routing problems with obstacles. As an example, we generalized the wellknown Sweep algorithm to operate on visibility graphs, which can be used in any transportation
problem with obstacles. Advanced matheuristic using neighborhoods of increasing complexity
shows very promising results. In Cazzaro & Pisinger (Submitted 2021) it has been shown that
it is on average only 0.01% more expensive than MIP solutions. The matheuristic can easily
be generalized to Hamiltonian-cycle branches. Finally, developed methods are applicable to any
kind of transportation problems where the individual strings leaving the hub must be balanced.

References
Bauer, Joanna, & Lysgaard, Jens. 2015. The offshore wind farm array cable layout problem: a planar
open vehicle routing problem. Journal of the Operational Research Society, 66(3), 360–368.
BVG Associates. 2019. Guide to an offshore wind farm: updated and extended. https://www.
thecrownestate.co.uk/media/2861/guide-to-offshore-wind-farm-2019.pdf.
Cazzaro, Davide, & Pisinger, David. 2022. Variable neighborhood search for large offshore wind farmlayout optimization. Computers & Operations Research, 138, 105588.
Cazzaro, Davide, & Pisinger, David. Submitted 2021. Balanced cable routing for offshore wind farms
with obstacles. Networks.
Das, Kaushik, & Cutululis, Nicolaos Antonios. 2017. Offshore Wind Power Plant Technology Catalogue- Components of wind power plants, AC collection systems and HVDC systems. Tech. rept. DTU.
Gillett, Billy E., & Miller, Leland R. 1974. A Heuristic Algorithm for the Vehicle-Dispatch Problem.
Operations Research, 22, 340–349.
Walling, R. A., & Ruddy, T. 2005. Economic optimization of offshore wind farm substations and collectionsystems. Pages 396–402 of: 5th international workshop on large scale integration of wind power andtransmission networks for offshore windfarms.
Yi, Xiao, Scutariu, Mircea, & Smith, Kenneth. 2019. Optimisation of offshore wind farm inter-arraycollection system. IET Renewable Power Generation, 13(11), 1990–1999.

TRISTAN XI Symposium

Original abstract submittal