Document Open Access Logo

Engineering Negative Cycle Canceling for Wind Farm Cabling

Authors Sascha Gritzbach , Torsten Ueckerdt , Dorothea Wagner , Franziska Wegner , Matthias Wolf

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.55.pdf
  • Filesize: 0.8 MB
  • 16 pages

Document Identifiers

Author Details

Sascha Gritzbach
  • Karlsruhe Institute of Technology, Germany
Torsten Ueckerdt
  • Karlsruhe Institute of Technology, Germany
Dorothea Wagner
  • Karlsruhe Institute of Technology, Germany
Franziska Wegner
  • Karlsruhe Institute of Technology, Germany
Matthias Wolf
  • Karlsruhe Institute of Technology, Germany

Funding

This work was funded (in part) by the Helmholtz Program Storage and Cross-linked Infrastructures, Topic 6 Superconductivity, Networks and System Integration, by the Helmholtz future topic Energy Systems Integration, and by the German Research Foundation (DFG) as part of the Research Training Group GRK 2153: Energy Status Data - Informatics Methods for its Collection, Analysis and Exploitation.

Acknowledgements

We thank our colleagues Lukas Barth and Marcel Radermacher for valuable discussions and Lukas Barth for providing a code interface for simultaneous MILP-solver experiments.

Cite As Get BibTex

