Complexity of Scheduling Charging in the Smart Grid

Mathijs de Weerdt, Michael Albert, Vincent Conitzer, Koos van der Linden

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

33 Downloads (Pure)

Abstract

The problem of optimally scheduling the charging demand of electric vehicles within the constraints of the electricity infrastructure is called the charge scheduling problem. The models of the charging speed, horizon, and charging demand determine the computational complexity of the charge scheduling problem. We show that for about 20 variants the problem is either in P or weakly NP-hard and dynamic programs exist to compute optimal solutions. About 10 other variants of the problem are strongly NP-hard, presenting a potentially significant obstacle to their use in practical situations of scale. An experimental study establishes up to what parameter values the dynamic programs can determine optimal solutions in a couple of minutes.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)
PublisherInternational Joint Conferences on Artifical Intelligence (IJCAI)
Pages4736-4742
Number of pages7
DOIs
Publication statusPublished - 13 Jul 2018
EventIJCAI 2018: 27th International Joint Conference on Artificial Intelligence - Stockholm, Sweden
Duration: 13 Jul 201819 Jul 2018
Conference number: 27
https://www.ijcai.org/

Conference

ConferenceIJCAI 2018
CountrySweden
CityStockholm
Period13/07/1819/07/18
Internet address

Fingerprint Dive into the research topics of 'Complexity of Scheduling Charging in the Smart Grid'. Together they form a unique fingerprint.

Cite this