A Novel Online Scheduling Algorithm and Hierarchical Protocol for Large-Scale EV Charging Coordination

For electric vehicle (EV) charging coordination, relaxation and approximation methods are usually employed to improve scheduling efficiency in solving integer linear programming (ILP) problems. Nevertheless, they have a few inherent flaws, such as frequent charging interruption and large deviation in final SOC. Based on the recursive method, this paper proposes a search-swapping algorithm (SSA) for optimal approximation. It leverages the non-aftereffect property of charging scheduling to approximate the optimal solution as well as uses single recursion instead of multiple recursion to reduce computation cost from exponential time to polynomial time. Compared with the conventional algorithms, it has much higher efficiency, less charging interruption, and better final SOC uniformity. Furthermore, a single-round interactive protocol is designed for hierarchical coordinated framework to achieve power dispatch. Numerous simulations show that the SSA has outstanding efficiency and satisfactory optimality.