Optimal Supercharge Scheduling of Electric Vehicles: Centralized Versus Decentralized Methods

The contemporary problem of scheduling the recharge operations of electric vehicles (EVs) has gained a lot of research attention. This is particularly true given the governmental and industrial confidence in a bright future for EVs accompanied with the widespread installation of an enormous number of charging stations across the world. As such, this paper addresses the delay-optimal scheduling of charging EVs at several charging stations (CSs) each with multiple charging outlets. At first, a centralized optimization framework is formulated using an integer linear problem (ILP) that accounts for the delayed arrival of EVs to CSs and the randomness in the requested recharge time interval. Simulation results showed the efficacy of the ILP model when compared to naive as well as sophisticated scheduling heuristics. Next, motivated by the scalability issues of the ILP model, this paper then proposes a distributed game-theoretical approach where each EV communicates with its selected CS and iterates on modifying its strategy until all EVs converge to selecting an appropriate CS that minimizes their waiting times for receiving services. The distributed game-theoretical approach recorded promising results especially when compared to the well-known shortest job first scheduling algorithm. Further, unlike the other approaches, which normally are centralized and suited for offline scheduling, the game-based method is suited for online scheduling since it played at anytime a batch of EVs requests charging services. The running time of the game is remarkably small and outperforms all other heuristics and its convergence to Nash equilibrium is guaranteed after only small number of iterations.