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.