License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.55
URN: urn:nbn:de:0030-drops-111766
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11176/
Gritzbach, Sascha ;
Ueckerdt, Torsten ;
Wagner, Dorothea ;
Wegner, Franziska ;
Wolf, Matthias
Engineering Negative Cycle Canceling for Wind Farm Cabling
Abstract
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 cable 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 [Sascha Gritzbach et al., 2018]. 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 under two 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.
BibTeX - Entry
@InProceedings{gritzbach_et_al:LIPIcs:2019:11176,
author = {Sascha Gritzbach and Torsten Ueckerdt and Dorothea Wagner and Franziska Wegner and Matthias Wolf},
title = {{Engineering Negative Cycle Canceling for Wind Farm Cabling}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {55:1--55:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-124-5},
ISSN = {1868-8969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11176},
URN = {urn:nbn:de:0030-drops-111766},
doi = {10.4230/LIPIcs.ESA.2019.55},
annote = {Keywords: Negative Cycle Canceling, Step Cost Function, Wind Farm Planning}
}
|
Keywords: |
|
Negative Cycle Canceling, Step Cost Function, Wind Farm Planning |
|
Collection: |
|
27th Annual European Symposium on Algorithms (ESA 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
06.09.2019 |
