[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Siting renewable power generation assets with combinatorial optimisation

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

This paper studies the problem of siting renewable power generation assets using large amounts of climatological data while accounting for their spatiotemporal complementarity. The problem is cast as a combinatorial optimisation problem selecting a pre-specified number of sites so as to minimise the number of simultaneous low electricity production events that they experience relative to a pre-specified reference production level. It is shown that the resulting model is closely related to submodular optimisation and can be interpreted as generalising the well-known maximum coverage problem. Both deterministic and randomised algorithms are discussed, including greedy, local search and relaxation-based heuristics as well as combinations of these algorithms. The usefulness of the model and methods is illustrated by a realistic case study inspired by the problem of siting onshore wind power plants in Europe, resulting in instances featuring over ten thousand candidate locations and ten years of hourly-sampled meteorological data. The proposed solution methods are benchmarked against a state-of-the-art mixed-integer programming solver and several algorithms are found to consistently produce better solutions at a fraction of the computational cost. The physical nature of solutions provided by the model is also investigated, and all deployment patterns are found to be unable to supply a constant share of the electricity demand at all times. Finally, a cross-validation analysis shows that, except for an edge case, the model can successfully and reliably identify deployment patterns that perform well on previously unseen climatological data from historical data spanning a small number of weather years.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1–41 (2009). https://doi.org/10.1007/s12532-008-0001-1

    Article  MathSciNet  MATH  Google Scholar 

  2. Ageev, A.A., Sviridenko, M.I.: Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J. Comb. Optim. 6, 307–308 (2004). https://doi.org/10.1023/B:JOCO.0000038913.96607.c2

    Article  MathSciNet  MATH  Google Scholar 

  3. Apt, J.: The Spectrum of Power from Wind Turbines. J. Power Sources 169(2), 369–374 (2007). https://doi.org/10.1016/j.jpowsour.2007.02.077

    Article  Google Scholar 

  4. Badanidiyuru, A., Vondrák, J.: Fast algorithms for maximizing submodular functions. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’14, pp. 1497–1514. SIAM (2014). https://doi.org/10.5555/2634074.2634184

  5. Badger, J., Bauwens, I., Casso, P., Davis, N., Hahmann, A., Bo Krohn Hansen, S., Ohrbeck Hansen, B., Heathfield, D., Knight, J.O., Lacave, O., Lizcano, G., Bosch i Mas, A., Gylling Mortensen, N., Olsen, B.T., Onninen, M., Potter van Loon, A., Volker, P.: Global Wind Atlas 3.0 (2021). https://globalwindatlas.info/

  6. Baringo, L., Conejo, A.J.: Strategic wind power investment. IEEE Trans. Power Syst. 29(3), 1250–1260 (2014). https://doi.org/10.1109/TPWRS.2013.2292859

    Article  Google Scholar 

  7. Barman, S., Fawzi, O., Ghoshal, S., Gurpinar, E.: Tight approximation bounds for maximum multi-coverage. Math. Program. (2021). https://doi.org/10.1007/s10107-021-01677-4

    Article  Google Scholar 

  8. Berger, M., D.Radu, Fonteneau, R., Henry, R., Glavic, M., Fettweis, X., Du, M.L., Panciatici, P., Balea, L., Ernst, D.: Critical Time Windows for Renewable Resource Complementarity Assessment. Energy 198 (2020). https://doi.org/10.1016/j.energy.2020.117308

  9. Berger, M., Radu, D.: Algorithms for Max k-Multicover (2021). https://gitlab.uliege.be/smart_grids/public/maxk_multicover

  10. Bertsimas, D., Tsitsiklis, J.: Simulated annealing. Stat. Sci. 8(1), 10–15 (1993). https://doi.org/10.1214/ss/1177011077

    Article  MATH  Google Scholar 

  11. Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: a fresh approach to numerical computing. SIAM Rev. 59(1), 65–98 (2017). https://doi.org/10.1137/141000671

    Article  MathSciNet  MATH  Google Scholar 

  12. Calinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740–1766 (2011). https://doi.org/10.1137/080733991

    Article  MathSciNet  MATH  Google Scholar 

  13. Chekuri, C., Kumar, A.: Maximum coverage problem with group budget constraints and applications. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 72–83. Springer Berlin Heidelberg, Berlin, Heidelberg (2004). https://doi.org/10.1007/s10878-016-0102-0

  14. Chekuri, C., Vondrák, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6), 1831–1879 (2014). https://doi.org/10.1137/110839655

    Article  MathSciNet  MATH  Google Scholar 

  15. Chlamtác, E., Dinitz, M., Konrad, C., Kortsarz, G., Rabanca, G.: The densest k-subhypergraph problem. SIAM J. Discrete Math. 32(2), 1458–1477 (2018). https://doi.org/10.1137/16M1096402

    Article  MathSciNet  MATH  Google Scholar 

  16. Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233–235 (1979). https://doi.org/10.1287/moor.4.3.233

    Article  MathSciNet  MATH  Google Scholar 

  17. Cornuejols, G., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Manag. Sci. 23(8), 789–810 (1977). https://doi.org/10.1287/mnsc.23.8.789

    Article  MathSciNet  MATH  Google Scholar 

  18. CPLEX, I.: IBM CPLEX Optimizer Reference Manual (2021). https://www.ibm.com/docs/en/icos/20.1.0?topic=cplex-users-manual

  19. Dobson, G.: Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Math. Oper. Res. 7(4), 515–531 (1982). https://doi.org/10.1287/moor.7.4.515

    Article  MathSciNet  MATH  Google Scholar 

  20. Dunning, I., Huchette, J., Lubin, M.: JuMP: a modeling language for mathematical optimization. SIAM Rev. 59(2), 295–320 (2017). https://doi.org/10.1137/15M1020575

    Article  MathSciNet  MATH  Google Scholar 

  21. Dvorkin, Y., Fernandez-Blanco, R., Wang, Y., Xu, B., Kirschen, D.S., Pandzic, H., Watson, J.P., Silva-Monroy, C.A.: Co-planning of investments in transmission and merchant energy storage. IEEE Trans. Power Syst. 33(1), 245–256 (2018). https://doi.org/10.1109/TPWRS.2017.2705187

    Article  Google Scholar 

  22. Engeland, K., Borga, M., Creutin, J.D., François, B., Ramos, M.H., Vidal, J.P.: Space-time variability of climate variables and intermittent renewable electricity production—a review. Renew. Sustain. Energy Rev. 79, 600–617 (2017). https://doi.org/10.1016/j.rser.2017.05.046

    Article  Google Scholar 

  23. ENTSO-E: Power Statistics (2021). https://www.entsoe.eu/data/power-stats

  24. European Centre for Medium-Range Weather Forecasts (ECMWF): ERA5 Hourly Data on Single Levels from 1979 to Present (2021). https://www.ecmwf.int/en/forecasts/datasets/reanalysis-datasets/era5

  25. Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634–652 (1998). https://doi.org/10.1145/285055.285059

    Article  MathSciNet  MATH  Google Scholar 

  26. Filmus, Y., Ward, J.: The power of local search: maximum coverage over a matroid. In: Christoph Dürr, T.W. (ed.) STACS’12 (29th Symposium on Theoretical Aspects of Computer Science), vol. 14, pp. 601–612. LIPIcs (2012). https://doi.org/10.4230/LIPIcs.STACS.2012.i

  27. Filmus, Y., Ward, J.: Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J. Comput. 43(2), 514–542 (2014). https://doi.org/10.1137/130920277

    Article  MathSciNet  MATH  Google Scholar 

  28. Gallo, G., Longo, G., Pallottino, S., Nguyen, S.: Directed hypergraphs and applications. Discrete Appl. Math. 42(2–3), 177–201 (1993). https://doi.org/10.1016/0166-218X(93)90045-P

    Article  MathSciNet  MATH  Google Scholar 

  29. Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., Hendel, G., Hojny, C., Koch, T., Le Bodic, P., Maher, S.J., Matter, F., Miltenberger, M., Mühmer, E., Müller, B., Pfetsch, M.E., Schlösser, F., Serrano, F., Shinano, Y., Tawfik, C., Vigerske, S., Wegscheider, F., Weninger, D., Witzig, J.: The SCIP Optimization Suite 7.0. ZIB-Report 20-10, Zuse Institute Berlin (2020)

  30. Gamrath, G., Gleixner, A., Koch, T., Miltenberger, M., Kniasew, D., Schloegel, D., Martin, A., Weninger, D.: Tackling industrial-scale supply chain problems by mixed-integer programming. J. Comput. Math. 37(6), 866–888 (2019). https://doi.org/10.4208/jcm.1905-m2019-0055

    Article  MathSciNet  MATH  Google Scholar 

  31. Gelaro, R., McCarty, W., Suárez, M.J., Todling, R., Molod, A., Takacs, L., Randles, C.A., Darmenov, A., Bosilovich, M.G., Reichle, R., et al.: The modern-era retrospective analysis for research and applications, version 2 (MERRA-2). J. Clim. 30(14), 5419–5454 (2017). https://doi.org/10.1175/JCLI-D-16-0758.1

    Article  Google Scholar 

  32. Geth, F., Brijs, T., Kathan, J., Driesen, J., Belmans, R.: An overview of large-scale stationary electricity storage plants in Europe: current status and new developments. Renew. Sustain. Energy Rev. 52, 1212–1227 (2015). https://doi.org/10.1016/j.rser.2015.07.145

    Article  Google Scholar 

  33. Giebel, G.: On the Benefits of Distributed Generation of Wind Energy in Europe. PhD Thesis, University of Oldenburg, Germany (2001)

  34. Grossman, T., Wool, A.: Computational experience with approximation algorithms for the set covering problem. Eur. J. Oper. Res. 101(1), 81–92 (1997). https://doi.org/10.1016/S0377-2217(96)00161-0

    Article  MATH  Google Scholar 

  35. Gurobi: Gurobi Optimizer Reference Manual (2021). http://www.gurobi.com

  36. Haas, S., Schachler, B., Krien, U.: Windpowerlib—a python library to model wind power plants (v0.2.0) (2019). https://windpowerlib.readthedocs.io/en/stable/index.html

  37. Hobbs, B.F., Xu, Q., Ho, J., Donohoo, P., Kasina, S., Ouyang, J., Park, S.W., Eto, J., Satyal, V.: Adaptive transmission planning: implementing a new paradigm for managing economic risks in grid expansion. IEEE Power Energy Mag. 14(4), 30–40 (2016). https://doi.org/10.1109/MPE.2016.2547280

    Article  Google Scholar 

  38. Hochbaum, D.S., Pathria, A.: Analysis of the greedy approach in problems of maximum k-coverage. Nav. Res. Logist. 45(6), 615–627 (1998). https://doi.org/10.1002/(SICI)1520-6750(199809)45:6$<$615::AID-NAV5$>$3.0.CO;2-5

  39. International Electrotechnical Commission: IEC 61400-1:2019: wind energy generation systems - part 1: design requirements (2019). https://webstore.iec.ch/publication/26423

  40. Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256–278 (1974). https://doi.org/10.1016/S0022-0000(74)80044-9

    Article  MathSciNet  MATH  Google Scholar 

  41. Jurasz, J., Canales, F., Kies, A., Guezgouz, M., Beluco, A.: A review on the complementarity of renewable energy sources: concept, metrics, application and future research directions. Sol. Energy 195, 703–724 (2020). https://doi.org/10.1016/j.solener.2019.11.087

    Article  Google Scholar 

  42. Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC’02, pp. 767–775. Association for Computing Machinery, New York, NY, USA (2002). https://doi.org/10.1145/509907.510017

  43. Klima, K., Apt, J.: Geographic smoothing of solar PV: results from Gujarat. Environ. Res. Lett. 10(10), 104001 (2015). https://doi.org/10.1088/1748-9326/10/10/104001

    Article  Google Scholar 

  44. Krause, A., Singh, A., Guestrin, C.: Near-optimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235–284 (2008). https://jmlr.org/papers/v9/krause08a.html

  45. Krishnan, V., Ho, J., Hobbs, B.F., Liu, A.L., McCalley, J.D., Shahidehpour, M., Zheng, Q.P.: Co-optimization of electricity transmission and generation resources for planning and policy analysis: review of concepts and modeling approaches. Energy Syst. 7(2), 297–332 (2016). https://doi.org/10.1007/s12667-015-0158-4

    Article  Google Scholar 

  46. Li, W., Stadler, S., Ramakumar, R.: Modeling and assessment of wind and insolation resources with a focus on their complementary nature: a case study of Oklahoma. Ann. Assoc. Am. Geogr. 101(4), 717–729 (2011). https://doi.org/10.1080/00045608.2011.567926

    Article  Google Scholar 

  47. Martin, C.M.S., Lundquist, J.K., Handschy, M.A.: Variability of interconnected wind plants: correlation length and its dependence on variability time scale. Environ. Res. Lett. 10(4), 044004 (2015). https://doi.org/10.1088/1748-9326/10/4/044004

    Article  Google Scholar 

  48. Milligan, M.R., Artig, R.: Choosing Wind Power Plant Locations and Sizes Based on Electric Reliability Measures Using Multiple-Year Wind Speed Measurements. Tech. Rep. CP-500-26724, NREL (1999). https://www.osti.gov/biblio/750939

  49. Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondrák, J., Krause, A.: Lazier than Lazy Greedy. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI’15, pp. 1812–1818. AAAI Press (2015). https://doi.org/10.5555/2886521.2886572

  50. Munoz, F.D., Hobbs, B.F., Ho, J.L., Kasina, S.: An engineering-economic approach to transmission planning under market and regulatory uncertainties: WECC case study. IEEE Trans. Power Syst. 29(1), 307–317 (2014). https://doi.org/10.1109/TPWRS.2013.2279654

    Article  Google Scholar 

  51. Musselman, A., Thomas, V.M., Boland, N., Nazzal, D.: Optimizing wind farm siting to reduce power system impacts of wind variability. Wind Energy 22(7), 894–907 (2019). https://doi.org/10.1002/we.2328

    Article  Google Scholar 

  52. Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3), 177–188 (1978). https://doi.org/10.1287/moor.3.3.177

    Article  MathSciNet  MATH  Google Scholar 

  53. Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-I. Math. Program. 14, 265–294 (1978). https://doi.org/10.1007/BF01588971

    Article  MathSciNet  MATH  Google Scholar 

  54. Norgård, P., Holttinen, H.: A multi-turbine power curve. In: NWPC’04: Nordic Wind Power Conference, no. 32R in Chalmers Tekniska Högskola, Institutionen för Elkraftteknik. Examensarbete (2004)

  55. O’Connell, N., Pinson, P., Madsen, H., O’Malley, M.: Benefits and challenges of electrical demand response: a critical review. Renew. Sustain. Energy Rev. 39, 686–699 (2014). https://doi.org/10.1016/j.rser.2014.07.098

  56. Olauson, J., Bergkvist, M.: Correlation between wind power generation in the European countries. Energy 114, 663–670 (2016). https://doi.org/10.1016/j.energy.2016.08.036

    Article  Google Scholar 

  57. Peleg, D., Schechtman, G., Wool, A.: Approximating bounded 0-1 integer linear programs. In: The 2nd Israel Symposium on Theory and Computing Systems, pp. 69–70. IEEE (1993). https://doi.org/10.1109/ISTCS.1993.253482

  58. Peleg, D., Schechtman, G., Wool, A.: Randomized approximation of bounded multicovering problems. Algorithmica 18(1), 44–66 (1997). https://doi.org/10.1007/BF02523687

    Article  MathSciNet  MATH  Google Scholar 

  59. Prasad, A.A., Taylor, R.A., Kay, M.: Assessment of solar and wind resource synergy in Australia. Appl. Energy 190, 354–367 (2017). https://doi.org/10.1016/j.apenergy.2016.12.135

    Article  Google Scholar 

  60. Radu, D., Berger, M.: Data for “Siting Renewable Power Generation Assets using Combinatorial Optimisation” (2021). https://dox.uliege.be/index.php/s/jNoMUGUHi1QhsAf

  61. Radu, D., Berger, M.: resite_ip: A Framework for RES Siting Leveraging Resource Complementarity (2021). https://gitlab.uliege.be/smart_grids/public/resite_ip/tree/feature-ol

  62. Radu, D., Berger, M., Fonteneau, R., Hardy, S., Fettweis, X., Du, M.L., Panciatici, P., Balea, L., Ernst, D.: Complementarity assessment of South Greenland katabatic flows and West Europe wind regimes. Energy 175, 393–401 (2019). https://doi.org/10.1016/j.energy.2019.03.048

    Article  Google Scholar 

  63. Resende, M.G.: Computing approximate solutions of the maximum covering problem with GRASP. J. Heurist. 4(2), 161–177 (1998). https://doi.org/10.1023/A:1009677613792

    Article  MATH  Google Scholar 

  64. Roughgarden, T. (ed.): Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, Cambridge (2021). https://doi.org/10.1017/9781108637435

  65. Stenclik, D., Denholm, P., Chalamala, B.: Maintaining balance: the increasing role of energy storage for renewable integration. IEEE Power Energy Mag. 15(6), 31–39 (2017). https://doi.org/10.1109/MPE.2017.2729098

    Article  Google Scholar 

  66. Sterl, S., Liersch, S., Koch, H., van Lipzig, N.P.M., Thiery, W.: A new approach for assessing synergies of solar and wind power: implications for West Africa. Environ. Res. Lett. 13(9) (2018). https://doi.org/10.1088/1748-9326/aad8f6

  67. WindEurope: Wind Energy and On-Site Energy Storage - Exploring Market Opportunities (2017). https://windeurope.org/wp-content/uploads/files/about-wind/reports/Wind-energy-in-Europe-Scenarios-for-2030.pdf

  68. WindEurope: Wind Energy in Europe in 2019 (2020). https://windeurope.org/wp-content/uploads/files/about-wind/statistics/WindEurope-Annual-Statistics-2019.pdf

  69. Wu, G., Deshmukh, R., Ndhlukulac, K., Radojicic, T., Reilly-Moman, J., Phadke, A., Kammen, D., Callaway, D.: Strategic siting and regional grid interconnections key to low-carbon futures in African countries. Proc. Natl. Acad. Sci. 114, 3004–3012 (2017). https://doi.org/10.1073/pnas.1611845114

    Article  Google Scholar 

  70. Zappa, W., van den Broek, M.: Analysing the potential of integrating wind and solar power in europe using spatial optimisation under various scenarios. Renew. Sustain. Energy Rev. 94, 1192–1216 (2018). https://doi.org/10.1016/j.rser.2018.05.071

    Article  Google Scholar 

  71. Zhang, H., Cao, Y., Zhang, Y., Terzija, V.: Quantitative synergy assessment of regional wind-solar energy resources based on MERRA reanalysis data. Appl. Energy 216, 172–182 (2018). https://doi.org/10.1016/j.apenergy.2018.02.094

    Article  Google Scholar 

