A Caltech Library Service

Distributed Load Balancing with Nonconvex Constraints: A Randomized Algorithm with Application to Electric Vehicle Charging Scheduling

Gan, Lingwen and Topcu, Ufuk and Low, Steven H. (2014) Distributed Load Balancing with Nonconvex Constraints: A Randomized Algorithm with Application to Electric Vehicle Charging Scheduling. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


With substantial potential to reduce green house gas emission and reliance on fossil fuel, electric vehicles (EVs) have lead to a booming industry, whose growth is expected to continue for the next few decades. However, EVs present themselves as large loads to the power grid. If not coordinated wisely, the charging of EVs will overload power distribution circuits and dramatically increase power supply cost. To address this challenge, significant amount of effort has been devoted in the literature to schedule the charging of EVs in a power grid friendly way. Nonetheless, the majority of the literature assumes that EVs can be charged intermittently at any power level below certain rating, while in practice, it is preferable to charge an EV consecutively at a pre-determined power to prolong the battery lifespan. This practical EV charging constraint is nonconvex and complicates scheduling. To schedule a large number of EVs with the presence of practical nonconvex charging constraints, a distributed and randomized algorithm is proposed in this paper. The algorithm assumes the availability of a coordinator which can communicate with all EVs. In each iteration of the algorithm, the coordinator receives tentative charging profiles from the EVs and computes a broadcast control signal. After receiving this broadcast control signal, each EV generates a probability distribution over its admissible charging profiles, and samples from the distribution to update its tentative charging profile. We prove that the algorithm converges almost surely to a charging profile in finite iterations. The final charging profile (that the algorithm converges to) is random, i.e., it depends on the realization. We characterize the final charging profile—a charging profile can be a realization of the final charging profile if and only if it is a Nash equilibrium of the game in which each EV seeks to minimize the inner product of its own charging profile and the aggregate electricity demand. Furthermore, we provide a uniform suboptimality upper bound, that scales O(1=n) in the number n of EVs, for all realizations of the final charging profile.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Low, Steven H.0000-0001-6476-3048
Record Number:CaltechAUTHORS:20190628-094804246
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:96817
Deposited By: Tony Diaz
Deposited On:28 Jun 2019 16:57
Last Modified:03 Oct 2019 21:25

Repository Staff Only: item control page