Scheduling Of EV Battery Swapping

We are at the cusp of a historic transformation of our traditional power systems towards more sustainable,robust,reliable and resilient smart grids.Smart grids incorporate advanced sensing,communication,computation and control to(a)accommodate more distributed energy resources,e.g.,renewables,storage,EVs,etc.;(b)involve the load side actively in power system operation;(c)implement distributed control frameworks to enhance stability of power systems;(d)be adaptive and resilient to fault conditions.As one of the most representative CPSs,smart grids have attracted a lot of interest from both industry and academia.EVs,as a core part of smart grids,are not only zero-emission but also able to function as both load and storage.They can play a key ancillary role in power system operation,e.g.,renewable integration,demand response,frequency regulation,etc.In addition,EVs bridge power networks with transportation networks,another typical CPS.EVs couple these two systems tightly through their mobility and energy carrier nature.Current research on EVs is centered around exploiting their charging flexibility.A great amount of previous literature takes advantage of abundant charg-ing time to schedule charging with the aim of improving individual/system utility based on the fact that EVs are usually used for commuting.However,range anxiety and long charging time are still the bottlenecks of EV prevalence.Before a breakthrough in battery technologies,new business models of EVs are still the focus of research.Currently battery swapping is the most promising EV refueling method in addition to charging and has been locally put into use.The battery swapping mode is to unload the depleted battery from an EV and replace it with a fully-charged one such that the EV can be refueled up in a short time.This decouples the charging and operation of EVs,thus reducing range anxiety.However,there are still many challenges in practical implementation of battery swapping,for instance,the mechanical tear and wear when plugging and plucking batteries,coordination of battery charging and swapping and battery reserves at stations.One urgent dilemma to be resolved is the contradiction between the explosive growth of EVs and the relatively slow penetration of supply equipment-battery swapping stations.Although the battery swapping mode is efficient,the temporary shortage in fully-charged batteries could result in congestion and long queues at stations,thus significantly lowering the system efficiency.This thesis focuses on the current practical situation where battery swapping stations have limited service capability,investigates scheduling of EV battery swapping in multiple practical scenarios while taking into account the influence of power systems and transportation systems,and aims to address two most prominent practical issues in current battery swapping practices.The main contributions of this thesis are1.We present an introduction to the development and the state of the art of EVs in smart grids,as well as the prospect of battery swapping,the challenges it faces in real practices and the necessity of its scheduling.2.A scheduling problem for EV battery swapping that takes into account station congestion is investigated.We establish a discrete-time station assignment model for battery swapping that takes into account traffic factors,e.g.,EVs*travel time and distance,and reflects the impact of assignments on station congestion,defined as the number of waiting EVs.In particular,at each time slot an operator optimally assigns stations to a set of EVs that need battery swapping in a way that minimizes both the total EVs'cost to travel to their assigned stations and the total congestion levels at these stations.The problem is a binary program with nonlinear temporal and spatial couplings.However,we show that it is polynomial-time solvable by reducing it to the standard minimum weight perfect bipartite matching problem.This leads to a solution based on the Hungarian algorithm for bipartite matching problems.3.Then we extend the above model to a more practical continuous-time online setting.Suppose EVs send their battery swapping requests to an operator when their batteries are running low.The operator instantly assigns stations in response to these requests based on real-time locations of the requesting EVs and the availability of fully-charged batteries at the stations.with the same aim of minimizing the total EV cost and station congestion.We design a simple and efficient online algorithm for station assignment that exploits the above bipartite matching approach and achieves a tight(optimal)competitive ratio under mild conditions.4.A scheduling problem for EV battery swapping that takes into account power system opera-tion is investigated.We propose to coordinate battery swapping such that EVs can make the most efficient use of currently available batteries in the system and meanwhile the operation of distribution networks is jointly optimized.We formulate an optimal scheduling problem for battery swapping that assigns to each EV a best station to swap its depleted battery.The station assignments not only determine EVs' travel distance,but also impact significantly the power flows on a distribution network.The schedule aims to minimize a weighted sum of EVs' cost(travel distance)and electricity generation cost over both station assignments and power flow variables,subject to EV range constraints,grid operational constraints and AC power flow equations.This joint battery swapping and OPF problem is nonconvex and com-putationally difficult for two reasons.First,AC power flow equations are nonlinear.Second,the station assignment variables are binary.We devise an efficient centralized solution that applies the recently developed SOCP relaxation of OPF and generalized Benders decom-position to compute a global optimum and is suitable for cases where the distribution grid,stations,and EVs are managed centrally.5.We extend the above joint battery swapping and OPF problem to a more general distributed scenario.The centralized solution will not be suitable for an equally(if not more)likely future business model where the distribution grid is managed by a utility company,stations are managed by a station operator(or multiple station operators),and EVs may be managed by individual drivers(or multiple EV groups,e.g.,taxi companies in the electric taxi case).Therefore,we propose two distributed solutions based on ADMM and dual decomposition respectively,where separate entities make their individual decisions but coordinate through information exchanges that do not involve their private information in order to jointly solve the global problem.Our distributed solutions preserve private information and are more suitable for general scenarios.The thesis concludes with directions for future research.