Minimizing Cost-Plus-Dissatisfaction in Online EV Charging Under Real-Time Pricing
Authors:
- 29 September 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Intelligent Transportation Systems
- Vol. 23 (8) , 12464-12479
Abstract
We consider an increasingly popular demand-response scenario where a home user schedules the flexible electric vehicle (EV) charging load in response to real-time electricity prices. The objective is to minimize the total charging cost with user dissatisfaction taken into account. We focus on the online setting where neither accurate prediction nor distribution of future real-time prices is available to the user when making irrevocable charging decisions in each time slot. The emphasis on considering user dissatisfaction and achieving optimal competitive ratio differentiates our work from existing ones and makes our study uniquely challenging. Our key contribution is two simple online algorithms with the optimal competitive ratio among all deterministic algorithms. The optimal competitive ratio is upper-bounded by $\min \left \{{ \sqrt {\alpha /p_{\min }},p_{\max }/p_{\min }}\right \} $ and the bound is asymptotically tight with respect to $\alpha $ , where $p_{\max }$ and $p_{\min }$ are the upper and lower bounds of real-time prices and $\alpha \geq p_{\min }$ captures the consideration of user dissatisfaction. The bounds with respect to small and large values of $\alpha $ suggest the fundamental difference of the problems with and without considering user dissatisfaction. We also extend the algorithms to take minimum charging requirement and short-term prediction into account. Simulation results based on real-world traces corroborate our theoretical findings and show that the empirical performance of our algorithms can be substantially better than the theoretical worst-case guarantees. Our algorithms also achieve notable performance gains under diverse settings as compared to conceivable alternatives.
Keywords
Funding Information
- Start-Up Grant from the School of Data Science, City University of Hong Kong (9380118)
- General Research Fund from Research Grants Council, Hong Kong (11206821)
This publication has 40 references indexed in Scilit:
- Peak-minimizing online EV charging: Price-of-uncertainty and algorithm robustification2015
- Optimal Charging of Electric Vehicles With Uncertain Departure Times: A Closed-Form SolutionIEEE Transactions on Smart Grid, 2014
- Online coordinated charging decision algorithm for electric vehicles without future informationIEEE Transactions on Smart Grid, 2014
- Real-Time PEV Charging/Discharging Coordination in Smart Distribution SystemsIEEE Transactions on Smart Grid, 2014
- Online welfare maximization for electric vehicle charging with electricity cost2014
- Cost-Optimal Charging of Plug-In Hybrid Electric Vehicles Under Time-Varying Electricity Price SignalsIEEE Transactions on Intelligent Transportation Systems, 2014
- Distributed control of electric vehicle charging2013
- The Design of Competitive Online Algorithms via a Primal—Dual ApproachFoundations and Trends® in Theoretical Computer Science, 2009
- Optimal Search and One-Way Trading Online AlgorithmsAlgorithmica, 2001
- Real-time pricing of electricity for residential customers: Econometric analysis of an experimentJournal of Applied Econometrics, 1995