Sascha Gritzbach, Torsten Ueckerdt, Dorothea Wagner, Franziska Wegner, and Matthias Wolf. Engineering Negative Cycle Canceling for Wind Farm Cabling. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.55

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Network flows
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Network optimization
Keywords
  • Negative Cycle Canceling
  • Step Cost Function
  • Wind Farm Planning

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. 4C Offshore Ltd. Hornsea Project Three Offshore Wind Farm, 2018. Accessed: 2018-08-15. URL: https://www.4coffshore.com/windfarms/hornsea-project-three-united-kingdom-uk1k.html.
  2. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network flows: theory, algorithms, and applications. Prentice Hall, Upper Saddle River, NJ [u.a.], 1993. Google Scholar
  3. Richard Bellman. On a Routing Problem. Quarterly of Applied Mathematics, 16:87-90, 1958. URL: https://doi.org/10.1090/qam/102435.
  4. Constantin Berzan, Kalyan Veeramachaneni, James McDermott, and Una-May O'Reilly. Algorithms for cable network design on large-scale wind farms. MSRP technical report, Massachusetts Institute of Technology, Cambridge, MA, USA, 2011. http://thirld.com/files/msrp_techreport.pdf, Accessed: 2016-01-04.
  5. Boris V. Cherkassky and Andrew V. Goldberg. Negative-cycle detection algorithms. Mathematical Programming, 85(2):277-311, June 1999. URL: https://doi.org/10.1007/s101070050058.
  6. Ouahid Dahmani, Salvy Bourguet, Mohamed Machmoum, Patrick Guerin, Pauline Rhein, and Lionel Josse. Optimization of the Connection Topology of an Offshore Wind Farm Network. IEEE Systems Journal, 9(4):1519-1528, 2015. URL: https://doi.org/10.1109/JSYST.2014.2330064.
  7. Mauricio C. de Souza, Philippe Mahey, and Bernard Gendron. Cycle‐based algorithms for multicommodity network flow problems with separable piecewise convex costs. Networks, 51(2):133-141, 2008. URL: https://doi.org/10.1002/net.20208.
  8. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269-271, December 1959. URL: https://doi.org/10.1007/BF01386390.
  9. Lester R. Ford, Jr. and Delbert R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, NJ, USA, 2010. Google Scholar
  10. Virginie Gabrel, Arnaud Knippel, and Michel Minoux. Exact solution of multicommodity network optimization problems with general step cost functions. Operations Research Letters, 25(1):15-23, 1999. URL: https://doi.org/10.1016/S0167-6377(99)00020-6.
  11. Andrew V. Goldberg and Tomasz Radzik. A heuristic improvement of the Bellman-Ford algorithm. Applied Mathematics Letters, 6(3):3-6, 1993. URL: https://doi.org/10.1016/0893-9659(93)90022-F.
  12. Andrew V. Goldberg and Robert E. Tarjan. Finding Minimum-cost Circulations by Canceling Negative Cycles. Journal of the ACM, 36(4):873-886, October 1989. URL: https://doi.org/10.1145/76359.76368.
  13. Donald Goldfarb, Jianxiu Hao, and Sheng-Roan Kai. Shortest Path Algorithms Using Dynamic Breadth-First Search. Networks, 21(1):29-50, 1991. URL: https://doi.org/10.1002/net.3230210105.
  14. Sascha Gritzbach, Torsten Ueckerdt, Dorothea Wagner, Franziska Wegner, and Matthias Wolf. Towards negative cycle canceling in wind farm cable layout optimization. In Proceedings of the 7th DACH+ Conference on Energy Informatics, volume 1 (Suppl 1). Springer, 2018. URL: https://doi.org/10.1186/s42162-018-0030-6.
  15. Longkun Guo and Peng Li. On the Complexity of Detecting k-Length Negative Cost Cycles. In Combinatorial Optimization and Applications, COCOA 2017, volume 10627 of Lecture Notes in Computer Science, pages 240-250. Springer International Publishing, 2017. URL: https://doi.org/10.1007/978-3-319-71150-8_21.
  16. Morton Klein. A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems. Management Science, 14(3):205-220, 1967. URL: https://doi.org/10.1287/mnsc.14.3.205.
  17. Sebastian Lehmann, Ignaz Rutter, Dorothea Wagner, and Franziska Wegner. A Simulated-Annealing-Based Approach for Wind Farm Cabling. In Proceedings of the Eighth International Conference on Future Energy Systems, e-Energy '17, pages 203-215, New York, NY, USA, 2017. ACM. URL: https://doi.org/10.1145/3077839.3077843.
  18. Sara Lumbreras and Andres Ramos. Optimal Design of the Electrical Layout of an Offshore Wind Farm Applying Decomposition Strategies. IEEE Transactions on Power Systems, 28(2):1434-1441, 2013. URL: https://doi.org/10.1109/TPWRS.2012.2204906.
  19. New York State Energy Research and Development Authority. New York State Offshore Wind Master Plan, 2017. Accessed: 2018-08-15. URL: https://www.nyserda.ny.gov/-/media/Files/Publications/Research/Biomass-Solar-Wind/Master-Plan/Offshore-Wind-Master-Plan.pdf.
  20. Adam Ouorou and Philippe Mahey. A minimum mean cycle cancelling method for nonlinear multicommodity flow problems. European Journal of Operational Research, 121(3):532-548, 2000. URL: https://doi.org/10.1016/S0377-2217(99)00050-8.
  21. Christos H. Papadimitriou. The complexity of the capacitated tree problem. Networks, 8(3):217-230, 1978. URL: https://doi.org/10.1002/net.3230080306.
  22. Tomasz Radzik and Andrew V. Goldberg. Tight bounds on the number of minimum-mean cycle cancellations and related results. Algorithmica, 11(3):226-242, March 1994. URL: https://doi.org/10.1007/BF01240734.
  23. Pedro Santos Valverde, António J. N. A. Sarmento, and Marco Alves. Offshore Wind Farm Layout Optimization - State of the Art. Journal of Ocean and Wind Energy, 1(1):23-29, 2014. Google Scholar
  24. WindEurope asbl/vzw. Wind in power 2017, 2018. Accessed: 2018-08-15. URL: https://windeurope.org/wp-content/uploads/files/about-wind/statistics/WindEurope-Annual-Statistics-2017.pdf.
  25. Menghua Zhao, Zhe Chen, and Frede Blaabjerg. Optimization of Electrical System for a Large DC Offshore Wind Farm by Genetic Algorithm. In Proceedings of NORPIE 2004, pages 1-8, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact