Online Charging Scheduling Algorithms of Electric Vehicles in Smart Grid: An Overview
---
paper_title: Optimal decentralized protocol for electric vehicle charging

paper_content:

Motivated by the power-grid-side challenges in the integration of electric vehicles, we propose a decentralized protocol for negotiating day-ahead charging schedules for electric vehicles. The overall goal is to shift the load due to electric vehicles to fill the overnight electricity demand valley. In each iteration of the proposed protocol, electric vehicles choose their own charging profiles for the following day according to the price profile broadcast by the utility, and the utility updates the price profile to guide their behavior. This protocol is guaranteed to converge, irrespective of the specifications (e.g., maximum charging rate and deadline) of electric vehicles. At convergence, the l 2 norm of the aggregated demand is minimized, and the aggregated demand profile is as “flat” as it can possibly be. The proposed protocol needs no coordination among the electric vehicles, hence requires low communication and computation capability. Simulation results demonstrate convergence to optimal collections of charging profiles within few iterations.
---
paper_title: A Model Predictive Control Approach for Low-Complexity Electric Vehicle Charging Scheduling: Optimality and Scalability

paper_content:

With the increasing adoption of plug-in electric vehicles (PEVs), it is critical to develop efficient charging coordination mechanisms that minimize the cost and impact of PEV integration to the power grid. In this paper, we consider the optimal PEV charging scheduling, where the non-causal information about future PEV arrivals is not known in advance, but its statistical information can be estimated. This leads to an "online" charging scheduling problem that is naturally formulated as a finite-horizon dynamic programming with continuous state space and action space. To avoid the prohibitively high complexity of solving such a dynamic programming problem, we provide a Model Predictive Control (MPC) based algorithm with computational complexity $O(T^3)$, where $T$ is the total number of time stages. We rigorously analyze the performance gap between the near-optimal solution of the MPC-based approach and the optimal solution for any distributions of exogenous random variables. Furthermore, our rigorous analysis shows that when the random process describing the arrival of charging demands is first-order periodic, the complexity of proposed algorithm can be reduced to $O(1)$, which is independent of $T$. Extensive simulations show that the proposed online algorithm performs very closely to the optimal online algorithm. The performance gap is smaller than $0.4\%$ in most cases.
---
paper_title: iEMS for large scale charging of electric vehicles: Architecture and optimal online scheduling

paper_content:

The problem of large scale charging of electric vehicles (EVs) is considered. An architecture for the energy management system (EMS) is proposed based on the concept of network switched charging where chargers are controlled by a scheduler that optimizes the overall operating profit of the service provider. It is assumed that the EMS has access to collocated renewable sources (e.g. solar power) and can supplement the renewable with purchased electricity from the grid. The renewable source may vary arbitrarily, and requests of all EVs accepted for service must be completed by their respective deadlines. Under a deterministic model for arbitrary arrivals, charging requests, and service deadlines, online scheduling of EV charging is formulated as a multi-processor deadline scheduling problem for which the optimal scheduler maximizes the competitive ratio against the best offline scheduler. An online scheduling algorithm, referred to as TAGS, is proposed based on the principle of threshold admission and greedy scheduling. TAGS has the complexity of O(n log n) where n is the number of EVs in the facility. It is shown that, when the price offered to the EV customers is higher than the purchasing price of electricity from the grid, TAGS achieves the competitive ratio of 1. Otherwise, TAGS achieves the maximum competitive ratio given by the inverse of a real root of a certain polynomial. Simulations are used to evaluate the performance of TAGS against standard benchmarks and for the setting of optimal charging price.
---
paper_title: Fast Prediction for Sparse Time Series: Demand Forecast of EV Charging Stations for Cell Phone Applications

paper_content:

This paper proposes a new cellphone application algorithm which has been implemented for the prediction of energy consumption at electric vehicle (EV) charging stations at the University of California, Los Angeles (UCLA). For this interactive user application, the total time for accessing the database, processing the data, and making the prediction needs to be within a few seconds. We first analyze three relatively fast machine learning-based time series prediction algorithms and find that the nearest neighbor (NN) algorithm (k NN with k = 1) shows better accuracy. Considering the sparseness of the time series of the charging records, we then discuss the new algorithm based on the new proposed time-weighted dot product (TWDP) dissimilarity measure to improve the accuracy and processing time. Two applications have been designed on top of the proposed prediction algorithm: one predicts the expected available energy at the outlet and the other one predicts the expected charging finishing time. The total time, including accessing the database, data processing, and prediction is approximately 1 s for both applications. The granularity of the prediction is 1 h and the horizon is 24 h; data have been collected from 20 EV charging outlets.
---
paper_title: Design a Wind Speed Prediction Model Using Probabilistic Fuzzy System

paper_content:

Generation of wind is a very complicated process and influenced by large numbers of unknown factors. A probabilistic fuzzy system based prediction model is designed for the short-term wind speed prediction. By introducing the third probability dimension, the proposed prediction model can capture both stochastic and the deterministic uncertainties, and guarantee a better prediction in complex stochastic environment. The effectiveness of this intelligent wind speed prediction model is demonstrated by the simulations on a group of wind speed data. The robust modeling performance further discloses its potential in the practical prediction of wind speed under complex circumstance.
---
paper_title: A Scalable Stochastic Model for the Electricity Demand of Electric and Plug-In Hybrid Vehicles

paper_content:

In this paper we propose a stochastic model, based on queueing theory, for electric vehicle (EV) and plug-in hybrid electric vehicle (PHEV) charging demand. Compared to previous studies, our model can provide 1) more accurate forecasts of the load using real-time sub-metering data, along with the level of uncertainty that accompanies these forecasts; 2) a mathematical description of load, along with the level of demand flexibility that accompanies this load, at the wholesale level. This can be useful when designing demand response and dynamic pricing schemes. Our numerical experiments tune the proposed statistics on real PHEV charging data and demonstrate that the forecasting method we propose is more accurate than standard load prediction techniques.
---
paper_title: An advanced data driven model for residential electric vehicle charging demand

paper_content:

As the electric vehicle (EV) is becoming a significant component of the loads, an accurate and valid model for the EV charging demand is the key to enable accurate load forecasting, demand respond, system planning, and several other important applications. We propose a data driven queuing model for residential EV charging demand by performing big data analytics on smart meter measurements. The data driven model captures the non-homogeneity and periodicity of the residential EV charging behavior through a self-service queue with a periodic and non-homogeneous Poisson arrival rate, an empirical distribution for charging duration and a finite calling population. Upon parameter estimation, we further validate the model by comparing the simulated data series with real measurements. The hypothesis test shows the proposed model accurately captures the charging behavior. We further acquire the long-run average steady state probabilities and simultaneous rate of the EV charging demand through simulation output analysis.
---
paper_title: Stochastic Optimization of Grid to Vehicle Frequency Regulation Capacity Bids

paper_content:

This paper investigates the application of stochastic dynamic programming to the optimization of charging and frequency regulation capacity bids of an electric vehicle (EV) in a smart electric grid environment. We formulate a Markov decision problem to minimize an EV's expected cost over a fixed charging horizon. We account for both Markov random prices and a Markov random regulation signal. We also propose an enhancement to the classical discrete stochastic dynamic programming method. This enhancement allows optimization over a continuous space of decision variables via linear programming at each state. Simple stochastic process models are built from real data and used to simulate the implementation of the proposed method. The proposed method is shown to outperform deterministic model predictive control in terms of average EV charging cost.
---
paper_title: A Model Predictive Control Approach for Low-Complexity Electric Vehicle Charging Scheduling: Optimality and Scalability

paper_content:

With the increasing adoption of plug-in electric vehicles (PEVs), it is critical to develop efficient charging coordination mechanisms that minimize the cost and impact of PEV integration to the power grid. In this paper, we consider the optimal PEV charging scheduling, where the non-causal information about future PEV arrivals is not known in advance, but its statistical information can be estimated. This leads to an "online" charging scheduling problem that is naturally formulated as a finite-horizon dynamic programming with continuous state space and action space. To avoid the prohibitively high complexity of solving such a dynamic programming problem, we provide a Model Predictive Control (MPC) based algorithm with computational complexity $O(T^3)$, where $T$ is the total number of time stages. We rigorously analyze the performance gap between the near-optimal solution of the MPC-based approach and the optimal solution for any distributions of exogenous random variables. Furthermore, our rigorous analysis shows that when the random process describing the arrival of charging demands is first-order periodic, the complexity of proposed algorithm can be reduced to $O(1)$, which is independent of $T$. Extensive simulations show that the proposed online algorithm performs very closely to the optimal online algorithm. The performance gap is smaller than $0.4\%$ in most cases.
---
paper_title: Profit-Maximizing Planning and Control of Battery Energy Storage Systems for Primary Frequency Control

paper_content:

We consider a two-level profit-maximizing strategy, including planning and control, for battery energy storage system (BESS) owners that participate in the primary frequency control (PFC) market. Specifically, the optimal BESS control minimizes the operating cost by keeping the state of charge (SoC) in an optimal range. Through rigorous analysis, we prove that the optimal BESS control is a "state-invariant" strategy in the sense that the optimal SoC range does not vary with the state of the system. As such, the optimal control strategy can be computed offline once and for all with very low complexity. Regarding the BESS planning, we prove that the the minimum operating cost is a decreasing convex function of the BESS energy capacity. This leads to the optimal BESS sizing that strikes a balance between the capital investment and operating cost. Our work here provides a useful theoretical framework for understanding the planning and control strategies that maximize the economic benefits of BESSs in ancillary service markets.
---
paper_title: Stochastic Analyses of Electric Vehicle Charging Impacts on Distribution Network

paper_content:

A stochastic modeling and simulation technique for analyzing impacts of electric vehicles charging demands on distribution network is proposed in this paper. Different from the previous deterministic approaches, the feeder daily load models, electric vehicle start charging time, and battery state of charge used in the impact study are derived from actual measurements and survey data. Distribution operation security risk information, such as over-current and under-voltage, is obtained from three-phase distribution load flow studies that use stochastic parameters drawn from Roulette wheel selection. Voltage and congestion impact indicators are defined and a comparison of the deterministic and stochastic analytical approaches in providing information required in distribution network reinforcement planning is presented. Numerical results illustrate the capability of the proposed stochastic models in reflecting system losses and security impacts due to electric vehicle integrations. The effectiveness of a controlled charging algorithm aimed at relieving the system operation problem is also presented.
---
paper_title: A Scalable Stochastic Model for the Electricity Demand of Electric and Plug-In Hybrid Vehicles

paper_content:

In this paper we propose a stochastic model, based on queueing theory, for electric vehicle (EV) and plug-in hybrid electric vehicle (PHEV) charging demand. Compared to previous studies, our model can provide 1) more accurate forecasts of the load using real-time sub-metering data, along with the level of uncertainty that accompanies these forecasts; 2) a mathematical description of load, along with the level of demand flexibility that accompanies this load, at the wholesale level. This can be useful when designing demand response and dynamic pricing schemes. Our numerical experiments tune the proposed statistics on real PHEV charging data and demonstrate that the forecasting method we propose is more accurate than standard load prediction techniques.
---
paper_title: A Model Predictive Control Approach for Low-Complexity Electric Vehicle Charging Scheduling: Optimality and Scalability

paper_content:

With the increasing adoption of plug-in electric vehicles (PEVs), it is critical to develop efficient charging coordination mechanisms that minimize the cost and impact of PEV integration to the power grid. In this paper, we consider the optimal PEV charging scheduling, where the non-causal information about future PEV arrivals is not known in advance, but its statistical information can be estimated. This leads to an "online" charging scheduling problem that is naturally formulated as a finite-horizon dynamic programming with continuous state space and action space. To avoid the prohibitively high complexity of solving such a dynamic programming problem, we provide a Model Predictive Control (MPC) based algorithm with computational complexity $O(T^3)$, where $T$ is the total number of time stages. We rigorously analyze the performance gap between the near-optimal solution of the MPC-based approach and the optimal solution for any distributions of exogenous random variables. Furthermore, our rigorous analysis shows that when the random process describing the arrival of charging demands is first-order periodic, the complexity of proposed algorithm can be reduced to $O(1)$, which is independent of $T$. Extensive simulations show that the proposed online algorithm performs very closely to the optimal online algorithm. The performance gap is smaller than $0.4\%$ in most cases.
---
paper_title: Fast Prediction for Sparse Time Series: Demand Forecast of EV Charging Stations for Cell Phone Applications

