Online EV Charging Scheduling with On-Arrival Commitment

The rapid proliferation of electric vehicles has resulted in a drastic increase in the total energy demand of EVs. Given the limited charging rate capacity of charging stations and uncertainty of EV arrivals, the aggregate demand might go beyond the charging station capacity, even with proper scheduling. This paper formulates a social welfare maximization problem for EV charging scheduling with charging capacity constraint. Even though the underlying problem is linear, it is difficult to tackle since the input to the problem, i.e., the charging profile of EVs, reveals in online fashion. We devise charging scheduling algorithms that not only work in the online scenario, but also provide the following two key features: 1) on-arrival commitment; respecting the capacity constraint may hinder fulfilling charging requirement of the deadline-constrained EVs entirely. Therefore, committing a guaranteed charging amount upon arrival of each EV is highly essential; 2) (group)-strategy-proofness as a salient feature to promote EVs to reveal their true type and do not collude with other EVs. Extensive simulations using real traces demonstrate the effectiveness of our online scheduling algorithms as compared to the optimal non-committed offline solution.