Optimal Scheduling for Electric Vehicle Charging With Discrete Charging Levels in Distribution Grid

To accommodate the increasing electric vehicle (EV) penetration in distribution grid, coordinated EV charging has been extensively studied in the literature. However, most of the existing works optimistically consider the EV charging rate as a continuous variable and implicitly ignore the capacity limitation in distribution transformers, which both have great impact on the efficiency and stability of practical grid operation. Towards a more realistic setting, this paper formulates the EV coordinated discrete charging problem as two successive binary programs. The first one is designed to achieve a desired aggregate load profile (e.g., valley-filling profile) at the distribution grid level while taking into account the capacity constraints of distribution transformers. Leveraging the properties of separable convex function and total unimodularity, the problem is transformed into an equivalent linear program, which can be solved efficiently and optimally. The second problem aims to minimize the total number of on-off switchings of all the EVs' charging profiles while preserving the optimality of the former problem. We prove the second problem is NP-hard and propose a heuristic algorithm to approximately achieve our target in an iterative manner. Case studies confirm the validity of our proposed scheduling methods and indicate our algorithm's potential for real-time implementations.