Complexity of Scheduling Charging in the Smart Grid

Conference Paper (2018)
Author(s)

MM de Weerdt (TU Delft - Algorithmics)

Michael Albert (Duke University)

V Conitzer (Duke University)

Koos van der Linden (TU Delft - Algorithmics)

Research Group
Algorithmics
Copyright
© 2018 M.M. de Weerdt, Michael Albert, Vincent Conitzer, J.G.M. van der Linden
DOI related publication
https://doi.org/10.24963/ijcai.2018/658
More Info
expand_more
Publication Year
2018
Language
English
Copyright
© 2018 M.M. de Weerdt, Michael Albert, Vincent Conitzer, J.G.M. van der Linden
Research Group
Algorithmics
Bibliographical Note
Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public. @en
Pages (from-to)
4736-4742
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

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.

Files

0658.pdf
(pdf | 1.77 Mb)
- Embargo expired in 01-07-2019
License info not available