Electric vehicles (EVs) can charge their battery from smart grid (G2V) through charging stations located at different parts of the city. However, charging of EVs in a large scale without coordination to the grid may cause grid failure. Therefore, coordinated charging of EVs is an important problem. In this paper, we formulate a bi-objective charge scheduling optimization problem that attempts to minimize the average charging cost while maximizing the number of EVs charged.
We refer to this problem as the Minimum Cost Maximum EV Charging Problem where mobile EVs communicate their charging preferences apriori to the aggregator and the aggregator schedules EVs to different charging stations in their route so that the objective is met, and the grid remains safe. We first prove that the problem is NP-complete in the strong sense. An upper bound is proved for the number of EVs charged. Two greedy heuristics are then proposed to solve the problem. Detailed simulation results for different city traffic scenarios show that the number of EVs charged as achieved by the heuristics proposed is close to the upper bound proved with reasonably low cost.