Distributed Routing and Charging Scheduling Optimization for Internet of Electric Vehicles

In this paper, we consider an Internet of Electric Vehicles (IoEV) powered by heterogeneous charging facilities in the transportation network. In particular, we take into account the state-of-the-art vehicle-to-grid (V2G) charging and renewable power generation technologies implemented in the charging stations, such that the charging stations differ from each other in their energy capacities, electricity prices, and service types (i.e., with or without V2G capability). In this case, each electric vehicle (EV) user needs to decide which path to take (i.e., the routing problem) and where and how much to charge/discharge its battery at the charging stations in the chosen path (i.e., the charging scheduling problem) such that its journey can be accomplished with the minimum monetary cost and time delay. From the system operator's perspective, we formulate a joint routing and charging scheduling optimization problem for an IoEV network, and show that the problem is NP-hard in general. To tackle the NP-hardness, we propose an approximate algorithm that can achieve affordable computational complexity in large-size IoEV networks. The proposed algorithm allows the routing and charging solution to be calculated in a distributed manner by the system operator and EV users, which can effectively reduce the computational complexity at the system operator and protect the EV users' privacy and autonomy. Besides, a proximal method is introduced to improve the convergence rate of the proposed algorithm. Extensive simulations using real world data show that the proposed distributed algorithm can achieve near-optimal performance with relatively low computational complexity in different system set-ups.