Robust Online Algorithms for Peak-Minimizing EV Charging Under Multistage Uncertainty

In this paper, we study how to utilize forecasts to design online electrical vehicle (EV) charging algorithms that can attain strong performance guarantees. We consider the scenario of an aggregator serving a large number of EVs together with its background load, using both its own renewable energy (for free) and the energy procured from the external grid. The goal of the aggregator is to minimize its peak procurement from the grid, subject to the constraint that each EV has to be fully charged before its deadline. Further, the aggregator can predict the future demand and the renewable energy supply with some levels of uncertainty. We show that such prediction can be very effective in reducing the competitive ratios of online control algorithms, and even allow online algorithms to achieve close-to-offline-optimal peak. Specifically, we first propose a 2-level increasing precision model (2-IPM), to model forecasts with different levels of accuracy. We then develop a powerful computational approach that can compute the optimal competitive ratio under 2-IPM over any online algorithm, and also online algorithms that can achieve the optimal competitive ratio. Simulation results show that, even with up to 20% day-ahead prediction errors, our online algorithms still achieve competitive ratios fairly close to 1, which are much better than the classic results in the literature with a competitive ratio of $e$. The second contribution of this paper is that we solve a dilemma for online algorithm design, e.g., an online algorithm with good competitive ratio may exhibit poor average-case performance. We propose a new Algorithm-Robustification procedure that can convert an online algorithm with good average-case performance to one with both the optimal competitive ratio and good average-case performance. We demonstrate via trace-based simulations the superior performance of the robustified version of a well-known heuristic algorithm based on model predictive control.