Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
36,748 characters · 17 sections · 17 citation commands
Dynamic Pricing and Energy Management Strategy for EV Charging Stations under Uncertainties
\abstract{This paper presents a dynamic pricing and energy management framework for electric vehicle (EV) charging service providers. To set the charging prices, the service providers faces three uncertainties: the volatility of wholesale electricity price, intermittent renewable energy generation, and spatial-temporal EV charging demand. The main objective of our work here is to help charging service providers to improve their total profits while enhancing customer satisfaction and maintaining power grid stability, taking into account those uncertainties. We employ a linear regression model to estimate the EV charging demand at each charging station, and introduce a quantitative measure for customer satisfaction. Both the greedy algorithm and the dynamic programming (DP) algorithm are employed to derive the optimal charging prices and determine how much electricity to be purchased from the wholesale market in each planning horizon. Simulation results show that DP algorithm achieves an increased profit (up to 9%) compared to the greedy algorithm (the benchmark algorithm) under certain scenarios. Additionally, we observe that the integration of a low-cost energy storage into the system can not only improve the profit, but also smooth out the charging price fluctuation, protecting the end customers from the volatile wholesale market.}
\onecolumn
Symbols
Recent innovations in battery and powertrain technology have served as a catalyst for expediting the proliferation of electric vehicles (EVs). EVs exhibit many advantages over the internal combustion engine (ICE) vehicles, including lower operation cost, higher fuel conversion efficiency, and reduced or eliminated tailpipe emission simpson,efficiency. The American market share of plug-in EVs in new registered cars increased from 0.14% to 0.37% in 2012, 0.62% in 2013, and 0.72% in 2014 market. According to Navigant Research, the global light duty EV market is expected to grow from 2.7 million vehicle sales in 2014 to 6.4 million in 2023 navigant. EVs will play a significant role in transportation electrification. Nevertheless, the limited driving range and the long charging time are still the major obstacles to the proliferation of EVs. The “range anxiety" is like the Sword of Damocles for EV owners. More charging stations need be established to alleviate the “range anxiety". In addition, the profitability of the EV charging industry is another critical issue that should be considered. The EV charging industry needs a promising business model to bring more private investors into this industry instead of solely relying on financial support or incentives from governments. The effective and efficient management of charging infrastructure is at the heart of the EV charging industry. The objective of this paper is to provide guidelines for charging service providers make informed and optimized decisions on pricing and energy management so as to coherently improve profits, enhance customer satisfaction, and reduce uncertainties or risks.
Currently, there is a plethora of literature aiming at addressing the dynamic pricing issue of EV charging stations. Yan et al. proposed a multi-tiered real-time pricing algorithm for charging stations by taking into account both the day-ahead predicted electricity price and the real-time load information yan. However, they did not consider the possibility that EV owners may change their charging behavior in response to the varying prices. Han et al. presented a dynamic pricing and scheduling scheme for EV charging stations while considering grid-to-vehicle (G2V) and vehicle-to-grid (V2G) han. They used a Stackelberg game to characterize the strategic interactions between the “selfish" EV owners and the charging stations. However, they only considered a single charging station in their model. In ban, a price control method was employed to guide EVs to different charging stations while satisfying the predefined QoS and maintaining power grid stability. The authors used a multi-queue system to model the arrival and departure of EVs. Nevertheless, they treated the charging station as a profit-neutral entity, which may not be an appropriate assumption for the real market. In martirano, the authors proposed a scheme called the “Interactive Energy", for the dynamic pricing and electricity delivery of the EV charging services based on the status of the microgrid. However, the overall customer satisfaction was not considered in their analysis. The pricing models proposed in asr and yguo did not incorporate the renewable energy (like wind power or solar power), which is becoming an important energy source. In yguo2, the authors addressed a two-stage framework for the economic operation of a microgrid-like electric vehicle parking deck using a stochastic approach and model predictive control (MPC).
Our work is motivated by the fact that the charging service providers face many uncertainties when determining the appropriate charging prices and managing the electricity storage. In this paper, we consider three types of uncertainties that the service providers may face: (1) the uncertainty of spatial-temporal charging demand at each charging station, (2) the uncertainty of renewable energy generation, and (3) the uncertainty of the electricity price at the wholesale market. We also assume that a charging service provider operates a network of charging stations. As a mediator in the power grid, the service provider purchases the electricity from the wholesale market and resells it to EV owners. We also assume that the service provider owns a storage system that stores the excessive electricity temporarily. Additionally, the service provider can harvest the distributed renewable energy generation, and use it as a supplementary energy source for EV charging.
In our study here, we first employ a linear regression model to estimate the EV charging demand. Specifically, the customer's price elasticity coefficients, reflecting the customer's sensitivity to charging price variation, will be estimated using historical data. Subsequently, we apply the Dynamic Programming (DP) computation algorithm to derive the optimal charging prices and how much electricity to be purchased from the wholesale market based on the current electricity storage and renewable energy forecast.
The main contribution of this paper is a computation framework to help the EV charging service provider calculate the optimal charging prices and determine the appropriate amount of electricity to purchase from the wholesale market in each planning horizon. Our computation framework can deal with the three aforementioned uncertainties and is aimed at striking a balance among the profit, customer satisfaction, and the power grid stability.
In our model, we postulate that there is an EV charging service provider operating a network of charging stations. As a mediator between the power grid and the end customers (i.e., EV owners), the charging service provider purchases electricity from the wholesale market at the day-ahead prices, and resells it to EV owners at the retail charging price. Figure (ref) depicts a general business model for EV charging.
The worldwide deregulation of electricity market (e.g., PJM Interconnection, ERCOT in USA, New Zealand, Singapore, UK markets, etc.) gives birth to the prosperous forward markets and day-ahead markets. The Independent System Operator (ISO) or the Regional Transmission Organization (RTO) calculates the day-ahead market prices through an auction between the power generators and the retailers using the locational marginal pricing (LMP) scheme huisman,lmp,lmp2. We assume that the charging service provider is one of the retailers, buying electricity from the wholesale market and reselling it to EV owners. Let $S=[s_1,s_2,\cdots,s_L]$ denote the set of charging stations. We divide a day into $N$ planning horizons (stages). At the beginning of each horizon, the service provider updates the charging prices, and calculates how much electricity needs to be purchased from the wholesale market. We allow charging prices vary among different charging stations. Let $P_k=[p_{k1},p_{k2},\cdots,p_{kL}](k=1,2,\cdots,N)$ be the charging price vector in the $k$-th horizon, and $o_k$ be the electricity purchase. Currently, the day-ahead market prices are calculated on a hourly basis, so $N=24$. Let $C=[c_1,c_2,\cdots,c_N]$ denote the day-ahead wholesale market prices. The total profit of the service provider in the $k$-th horizon is given by
where $d_{kj}$ is the charging demand at the $j$-th charging station in the $k$-th horizon, and $\sum_{j=1}^Lp_{kj}d_{kj}$ is the total revenue, and $c_ko_k$ is the cost of electricity purchased in the $k$-th horizon.
The charging service provider attempts to achieve the goals of improving the profits, enhancing the customer satisfaction, and maintaining power grid stability. Poor customer satisfaction may hinder the wide adoption of EVs, thus, affecting the development of the entire EV industry. In this sense, the charging service provider cannot be a myopic profit squeezer that maximizes the profit at the expense of customer satisfaction. Various customer satisfaction evaluation methods have been studied in yang,fahrioglu,faranda. In this paper, we use a quadratic function to characterize the overall customer satisfaction of the entire population of EV owners, denoted by $G_k$.
where $\beta$ is the weighting parameter and $E$ is the capacity of the electricity storage system, $\omega$ and $\alpha$ are the shape parameters of this quadratic function. The variable $\phi_k$ is the total electricity consumption (charging demand) of all EV owners in the $k$-th horizon which is defined as
The quadratic functions with different combinations of $\omega$ and $\alpha$ are shown in Figure (ref). We observe that the quadratic function has a minimum value of 0, suggesting that the EV owners are very “unhappy", and a maximum value of 1, suggesting that the EV owners are very “happy". Additionally, Equation ((ref)) is a non-decreasing concave function with a non-increasing first-order derivative. The overall customer satisfaction grows as the total electricity consumption increases. However, the decreasing growth rate suggests that the customer satisfaction tends to get saturated as the electricity consumption increases.
Many studies lopes,kinter,scott have shown that large-scale simultaneous EV charging presents many challenges to the existing power grid pertaining to severe power loss, power grid stability, frequency drift, and voltage fluctuation, etc. In the electric power system, the networked generators cooperatively adjust their outputs to balance the supply and the demand and maintain the power quality. Generally, the power generators hope that the load is predictable and relatively stable (or at least slow-varying). If the load fluctuates too much, the power generators have to ramp up and down frequently, resulting in low efficiency and high maintenance cost. As a result, we do not want the electricity purchase from the wholesale market $o_k$ to fluctuate too much which may create a heavy “burden" on the power grid. We formulate the penalty of EV charging in the following way
where $o_{\textrm{ref}}$ is a reference purchase (or average electricity purchase) and $o_k$ is the electricity purchased in the $k$-th horizon. The variable $\mu$ is the weighting parameter reflecting the sensitivity of electricity purchase fluctuation.
We assume that the charging service provider has an electricity storage with a capacity of $E (\textrm{MWh})$. Let $I_k$ denote the electricity in the storage at the beginning of the $k$-th horizon, and let $u_k$ be the renewable energy generation (i.e. wind power or solar power). Here $u_k$ is the predicted renewable energy. The electricity storage cost in the $k$-th horizon is given as follows
where $\sum_{j=1}^Ld_{kj}$ is the total charging demand in the $k$-th horizon, and $\eta(\$/\textrm{MWh})$ is the unit storage cost. The storage cost includes capital cost, maintenance cost, and power loss due to energy conversion.
Finally, the total utility of the service provider in the $k$-th horizon is given as
Note that the total utility consists of four components---total revenue, customer satisfaction, power grid influence, and electricity storage cost. The values of $\beta$ and $\mu$ reflect the weights of customer satisfaction and EV charging penalty in the total utility function.
Our objective here is to maximize the overall utility by solving the following optimization problem.
where $P_k$ and $o_k$ are , respectively, the charging price vector and electricity purchase in the $k$-th horizon.
To resolve this problem, we are facing two major challenges: (1) accurately estimate the charging demand $\phi_k$, and (2) solve the large-scale optimization problem in a more efficient way. In the following sections, we will discuss these problems in more details.
In this section, we consider the estimation of the charging demand $\phi_k$. The charging demand function characterizes the customer's responsiveness to the fluctuation of charging prices, for EV owners may adjust their charging demand or schedule in response to the variation of charging prices.
In the initial phase of the optimization framework, we do not have the information of the EV owner's responsiveness to the charging prices. We thus apply a linear regression model to learn and predict the charging demand $\phi_k$. For each charging station $j(j=1,2,\cdots,L)$, the charging demand is expressed by
where $\gamma_{0,j}(j=1,2,\cdots, L)$ is the intercept of the $j$-th linear regression equation, and $\gamma_{i,j}=\gamma_{j,i}(i\neq j)$ are the cross-price elasticity parameters, reflecting how the change of the charging price of station $j$ can influence the charging demand at station $i$. And $\gamma_{i,i}$ is the self-price elasticity parameter, reflecting how the change of the charging price of station $i$ can influence its own charging demand.
In this work, we employ the recursive least square (RLS) proakis method to estimate the elasticity demand parameters from historical data. Let $W_j=[\gamma_{0,j},\gamma_{1,j},\cdots,\gamma_{N,j}]$ denote the price elasticity parameter vector relevant to charging station $j(j=1,2,\cdots,L)$. Applying the RLS algorithm, we have the following update formula
where $e_{kj}$ is the prediction error and $\lambda$ is the forgetting factor. In initialization, $H_{0j}$ is the identity matrix and $P_0$ is an all-zero vector.
Note that Equation ((ref)) captures both the spatial and temporal fluctuation of charging demand. The difference in population density, traffic flow, and urbanization level may result in the spatial fluctuation of charging demand. Thus, we use different linear regression equations to estimate different charging stations. On the other hand, the use of RLS algorithm enables us to characterize the temporal fluctuation of charging demand. It keeps track of the most recent changes in customer's charging behavior because the price elasticity parameters will be updated once a new data is observed.
Note that Equation ((ref)) is a complex optimization problem with $N(L+1)$ decision variables and $N(2L+3)$ constraints. It is mathematically cumbersome and hardly feasible to solve this problem in a brute force manner. One approach is to divide the original optimization problem into $N$ independent subproblems. Each horizon corresponds to a subproblem, and then employ the greedy search algorithm. This idea will be further discussed in Subsection 4.1.
On the other hand, we observe that the original problem exhibits the properties of overlapping subproblems and optimal substructure, which can be exploited to solve this problem more efficiently. Here, we apply the dynamic programming (DP) computation algorithm to the original problem. DP is a computation algorithm of solving a large-scale complex problem by partitioning it into a set of smaller and simpler subproblems cormen,bertsekas. By solving and combining these subproblems in a forward (bottom-up) or backward (top-down) fashion, we can obtain the solution to the original problem. In contrast to the brute force approach, DP can significantly accelerate computation speed and save storage. We will discuss DP in Subsection 4.2.
The original optimization problem in Equation ((ref)) aims to maximize the total utility over $N$ horizons. The control variables are “chained" in the sense that the decision variables in the previous horizon can influence the decision variables in the current horizon. For simplicity, we ignore the correlation between adjacent horizons, and try to maximize the utility in each individual horizon. Specifically, we attempt to solve the following problem in the $k$-th horizon,
where $P_k$ and $o_k$ are , respectively, the charging price vector and electricity purchase in the $k$-th horizon. We will use the greedy algorithm as a benchmark in the simulations.
Note that the hourly-based wholesale electricity prices are only posted day ahead. We analyse the dynamic pricing problem with finite horizons (stages) with $N=24$. The system dynamics are expressed by the evolution of some variables, or the system's state variables, under the influence of the decision variables at the beginning of each horizon (stage) bertsekas,nemhauser. The system dynamics are expressed by the following evolution equation
where $I_k$ is the state variable, representing the electricity storage at the beginning of the $k$-th horizon. The variables $u_k$ and $o_k$ are, respectively, the renewable energy and the electricity to be purchased from the wholesale market. The charging demand in the $k$-th horizon is $\phi_k$. Note that $\phi_k$ is actually a function of the charging price vector $P_k$, and the decision variables of the system are $(P_k, o_k)$. The aggregated utility of the service provider from the first horizon to the $N$th horizon is given by
where $\Pi_{N+1}(I_{N+1})$ is the terminal utility incurred at the end of the process. We can assign a heuristic value for the terminal utility. The maximum utility $J_1(I_1)$ is given by the following form
Furthermore, the utility $J_1(I_1)$ can be calculated in a recursive manner as follows
or
where $J_2(I_2)$ is given by
We can apply Equation ((ref)) recursively from the $N$th horizon backward to the first horizon to derive the solution $J_1(I_1)$. The detailed derivation of Equation ((ref)) to Equation ((ref)) is given in Appendix.
Let $X_k=[p_{k1},p_{k2},\cdots, p_{kL},o_k]^{\textrm{T}}$ denote the decision variables. Moreover, the recursive DP formula can be rewritten as one of quadratic programming as follows,
where $Z(X_k)$ is the feasible solutions derived from the constraints in Equation ((ref)). The matrix $\mathbf{Q}$ is given by
where $\Gamma_j(j = 1, 2,\cdots,L)$ is
$B_k$ is
where $\Gamma_0$ is
$r_k$ is
where $J_{k+1}(I_{k+1})$ is the total aggregated utility starting from the ($k+1$)th horizon to the $N$th horizon, which can be calculated using the DP recursive formula. We can treat $J_{k+1}(I_{k+1})$ as a constant value when we calculate $J_k(I_k)$.
There are two principal modules in the dynamic pricing and energy management framework: the charging demand prediction module and the DP module. Figure (ref) illustrates the schematics of the framework. They work collaboratively to make the optimal decisions on charging prices $P_k$ and the electricity purchase $o_k$ for the service provider. The algorithm is summarized below:
The simulation parameters are given in Table 1. We use the historical data of the PJM day-ahead market in our simulations, see Figure (ref). We use the solar radiation data from the National Solar Radiation Data Base solardata as a proxy of the predicted renewable energy generation. For simplicity, we assume that the solar cell efficiency is 20%. The renewable energy generation prediction is shown in Figure (ref). We notice that the solar power generation begins at 8:00 and ends at 17:00 with a peak at 13:00.
We use the greedy algorithm as the benchmark, and compare DP algorithm with the greedy algorithm. Figure (ref) shows the profit increase of DP algorithm (using greedy algorithm as the benchmark). The simulation reveals that DP algorithm achieves up to 9% increase in profit in contrast to the greedy algorithm. The reason why DP algorithm can achieve a higher profit is that it exploits the information of the entire hourly day-ahead prices and the renewable energy prediction to make optimized decisions at each horizon. The decisions made in each horizon are optimized so that the aggregated profit over multiple horizons is maximized. In contrast, the greedy algorithm is a myopic algorithm because it only maximizes the profit in the current horizon without considering the day-ahead prices and the renewable energy generation in the future. Comparing the computational complexity of the two algorithms, we note that greedy algorithm has a linear time complexity $O(N)$, while DP algorithm has a quadratic time complexity $O(N^2)$, where $N$ is the number of planning horizons. Therefore, DP algorithm achieves a higher profit (better performance) at the cost of increased computing time.
This section considers how the profit and customer satisfaction change as the customer satisfaction weighting parameter $\beta$ increases from 0 to 30000 with an interval of 5000. From Figure (ref), we observe that as $\beta$ increases, the customer satisfaction increases and the profit suffers a significant decrease. It is clear that the charging service provider should make a tradeoff between profit maximization and customer satisfaction improvement by choosing a proper weighting parameter $\beta$.
The electricity storage system enables the charging service provider to purchase extra electricity from the wholesale market when the wholesale price is low, and store the unsold electricity for future use when the wholesale price is high. In this simulation, we analyze how this “buy low and sell high" strategy may change as the energy storage cost increases. In Figure (ref), the first three subplots are the electricity purchase with different energy storage costs ($\eta = 0.5,\eta = 1.0, \eta = 1.5$ ), and the last subplot is the day-ahead wholesale market prices. From Figure (ref), we make three observations: (1) The average electricity purchase is 37 MWh in each horizon; (2) When $\eta = 1.5$, the electricity purchase almost does not change. This suggests that the service provider becomes conservative in electricity purchase as the storage cost increase. In other words, the service provider cannot improve the profit through “buy low and sell high" strategy due to the high storage cost; (3) When $\eta = 0.5$ and $\eta = 1.0$, the service provider is likely to purchase more electricity during low-price horizons (from 3:00 to 8:00), and purchase less electricity during high-price horizons (from 11:00 to 19:00). Generally speaking, low electricity storage cost spurs the service provider to adopt an aggressive electricity purchase strategy.
In this section, we investigate the correlation between the charging prices and the electricity storage cost. In the simulation we have 20 charging stations in total, and we randomly choose 3 charging stations to plot Figure (ref). The solid lines represent the charging prices with low storage cost ($\eta = 0.5$), and the dash lines are the charging prices with high storage cost ($\eta = 1.5$).
First, we notice that different charging stations have different charging prices. Second, the charging prices with high storage cost are more volatile than those with low storage cost. When the wholesale prices are low (from 1:00 to 8:00), the charging prices with high storage cost are lower than those with low storage cost. When the wholesale prices are high (from 12:00 to 19:00), the charging prices with high storage cost are higher than those with low storage cost. The reason for the difference is that when the storage cost is low, the service provider can have more electricity reserved in the storage system which can be used in the future when the wholesale electricity price is high. Therefore, the charging prices stay relatively stable over time. As the storage cost increases, electricity storage becomes expensive. Without the “buffer effect" of the electricity storage system, the EV owners are exposed to the varying charging price which is directly influenced by the wholesale market. Hence, a low-cost energy storage system can not only increase the total profit but also act as a buffer to smooth out the fluctuation of the charging prices.
In this paper, a DP based pricing and energy management framework for EV charging stations is studied. The proposed framework aims to strike a balance among three conflicting goals of improving the total profit, enhancing the user satisfaction, and reducing the EV charging impact on the power grid. In this study here, we incorporate the electricity storage system and the renewable energy generation as an energy supplement. To solve the optimization problem, we apply the DP algorithm to calculate the charging prices and the electricity purchase for each planning horizon. The simulation results show that the DP algorithm can obtain higher profits compared with the greedy algorithm. In addition, we observe that the electricity purchase is heavily influenced by the wholesale prices and the energy storage cost. A low-cost energy storage system is beneficial for improving the profit and stabilizing the charging prices.