Optimal Online Adaptive Electric Vehicle Charging
We propose an online linear program (OLP) based algorithm for scheduling electric vehicle (EV) charging. To determine the charging rates in each control period, OLP solves a linear program based only on EVs currently in the charging facility, assuming no future EV arrivals. We prove that OLP achieves the offline optimal where all future EV arrivals are assumed to be known in advance, provided the cost coefficients are uniformly monotone. For general cost functions, we prove that the competitive ratio is upper bounded by the variability in the cost coefficients. We demonstrate the performance of OLP using real charging data from Google and Caltech's Adaptive Charging Network.
© 2017 IEEE. We thank Yorie Nakahira and Fengyu Zhou of caltech for helpful discussions, and George Lee and Ted Lee of PowerFlex for providing charging data. This work has been supported by NSF grants through PFI:AIR-TI award 1602119. EPCN 1619352, CNS 1545096 CCF 1637598 and ARPA-E grant through award DE-AR0000699.