  In a wind farm turbines convert wind energy into electrical energy. The
generation of each turbine is transmitted, possibly via other turbines, to a
substation that is connected to the power grid. On every possible
interconnection there can be at most one of various different cable types. Each
type comes with a cost per unit length and with a capacity. Designing a
cost-minimal cable layout for a wind farm to feed all turbine production into
the power grid is called the Wind Farm Cabling Problem (WCP).
  We consider a formulation of WCP as a flow problem on a graph where the cost
of a flow on an edge is modeled by a step function originating from the cable
types. Recently, we presented a proof-of-concept for a negative cycle
canceling-based algorithm for WCP [14]. We extend key steps of that heuristic
and build a theoretical foundation that explains how this heuristic tackles the
problems arising from the special structure of WCP.
  A thorough experimental evaluation identifies the best setup of the algorithm
and compares it to existing methods from the literature such as Mixed-integer
Linear Programming (MILP) and Simulated Annealing (SA). The heuristic runs in a
range of half a millisecond to approximately one and a half minutes on
instances with up to 500 turbines. It provides solutions of similar quality
compared to both competitors with running times of one hour and one day. When
comparing the solution quality after a running time of two seconds, our
algorithm outperforms the MILP- and SA-approaches, which allows it to be
applied in interactive wind farm planning.
