Microgrid Revenue Maximization by Charging Scheduling of EVs in Multiple Parking Stations
For microgrid operators managing multiple EV charging stations, this work provides a near-optimal, polynomial-time scheduling algorithm that significantly reduces peak demand and electricity costs.
This paper tackles the NP-hard problem of scheduling EV charging across multiple parking stations in a microgrid to maximize revenue under global peak constraints. The proposed primal-dual algorithm achieves 98% of optimal performance, reduces peak demand by 16% over existing methods, and improves resource utilization.
Nowadays, there has been a rapid growth in global usage of the electronic vehicles (EV). Despite apparent environmental and economic advantages of EVs, their high demand charging jobs pose an immense challenge to the existing electricity grid infrastructure. In microgrids, as the small-scale version of traditional power grid, however, the EV charging scheduling is more challenging. This is because, the microgrid owner, as a large electricity customer, is interested in shaving its global peak demand, i.e., the aggregated demand over multiple parking stations, to reduce total electricity cost. While the EV charging scheduling problem in single station scenario has been studied extensively in the previous research, the microgrid-level problem with multiple stations subject to a global peak constraint is not tackled. This paper aims to propose a near-optimal EV charging scheduling mechanism in a microgrid governed by a single utility provider with multiple charging stations. The goal is to maximize the total revenue while respecting both local and global peak constraints. The underlying problem, however, is a NP-hard mixed integer linear problem which is difficult to tackle and calls for approximation algorithm design. We design a primaldual scheduling algorithm which runs in polynomial time and achieves bounded approximation ratio. Moreover, the proposed global scheduling algorithm applies a valley-filling strategy to further reduce the global peak. Simulation results show that the performance of the proposed algorithm is 98% of the optimum, which is much better than the theoretical bound obtained by our approximation analysis. Our algorithm reduces the peak demand obtained by the existing alternative algorithm by 16% and simultaneously achieves better resource utilization.