Source-linked AI summary
Charging Scheduling of Electric Vehicles with Local Renewable Energy under Uncertain Electric Vehicle Arrival and Grid Power Price
Tian Zhang, Wei Chen, Zhu Han, Zhigang Cao
TL;DR
The paper addresses delay-optimal EV charging with uncertain arrivals, renewable supply, prices, and charging requirements under a long-term cost constraint. It maps EVs to charge demands and formulates the problem as an MDP, deriving structural conditions for optimal policies and examining radical and conservative policies numerically. The simulations report that larger battery capacity lowers cost, while queue-length performance improves with larger capacity or more charge points.
Problem
The paper asks how to minimize EV mean waiting time at a renewable-equipped charging station under a long-term grid-cost constraint with stochastic system inputs and random charging energy.
Method
The paper maps each EV to consecutive charge demands, proves queue-length equivalence, and analyzes the resulting constrained scheduling problem through an MDP with a two-dimensional policy.
Results
The analysis derives necessary optimality conditions, identifies state conditions for charging no demand or as many demands as possible, and numerically studies radical and conservative policies.
Takeaways & Limitations
Larger battery capacity lowers cost, while larger battery capacity or more charge points improves average queue-length performance in the reported simulations.
Abstract
from arXiv · showhide
In the paper, we consider delay-optimal charging scheduling of the electric vehicles (EVs) at a charging station with multiple charge points. The charging station is equipped with renewable energy generation devices and can also buy energy from power grid. The uncertainty of the EV arrival, the intermittence of the renewable energy, and the variation of the grid power price are taken into account and described as independent Markov processes. Meanwhile, the charging energy for each EV is random. The goal is to minimize the mean waiting time of EVs under the long term constraint on the cost. We propose queue mapping to convert the EV queue to the charge demand queue and prove the equivalence between the minimization of the two queues' average length. Then we focus on the minimization for the average length of the charge demand queue under long term cost constraint. We propose a framework of Markov decision process (MDP) to investigate this scheduling problem. The system state includes the charge demand queue length, the charge demand arrival, the energy level in the storage battery of the renewable energy, the renewable energy arrival, and the grid power price. Additionally the number of charging demands and the allocated energy from the storage battery compose the two-dimensional policy. We derive two necessary conditions of the optimal policy. Moreover, we discuss the reduction of the two-dimensional policy to be the number of charging demands only. We give the sets of system states for which charging no demand and charging as many demands as possible are optimal, respectively. Finally we investigate the proposed radical policy and conservative policy numerically.
I. INTRODUCTION
The paper formulates EV charging at a renewable-equipped station as delay-optimal scheduling under uncertain arrivals, renewable supply, prices, and charging requirements. It maps EVs to charge demands, establishes queue-length equivalence, and analyzes the resulting constrained MDP.
- Motivation and problem formulation: The station schedules EVs across multiple charge points using local renewable energy, storage, and grid power while minimizing mean waiting time under a long-term cost constraint.EV arrivals, renewable-energy arrivals, and grid prices are modeled as Markov processes.
- Queue mapping: Random charging requirements make direct EV-queue analysis difficult, so each EV is mapped to consecutive charge demands representing its required energy blocks.The number of consecutive demands for an EV equals its required charging energy in blocks.
- MDP formulation: The reconstructed problem is modeled as an MDP whose state includes queue length, demand arrival, battery energy, renewable arrival, and grid price.The policy jointly selects the number of demands charged and the energy allocated from storage.
- System model: The formulation uses discrete time, finite charge-point capacity, Markov renewable and price processes, and energy blocks for charging.At most M EVs can charge in each period, and storage supplies part of the required energy while the grid supplies the remainder.
- Queue mapping: The paper proves that minimizing average charge-demand queue length is equivalent to minimizing average EV queue length.This equivalence permits the scheduling problem to be studied through the charge-demand queue.
III. SIMPLIFIED PROBLEM
The paper simplifies the general random-energy problem by assuming every EV requires one energy block, making the queue mapping an identity. It then formulates the resulting scheduling task as a constrained MDP.
- MDP formulation: The system state is X[n] = (Q[n], A[n], Eb[n], Ea[n], P[n]), and the action is (K[n], W[n]).The state tracks queue, arrivals, stored energy, and price; the action controls charging quantity and stored-energy allocation.
- Optimization problem: The constrained MDP seeks a policy minimizing mean queue delay subject to a long-run cost constraint.A stationary deterministic policy maps each state to a feasible charging action.
- Feasible actions: Charging is limited by the queue length and the M charge points in each period.The feasible number of charged EVs ranges from 0 to min{q[n], M}.
- Simplified problem: The simplified case sets C = 1, so all EVs require the same charging energy E and EVs and demands are interchangeable.Under this assumption, the queue mapping becomes an identity transform.
IV. ANALYSIS OF THE OPTIMAL POLICY
The optimal-policy analysis proceeds by replacing the constrained MDP with an unconstrained formulation, analyzing its discount counterpart, reducing policy dimensionality, and constructing two stationary policies.
- Optimal-policy analysis: The analysis first transforms the constrained MDP into an unconstrained MDP and then studies the corresponding discount MDP.It subsequently examines whether the two-dimensional policy can be reduced to charging-demand decisions alone.
- Policy construction: The paper concludes by proposing radical and conservative stationary deterministic policies from the theoretical results.These policies are used to study the scheduling problem numerically.
A. Transformation to the unconstrained MDP and discount MDP
The paper connects the constrained problem to an unconstrained average-cost MDP and its discounted version, establishing stationary optimal policies and necessary structural conditions.
- Transformation to the unconstrained MDP: For some β > 0, an optimal solution of the unconstrained MDP is also optimal for the original constrained MDP.This provides the bridge from the cost-constrained problem to an unconstrained formulation.
- Discount MDP: A stationary deterministic policy solving the unconstrained average-cost MDP can be obtained as a limit of discount-optimal policies as α → 1.The discount MDP is therefore used to derive an average-cost optimal policy.
- Value-function properties: The discounted value function is increasing in queue length, non-increasing in stored battery energy, and convex in queue length and battery energy.These properties support structural analysis of optimal actions.
- Necessary conditions: An action is not discount-optimal when it both leaves more than q − min{q, M} demands unserved and exceeds storage capacity after renewable arrival.Thus, optimal actions must avoid simultaneously violating these two conditions.
- Necessary conditions: The optimal policy must satisfy the inequality array derived in Lemma 5; if it has one solution, that solution is optimal.The result follows from the necessary condition together with existence of an optimal policy.
C. The average cost optimal policy
The paper analyzes the average-cost optimal policy through constrained and unconstrained MDP formulations, using discount-MDP results to characterize stationary deterministic policies.
- C. The average cost optimal policy: The optimal policy satisfies monotonicity inequalities relating queue length, demand arrival, and the associated value functions.The inequalities compare Z1, Z2, and Z3 across increases in queue-related state variables.
D. Reducing the policy’s dimension
The paper reduces the coupled policy from charging-demand selection and battery allocation to a demand-selection policy, then identifies conditions for charging no demand or as many demands as possible.
- D. Reducing the policy’s dimension: When the number of charging EVs is fixed, greedy battery allocation is optimal, enabling the policy reduction from (k, w) to k.Battery power is allocated as fully as possible because it is free, although the paper presents the broader reduction as a conjecture.
- D. Reducing the policy’s dimension: The battery-energy evolution is reformulated after dimension reduction, and the conjectured reduction can be proved when β ≫1 using the stated lemmas.The paper labels the reduction result a conjecture before specifying this sufficient condition.
- D. Reducing the policy’s dimension: The dimension-reduced policy selects k charging EVs and sets the remaining queue length to u = q − k.This defines a stationary deterministic policy for each state-action pair.
- D. Reducing the policy’s dimension: u = q −min{q, M} is discount optimal in specified states, corresponding to charging as many EVs as possible.If fewer than M EVs wait, all are charged; otherwise, M EVs are selected from the queue head.
- D. Reducing the policy’s dimension: u = q is discount optimal in specified states, corresponding to charging no EV.The cited result is stated for system states satisfying an omitted condition.
- D. Reducing the policy’s dimension: u = q −min{q, M} is average-cost optimal in specified states, while u = q is average-cost optimal in other specified states.These average-cost results are obtained after the corresponding discount-policy analysis.
E. Two stationary deterministic policies
The paper proposes radical and conservative stationary deterministic policies for EV charging. The radical policy prioritizes charging speed without considering the average cost constraint, while the conservative policy enforces the cost constraint period by period.
- Radical policy: The radical policy charges as many EVs as possible and allocates storage-battery energy greedily.If battery energy covers the requirement, grid power is not used; otherwise, the battery is fully allocated and the remainder comes from the grid.
- Radical policy: The radical policy does not consider the average cost constraint.
- Conservative policy: The conservative policy guarantees the average cost constraint by satisfying the cost constraint in every period.
- Conservative policy: The conservative policy first limits each period's charging cost, then charges as many EVs as possible and greedily allocates battery energy.
- Scope assumption: The analysis assumes grid and renewable-generation power are sufficient to stabilize the queue length.Bounds involving average renewable-generation and EV-arrival rates are left for future work.
V. NUMERICAL RESULTS
Simulations examine how arrival rates, renewable supply, storage capacity, charge-point numbers, and cost constraints affect average cost and EV queue length under radical and conservative policies.
- Simulation setup: The simulations use period length τ = 1, energy-block size E = 10, and vary renewable storage capacity, charge-point number, and policy parameters.The radical policy is used for the cost experiments, while the conservative policy is used for the EV queue-length experiment.
- Average cost versus EV arrival: When mean EV arrival ¯A is small, average cost is nearly zero; for large ¯A with many charge points, cost increases roughly linearly.At low arrival, the battery can supply required energy; at high arrival, grid power becomes the main source.
- Average cost versus EV arrival: With few charge points, average cost eventually becomes constant as ¯A increases because charging demands are capped at the number of charge points.The required energy becomes M × E with high probability, making grid consumption and cost constant.
- Average cost versus renewable arrival: Average cost decreases as mean renewable arrival ¯Ea increases, then becomes nearly static when renewable supply is sufficient or storage overflow limits stored energy.For limited capacity such as Emax = 100, overflow can leave grid power necessary even at larger ¯Ea.
- Storage capacity: Larger battery capacity lowers average cost by reducing renewable-energy overflow and waste.The paper states that overflow probability decreases as Emax increases and is zero for infinite capacity.
- Policy implication: When ¯A is below a threshold or ¯Ea exceeds a threshold, the radical policy remains optimal even with the average-cost constraint.The radical policy is optimal for mean EV queue-delay minimization without the average-cost constraint.
- EV queue length: Under the conservative policy, average EV queue length improves as ¯B increases and becomes almost constant beyond a threshold; larger capacity or more charge points improve length performance.Once ¯B is large enough, the charging limit is determined by queue length and charge-point number rather than stored energy.
APPENDIX A PROOF OF LEMMA 1
The proof establishes the relation between EV-queue and energy-demand-queue lengths and verifies monotonicity properties of the discounted value function through feasibility and induction arguments.
- Queue mapping: Queue mapping represents each EV by consecutive charge demands whose number equals its required energy, converting EV-queue analysis into charge-demand-queue analysis.Earlier-arriving EVs also leave no later under the mapped queue, yielding an isotonic mapping.
- Queue mapping: The mapping implies that minimizing mean EV queue length is equivalent to minimizing mean charge-demand queue length.The equivalence follows because service order is preserved by the mapping.
- MDP existence: The unconstrained MDP admits an optimal stationary policy satisfying limiting behavior for all states and achieving the prescribed average-cost bound.The argument invokes ergodicity and results concerning discounted and constrained MDPs.
- Monotonicity proof: The value function is shown to be increasing in queue length by induction over the finite-horizon value iterations.The proof compares feasible action sets in neighboring queue states, separating cases according to the number of charge points.
- Monotonicity proof: The value function is shown to be non-increasing in stored battery energy through the same induction-based comparison of feasible actions.The proof establishes the base cases and then applies the induction hypothesis to adjacent energy states.
APPENDIX F PROOF OF PROPERTY 3
The proof develops a convexity argument for the value function using induction, a minimum-function inequality, and convex combinations of feasible policies.
- Neighboring actions: The proof also derives neighboring-action value differences by applying optimality inequalities to actions with adjusted charging-demand and battery allocations.These inequalities support the displayed relations involving Vα at adjacent queue and energy states.
- Supporting inequality: The proof begins with an inequality showing that a weighted average of two minima is no greater than the minimum of the weighted average arguments.The proposition is verified by considering whether both arguments lie above, below, or on opposite sides of the threshold.
- Convexity induction: The induction step uses the minimum-function proposition and established properties of the value function to preserve convexity under the dynamic-programming recursion.The interpolated action pair remains feasible for the interpolated system state.
- Convexity induction: The value function is proved convex in queue length and stored battery energy by induction on the value-iteration horizon.The base case is Vα,0 = 0, and the induction step combines convexity of the previous value function with feasible interpolated actions.
APPENDIX H PROOF OF LEMMA 7
The proof characterizes boundary charging decisions by restricting the policy set and deriving contradictions when those boundary actions are assumed nonoptimal.
- Policy restriction: Based on Conjecture 1, the proof restricts attention to policies whose battery allocation is a nonnegative function of the number of charging demands.This reduces the policy set before comparing neighboring actions.
- Action comparison: Optimality comparisons yield an upper bound involving Z(u*) and the grid-price term for the relevant charging action.The second half of the lemma follows by combining the neighboring-action comparison with Lemma 3.
- Boundary policies: The proof shows by contradiction that the action u = q − min{q, M} must be optimal in its designated state conditions.Assuming it is not optimal produces an inequality conflicting with the derived bound on Z(u*).
- Boundary policies: A parallel contradiction establishes the optimality of charging all queued demands, u = q, under the corresponding state conditions.The contradiction uses Z(q) ≥ Z(u* + 1) together with the grid-price bound.