Source-linked AI summary
A Model Predictive Control Approach for Low-Complexity Electric Vehicle Charging Scheduling: Optimality and Scalability
Wanrong Tang, Ying Jun Zhang
TL;DR
PEV charging must be scheduled without knowing future arrivals, even though solving the resulting continuous dynamic program can be prohibitively expensive. The paper proposes an MPC-based Expected Load Flattening algorithm, analyzes its performance for arbitrary exogenous-demand distributions, and reports near-optimal performance with O(T^3) complexity that becomes O(1) under first-order periodic demand.
Problem
PEV charging scheduling must minimize integration cost and grid impact when future charging demand is unavailable but its statistics can be estimated.
Method
The paper uses an MPC-based Expected Load Flattening algorithm that replaces future exogenous variables with expectations and exploits load-flattening structure.
Results
ELF performs very close to the optimal online algorithm, with relative performance loss no more than 0.38% in the reported evaluation.
Takeaways & Limitations
The method provides O(T^3) complexity generally and can achieve O(1) complexity under a first-order periodic arrival process.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
The paper formulates online PEV charging under uncertain future arrivals as a continuous-state, continuous-action dynamic program and develops a low-complexity MPC-based solution. Its load-flattening structure supports optimal allocation, broad performance analysis, and scalability under periodic demand.
- Problem setting: Future PEV arrivals are unknown, so scheduling uses estimated statistical information rather than non-causal demand knowledge.The problem concerns random arrivals, demands, and departure times, with charging demands required before deadlines.
- Problem setting: The online scheduling problem is a finite-horizon dynamic program with continuous state and action spaces, making standard numerical solutions prohibitively complex.Nested future-arrival expectations and discretization create complexity that can grow exponentially with the horizon and state or decision dimensions.
- Proposed approach: The proposed MPC-based Expected Load Flattening algorithm has O(T^3) complexity and requires only expected demand values rather than full arrival distributions.The approach replaces exogenous random variables with expectations and exploits the load-flattening structure of the expected-value problem.
- Structural result: The optimal aggregate charging rate is independent of the strictly convex cost function and minimizes total-load variance under the scheduling constraints.The aggregate rate can be converted into individual PEV charging through earliest-deadline-first scheduling.
B. Online PEV Charging problem
The online PEV charging problem schedules charging using current causal information and statistical information about future demand. It is formulated as finite-horizon dynamic programming with continuous state and action spaces, but standard numerical solutions can be prohibitively complex.
- Problem formulation: Online scheduling uses future-demand statistics, base load, and the remaining demands and deadlines of arrived PEVs.The charging rate is determined from information available at the current time; future arrivals are not known causally.
- Problem formulation: The system state aggregates unfinished charging demand by deadline rather than tracking each PEV individually.This aggregation follows because the schedule depends on total demand that must be completed by each future time.
- Dynamic programming formulation: The online problem is a finite-horizon dynamic program with continuous state and decision spaces.Its state transition incorporates random PEV arrivals and the evolution of unfinished demands.
- Feasibility constraints: The dynamic-programming constraints enforce meeting charging demands before deadlines and prevent cumulative charging from exceeding cumulative arrivals.These constraints characterize feasible charging schedules over time.
- Computational challenge: Standard numerical methods can have complexity that grows exponentially with the time span and state and decision dimensions.Nested future-arrival expectations and discretization create a curse of dimensionality.
III. MPC-BASED ONLINE CHARGING ALGORITHM
The paper replaces future random variables with expected values and exploits load flattening to design the low-complexity online ELF algorithm. The method repeatedly updates the schedule as new arrivals are observed while preserving feasibility.
- MPC formulation: The MPC approach replaces exogenous random variables with their expected values to obtain a simpler deterministic problem.Expected values are easier to estimate than higher-order distributional statistics.
- Algorithm design: The online ELF algorithm exploits the load-flattening structure of the expected-value problem instead of using generic convex optimization.It balances charging load across future time slots by searching maximum-density intervals.
- Online updates: At each time stage, the algorithm solves the expected-value problem and resolves it after incorporating newly realized PEV arrivals.This receding-horizon update produces a sequence of charging decisions.
- Feasibility: The solution remains feasible because its charging constraints include those of the original online problem.Thus, current parking PEV demands are guaranteed to be fulfilled before departure.
- Complexity: The online ELF algorithm has computational complexity O(T^3), lower than the O(T^3.5) complexity of the interior point method.The load-flattening construction also supports a later reduction to O(1) under first-order periodic arrivals.
B. Optimality Analysis
The analysis evaluates the MPC approximation through the Value of the Stochastic Solution and proves that its performance gap is bounded for any distribution of future charging-demand arrivals. This provides theoretical support for using expected-value MPC in the online problem.
- Optimality metric: The Value of the Stochastic Solution measures the gap between the optimal online solution and the expected-value solution.The analysis uses expected objective values for offline, online, and expected-value problems.
- MPC approximation: MPC replaces random variables with expected values regardless of their distribution functions.The analysis examines whether this approximation remains justified despite potentially distribution-dependent performance loss.
- Proof strategy: The analysis bounds the expected-value objective from above and uses a lower bound on the offline objective to bound the online objective.This route is chosen because directly analyzing the online objective is generally difficult.
- Theoretical guarantee: Theorem 3 states that the VSS is bounded for any distribution of the random variables.The theorem follows from bounds established for the offline and expected-value objective terms.
- Interpretation: The paper notes that the observed performance gap is often much smaller than the VSS bound.The numerical evaluation is identified as the place where this empirical behavior is examined.
IV. ONLINE ELF ALGORITHM UNDER FIRST-ORDER PERIODIC RANDOM PROCESSES
Under first-order periodic arrivals, online ELF restricts its maximum-density search to one period and achieves complexity independent of the total horizon T. The reduction applies because arrival means repeat periodically even though individual arrivals remain uncertain.
- First-order periodicity means the mean arrival process is periodic, while actual arrival realizations remain uncertain and non-periodic.
- The algorithm replaces searching across the full horizon with considering expected arrivals over one period.The period length is p, and the maximum parking time over the period is denoted by ˆe.
- The search region is decomposed into three subregions, with maximum densities used to identify the overall maximum-density interval.A reduced region within [k + 1, k + ˆe] supports calculating the remaining subregion maxima through Lemma 1.
- When ¯j < ¯i + p, the maximum-density interval is [¯i, ¯j], and the search region ends at ¯j.
- When ¯j ≥ ¯i + p, the maximum-density interval is [¯i, ¯j + (r − 1)p], and the search region ends at that extended endpoint.
- The resulting search depends only on [k + 1, k + ˆe], reducing online ELF complexity from O(T^3) to O(1).Thus, the computational complexity does not increase with system time T.
B. First-order Stationary Process
For first-order stationary demand, the optimal charging solution admits a closed-form characterization. Simulations show that online ELF closely tracks the optimal online algorithm and substantially outperforms AVG in relative performance loss.
- B. First-order Stationary Process: First-order stationarity makes the statistical mean depend on relative time difference rather than absolute time.
- B. First-order Stationary Process: The stationary mean vector can be represented as µ = [ν, µ1, µ2, · · · , µ¯e, 0, · · · , 0], where ¯e is the maximum parking time.
- B. First-order Stationary Process: Lemma 2 places the maximum-density intervals for two search regions at [k, T] and [k + 1, T].
- B. First-order Stationary Process: The largest of X, Y, and Z determines the maximum-density interval and the charging rate selected at time k.
- A. Average Performance Evaluation: The simulations compare ELF with the SAA-based optimal solution and the fixed-rate online AVG heuristic under light, moderate, and heavy traffic.The simulated system spans 24 hours with 10-minute time slots, using Poisson arrivals and exponentially distributed parking times.
- A. Average Performance Evaluation: 0.38% maximum relative performance loss is reported for ELF, compared with up to 5.82% for AVG.The ELF result is reported alongside VSS no greater than 0.1536.
- A. Average Performance Evaluation: 6% relative performance loss would correspond to $58060 in extra annual electricity cost for the illustrative charging-station scenario.
B. Complexity of The Online Algorithm ELF
The online ELF algorithm is evaluated for charging performance and computational complexity against optimal, AVG, and ORCHARD baselines. Simulations show near-optimal performance and computational time comparable to ORCHARD.
- Complexity evaluation: The study compares ELF’s CPU computational time with optimal online, truncated SAA, AVG, and ORCHARD algorithms.
- Comparison with ORCHARD: ELF has better average performance than ORCHARD, while their CPU computational times are similar.
- Algorithmic complexity: The paper’s proposed MPC-based online algorithm has O(T^3)-complexity and can become scalable under a first-order periodic load-demand process.
APPENDIX
The appendix proves feasibility of earliest-deadline-first scheduling by induction over time stages. At each stage, EDF prioritizes PEVs with the earliest departure deadlines.
- Inductive feasibility proof: EDF scheduling first charges PEVs whose deadlines occur at the earliest time stage.
- Inductive feasibility proof: The induction hypothesis assumes EDF can fulfill all PEVs departing by time stage m.
- Inductive feasibility proof: After meeting deadlines at stage m, EDF serves PEVs departing at stage m + 1 before those with later deadlines.
- Inductive feasibility proof: The argument concludes that PEVs with deadline m + 1 can be fully charged under EDF.
- Inductive feasibility proof: Combining the induction steps establishes feasibility for all PEVs with deadlines through stage m + 1.
B. Proof of Theorem 2:
The proof uses KKT conditions and strict convexity to characterize optimal charging across time slots. It concludes that the optimal charging solution is invariant to the chosen strictly convex increasing cost function and flattens total load.
- KKT characterization: The KKT conditions separate charging cases according to whether a PEV receives positive charging at a time slot.
- Load comparison: Strict monotonicity of f′(s_t + l_t) links marginal-cost comparisons to comparisons of optimal total loads.
- KKT characterization: When a PEV is charged at two time slots, the corresponding marginal costs are equal through the optimality conditions.
- Objective-function invariance: The proof compares two strictly convex objective functions and uses contradiction to establish equality of their optimal charging solutions.
- Objective-function invariance: The optimal charging solution s*_t is the same for any strictly convex function f(s_t + l_t).
- Load flattening: The common optimal solution is a load-flattening solution equivalent to minimizing a quadratic total-load objective.
C. Proof of Proposition 1:
The proof establishes convexity of the optimal value function with respect to the demand pattern. It combines convex feasible schedules with convex charging costs and Jensen’s inequality.
- Convexity proof: The argument establishes that Ψ1(Ξ) is convex over the set of demand patterns Ξ.
- Convexity proof: For two demand patterns, a convex combination of their optimal schedules remains feasible because the constraints are linear.
- Convexity proof: Convexity of f(s_t + l_t) bounds the cost of the combined schedule by the corresponding combination of costs.
- Jensen bound: The proof also relates aggregate charging across time stages to total charging demand and applies Jensen’s inequality.
E. Proof of Lemma 1:
The proof considers two cases for comparing interval densities in region Π3. Depending on the overlap condition, extending the interval by p either increases density successively or decreases it, identifying the maximizing interval.
- When ¯j ≥ ¯i + p, repeatedly extending [¯i, ¯j] by p increases its density over region Π3.The resulting maximum-density interval is [¯i, ¯j + (r − 1)p].
- In the first case, the maximizing endpoints are ˆi3 = ¯i and ˆj3 = ¯j + (r − 1)p.
- For the region with fixed i = k, the proof likewise sets ˆj2 = ¯j + (r − 1)p.
- When ¯j < ¯i + p, repeatedly extending [¯i, ¯j] by p decreases its density over region Π3.The original interval [¯i, ¯j] therefore has maximum density.
- In the second case, the maximizing endpoints are ˆi3 = ¯i and ˆj3 = ¯j.The corresponding maximum-density expression follows in the proof.
- The proof concludes after establishing the stated maximum-density cases.
F. Proof of Lemma 2:
The proof characterizes maximum-density intervals by establishing monotonicity of ρ(i, j) with respect to interval endpoints. It uses these monotonicity results to identify maxima on intervals beginning at k and k + 1.
- ρ(i, j) denotes the maximum density of interval [i, j].
- For fixed i, proving ρ(i, j) ≤ ρ(i, j + 1) shows that maximum density is achieved at j = T.
- The established monotonicity implies that Y is the maximum density of [k, j] over j = k + ¯e + 1, · · · , T.
- For intervals with k + 1 ≤ i ≤ j ≤ T, the density is expressed using the sequence µ_t and an additive ν term.
- Showing that ρ(i, j) is non-decreasing in j and non-increasing in i identifies the maximum on [k + 1, T].
- The proof concludes after deriving the required monotonicity implications.