I. Introduction
Electric vehicles (EVs) have attracted enormous attention in recent years due to their potential in mitigating energy crises and air pollution. However, when large-scale EVs are connected to the power grid (smart grid [1]), the instantaneous charging load may cause a significant impact on the power grid [2]. At the same time, the large-scale access of renewable energy puts forward higher requirements for the regulation capacity of the power grid [3]. Therefore, reasonable battery energy replenishment scheduling is needed.