KIT | KIT-Bibliothek | Impressum | Datenschutz

Engineering Negative Cycle Canceling for Wind Farm Cabling

Gritzbach, Sascha ORCID iD icon 1; Ueckerdt, Torsten 1; Wagner, Dorothea 1; Wegner, Franziska 1; Wolf, Matthias ORCID iD icon 1
1 Karlsruher Institut für Technologie (KIT)


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). ... mehr

Verlagsausgabe §
DOI: 10.5445/IR/1000104999
Veröffentlicht am 15.01.2020
DOI: 10.4230/LIPIcs.ESA.2019.55
Zitationen: 4
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2019
Sprache Englisch
Identifikator ISBN: 978-3-9597712-4-5
ISSN: 1868-8969
KITopen-ID: 1000104999
HGF-Programm 37.06.01 (POF III, LK 01) Networks and Storage Integration
Erschienen in 27th Annual European Symposium on Algorithms (ESA 2019). Hrsg.: Michael A. Bender
Veranstaltung 27th Annual European Symposium on Algorithms (ESA 2019), Garching bei München, Deutschland, 09.09.2019 – 11.09.2019
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten Art.-Nr.: 55
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 144
Schlagwörter Negative Cycle Canceling, Step Cost Function, Wind Farm Planning
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page