Report

Stochastic Distributed Protocol for Electric Vehicle Charging with Discrete Charging Rate Lingwen Gan, Ufuk Topcu, Steven Low California Institute of Technology Electric Vehicles (EV) are gaining attention • Advantages over internal combust engine vehicles • On lots of R&D agendas Challenges of EV • EV itself • Integration with the power grid – Overload distribution circuit – Increase voltage variation – Amplify peak electricity load demand Uncoordinated charging Coordinated charging Non-EV demand time Coordinate charging to flatten demand. Related works • Centralized charging control – – – [Clement’09], [Lopes’09], [Sortomme’11] Easy to obtain global optimum Difficult to scale • Decentralized charging control – – – [Ma’10], [GTL’11] Easy to scale Difficult to obtain global optimum This work: • Decentralized • Optimally flattened demand • Discrete charging rate Continuous charging rate Outline • EV model and optimization problem – Continuous charging rate – Discrete charging rate • Results with continuous charging rate [GTL’11] • Results with discrete charging rate EV model with continuous charging rate EV n plug in : charging profile of EV n deadline time Area = Energy storage (pre-specified) Convex EV model with discrete charging rate EV n plug in deadline Finite time Global optimization: flatten demand 1 Utility : charging profile of EV n 0.9 0.8 EV 1 EV N 0.7 0.6 0.5 demand base demand 0.4 20:00 0:00 4:00 8:00 12:00 16:00 time of day Optimal charging profiles = solution to the optimization 20:00 Continuous / Discrete charging rate Flatten demand: Continuous: convex optimization Discrete: discrete optimization plug in deadline Outline • EV model and optimization problem – Continuous charging rate – Discrete charging rate • Results with continuous charging rate [GTL’11] • Results with discrete charging rate Distributed algorithm (continuous charging rate) [GTL’11]: L. Gan, U. Topcu and S. H. Low, “Optimal decentralized protocols for electric vehicle charging,” in Proceeding of Conference of Decision and Control, 2011. Utility EVs “cost” penalty Both the utility and the Evs only needs local information. Convergence & Optimality Utility EVs calculate Thm [GTL’11]: The iterations converge to optimal charging profiles: Outline • EV model and optimization problem – Continuous charging rate – Discrete charging rate • Results with continuous charging rate [GTL’11] • Results with discrete charging rate Difficulty with discrete charging rates Utility EVs calculate Discrete optimization Need stochastic algorithm plug in deadline Stochastic algorithm to rescue 1 plug in deadline Discrete optimization over Convex optimization over Avoid discrete programming 1 Stochastic algorithm to rescue 1 plug in deadline 1 Discrete optimization over Convex optimization over sample Able to spread charging time, even if EVs are identical Challenge with stochastic algorithm • Examples of stochastic algorithm – Genetic algorithm, simulated annealing – Converge almost surely (with probability 1) – Converge very slowly • In order to obtain global optima • Do not have equilibrium points • What we do? – Develop stochastic algorithms with equilibrium points. – Guarantee these equilibrium points are “good”. – Guarantee convergence to equilibrium points. Tool: supermartingale. Supermartingale Def: We call the sequence , (a) (b) a supermartingale if, for all Thm: Let be a supermartingale and suppose that uniformly bounded from below. Then For some random variable . are Distributed stochastic charging algorithm 1 1 The objective value is a supermartingale. Interpretation of the minimization To find the distribution, we minimize Average load of others Direction to shift Shift in the direction to flatten the average load of others. Challenge with stochastic algorithm • Examples of stochastic algorithm – Genetic algorithm, simulated annealing – Converge almost surely (with probability 1) – Converge very slowly • In order to obtain global optima • Do not have equilibrium points • What we do? – Develop stochastic algorithms with equilibrium points. – Guarantee these equilibrium points are “good”. – Guarantee convergence to equilibrium points. Tool: supermartingale. Equilibrium charging profile Def: We call a charging profile charging profile, provided that equilibrium for all k≥1. Genetic algorithm & simulated annealing do not have equilibrium charging profiles. Thm: (i) Algorithm DSC has equilibrium charging profiles; (ii) A charging profile is equilibrium, iff it is Nash equilibrium of a game; (iii) Optimal charging profile is one of the equilibriums. Near optimal Thm: Every equilibrium has a uniform sub-optimality ratio bound When the number of EVs is large, very close to optimal. Finite convergence Thm: Algorithm DSC almost surely converges to (one of) its equilibrium charging profiles within finite iterations. Genetic algorithm & simulated annealing never converge in finite steps. Fast convergence Iteration 6~10 Iteration 1~5 demand 1.2 1.2 1 1 0.8 0.8 0.6 0.6 0.4 0.4 0.2 20:00 4:00 12:00 20:00 0.2 20:00 Iteration 11~15 4:00 12:00 20:00 Iteration 16~20 1.2 1.2 1 1 0.8 0.8 Stop after 100.6iterations 0.6 0.4 0.2 20:00 base demand 0.4 4:00 12:00 20:00 0.2 20:00 time of day 4:00 12:00 20:00 Close to optimal Demand (kW/house) Close to flat Theoretical sub-optimality bound 0.03 0.025 Suboptimality 0.02 ratio 0.015 0.01 0.005 0 40 80 120 160 200 # EVs in 100 houses Always below 3% sub-optimality. 240 Summary • Propose a distributed EV charging algorithm. – Flatten total demand – Discrete charging rates – Stochastic algorithm • Provide theoretical performance guarantees – Converge in finite iterations – Small sub-optimality at convergence • Verification by simulations. – Fast convergence – Close to optimal. suboptimality 0.03 0.025 0.02 0.015 0.01 0.005 0 40 80 120 160 200 240