Download references

Acknowledgements

Mathias Berger and David Radu would like to gratefully acknowledge the support of the Belgian government through its Energy Transition Fund and the REMI project. Antoine Dubois would like to acknowledge the support of a FRIA fellowship of the FRS-FNRS. The authors would like to thank Raphael Fonteneau for valuable discussions and the anonymous reviewers whose comments helped improve the clarity and quality of this manuscript.

Author information

Authors and Affiliations

  1. Department of Electrical Engineering and Computer Science, University of Liège, Liège, Belgium

    Mathias Berger, David Radu, Antoine Dubois, Quentin Louveaux & Damien Ernst

  2. Faculty of Electrical Engineering and Computing, University of Zagreb, Zagreb, Croatia

    Hrvoje Pandžić

  3. Department of Electrical and Computer Engineering, NYU Tandon School of Engineering, New York, USA

    Yury Dvorkin

Authors
  1. Mathias Berger
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David Radu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Antoine Dubois
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Hrvoje Pandžić
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Yury Dvorkin
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Quentin Louveaux
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Damien Ernst
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mathias Berger.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Berger, M., Radu, D., Dubois, A. et al. Siting renewable power generation assets with combinatorial optimisation. Optim Lett 16, 877–907 (2022). https://doi.org/10.1007/s11590-021-01795-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-021-01795-0

Keywords

Search

Navigation