Network planning in smart grids via a local search heuristic for spanning forest problems

George Davidescu, Thomas Stutzle, Valeriy Vyatkin

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

Smart grids are automated, distributed energy exchange networks that, in contrast to traditional electricity grids, feature reconfigurable network topologies. Network planning is an essential function of smart grids that connects customers to energy sources using available physical links in the network. We model this as the problem of creating a spanning forest with a capacity constraint on each tree bounding its total weight. Each tree of the forest corresponds to a set of customers, rooted at a source. We call this the Capacitated Spanning Forest (CSF) problem. CSF is NP-complete even on unweighted graphs with two sources. We present a solution to this problem using a Local Search heuristic and demonstrate its performance on square grids and on a real-world sample grid topology.
Original languageEnglish
Title of host publicationProceedings of the 26th IEEE International Symposium on Industrial Electronics, ISIE 2017
PublisherIEEE
Pages1212-1218
Number of pages7
ISBN (Electronic)978-1-5090-1412-5
DOIs
Publication statusPublished - 8 Aug 2017
MoE publication typeA4 Article in a conference publication
EventInternational Symposium on Industrial Electronics - Edinburgh, United Kingdom
Duration: 19 Jun 201721 Jun 2017
Conference number: 26

Publication series

NameProceedings of the IEEE International Symposium on Industrial Electronics
PublisherIEEE
ISSN (Print)2163-5137
ISSN (Electronic)2380-1395

Conference

ConferenceInternational Symposium on Industrial Electronics
Abbreviated titleISIE
CountryUnited Kingdom
CityEdinburgh
Period19/06/201721/06/2017

Fingerprint Dive into the research topics of 'Network planning in smart grids via a local search heuristic for spanning forest problems'. Together they form a unique fingerprint.

  • Cite this

    Davidescu, G., Stutzle, T., & Vyatkin, V. (2017). Network planning in smart grids via a local search heuristic for spanning forest problems. In Proceedings of the 26th IEEE International Symposium on Industrial Electronics, ISIE 2017 (pp. 1212-1218). (Proceedings of the IEEE International Symposium on Industrial Electronics). IEEE. https://doi.org/10.1109/ISIE.2017.8001418