Mobility aware scheduling for imbalance reduction through charging coordination of electric vehicles in smart grid

Electric vehicles (EVs) are being introduced by different manufacturers as an environment-friendly alternative to vehicles with internal combustion engines. The number of EVs is expected to grow rapidly in the coming years which will act as distributed loads in the demand side of the smart grid. On the supply side, an aggregator has to predict a load schedule 12-36 h in advance to charge the EVs and purchase energy accordingly from the day-ahead market. The goal of the aggregator is to schedule the EVs at different charging stations along the route of the EVs for charging so that the energy imbalance between the energy purchased and the energy consumed by the EVs is minimized while maximizing the number of EVs charged. In this work, we refer to this problem as the Bounded Maximum Energy Usage Maximum EV Charging Problem where mobile EVs communicate their charging preferences to the aggregator and the aggregator schedules EVs to different charging stations in their route so as to maximize both the purchased energy utilization (and therefore, minimum energy imbalance) and the number of EVs charged. We first prove that the problem is NP-complete. A pseudo-polynomial algorithm is proposed for a restricted version of the problem that can act as an upper bound for the energy usage. We also give an upper bound for the number of EVs charged. An offline and an online heuristic are then proposed to solve the problem. Detailed simulation results in different city traffic scenarios are presented to show the performance of the algorithms.