paper_content:

This paper proposes a new cellphone application algorithm which has been implemented for the prediction of energy consumption at electric vehicle (EV) charging stations at the University of California, Los Angeles (UCLA). For this interactive user application, the total time for accessing the database, processing the data, and making the prediction needs to be within a few seconds. We first analyze three relatively fast machine learning-based time series prediction algorithms and find that the nearest neighbor (NN) algorithm (k NN with k = 1) shows better accuracy. Considering the sparseness of the time series of the charging records, we then discuss the new algorithm based on the new proposed time-weighted dot product (TWDP) dissimilarity measure to improve the accuracy and processing time. Two applications have been designed on top of the proposed prediction algorithm: one predicts the expected available energy at the outlet and the other one predicts the expected charging finishing time. The total time, including accessing the database, data processing, and prediction is approximately 1 s for both applications. The granularity of the prediction is 1 h and the horizon is 24 h; data have been collected from 20 EV charging outlets.
---
paper_title: Design a Wind Speed Prediction Model Using Probabilistic Fuzzy System

paper_content:

Generation of wind is a very complicated process and influenced by large numbers of unknown factors. A probabilistic fuzzy system based prediction model is designed for the short-term wind speed prediction. By introducing the third probability dimension, the proposed prediction model can capture both stochastic and the deterministic uncertainties, and guarantee a better prediction in complex stochastic environment. The effectiveness of this intelligent wind speed prediction model is demonstrated by the simulations on a group of wind speed data. The robust modeling performance further discloses its potential in the practical prediction of wind speed under complex circumstance.
---
paper_title: Distribution Locational Marginal Pricing for Optimal Electric Vehicle Charging Management

paper_content:

AC optimal power flow (ACOPF) is typically used for operational dispatch decisions. However, DC optimal power flow (DCOPF) based on linearization of the ACOPF is widely used for locational marginal price (LMP) calculation in market operation and settlements due to its efficiency and reasonable accuracy. The DCOPF is considered to be sufficient in many cases. Especially for calculating LMPs of distribution systems, the DCOPF is a good option considering the large number of nodes in distribution systems. In industry, DCOPF has been employed by several software tools for chronological LMP simulation and forecasting.
---

Title: Online Charging Scheduling Algorithms of Electric Vehicles in Smart Grid: An Overview

Section 1: Introduction
Description 1: This section provides an introduction to electric vehicles (EVs), their benefits, challenges, and the need for effective charging scheduling algorithms.

Section 2: Basic Model of Real-Time Stochastic EV Charging Control
Description 2: This section describes the fundamental elements and concepts in real-time stochastic EV charging scheduling, such as event-driven control, system time, and causal information.

Section 3: Stochastic Control Techniques of EV Charging
Description 3: This section discusses various control techniques for EV charging based on the knowledge of future random data, including methodologies with complete knowledge of data, no knowledge of future data, and partial knowledge of statistical information.

Section 4: Methodologies with Complete Knowledge of Future Data
Description 4: This section delves into methodologies that assume complete knowledge of future data and how they translate the EV charging scheduling problem into a deterministic problem.

Section 5: Methodologies with Knowledge of Statistical Information
Description 5: This section covers stochastic control techniques when statistical information, such as moments or probability distributions, is available for future data.

Section 6: Performance Evaluation
Description 6: This section evaluates the performance of different methodologies and algorithms within various scenarios, highlighting their effectiveness and comparative results.

Section 7: Future Research Directions
Description 7: This section discusses potential future research directions, including economic incentive design, online/stochastic learning of random data, and integration of renewable sources.

Section 8: Conclusions
Description 8: This section summarizes the key points of the survey and provides closing thoughts on the importance and impact of advanced online EV charging scheduling algorithms.