Targeted optimal-path problem for electric vehicles with connected charging stations

Path planning for electric vehicles (EVs) can alleviate the limited cruising range and “range anxiety”. Many existing path optimization models cannot produce satisfactory solutions due to the imposition of too many assumptions and simplifications. The targeted optimal-path problem for electric vehicles (EV-TOP), which is proposed in the paper, aims at identifying the targeted optimal path for EVs under the limited battery level. It minimizes the travel cost, which is composed of the travel time and the total time that is spent at charging stations (CSs). The model is much more realistic due to the prediction and the consideration of the waiting times at CSs and more accurate approximations of the electricity consumption function and the charging function. Charging station information and the road traffic state are utilized to calculate the travel cost. The EV-TOP is decomposed into two subproblems: a constrained optimal path problem in the network (EV1-COP) and a shortest path problem in the meta-network (EV2-SP). To solve the EV1-COP, the Lagrangian relaxation algorithm, the simple efficient approximation (SEA) algorithm, and the Martins (MS) deletion algorithm are used. The EV2-SP is solved using Dijkstra’s algorithm. Thus, a polynomial-time approximation algorithm for the EV-TOP is developed. Finally, two computational studies are presented. The first study assesses the performance of the travel cost method. The second study evaluates the performance of our EV-TOP by comparing it with a well-known method.