Peak-minimizing online EV charging

In this paper, we consider an aggregator that manages a large number of Electrical Vehicle (EV) charging jobs, each of which requests a certain amount of energy that needs to be charged before a deadline. The goal of the aggregator is to minimize the peak consumption at any time by planning the charging schedules in order. A key challenge that the aggregator faces in the planning is that there exists significant uncertainty in future arrivals of EV charging jobs. In contrast to existing approaches that either require precise knowledge of future arrivals or do not make use of any future information at all, we consider a more practical scenario where the aggregator can obtain a limited amount of future knowledge. Specifically, we consider a model where a fraction of the users reserve EV charging jobs (with possible reservation uncertainty) in advance and we are interested in understanding how much limited future knowledge can improve the performance of the online algorithms. We provide a general and systematic framework for determining the optimal competitive ratios for an arbitrary set of reservation parameters, and develop simple online algorithms that attain these optimal competitive ratios. Our numerical results indicate that reservation can indeed significantly improve the competitive ratio and reduce the peak consumption.