Joint route and charging schedule optimization for electric vehicles considering nonlinear charging process using State-Space-Time networks

Electric Vehicles (EVs) are increasingly integral to modern transportation systems for their environmental advantages. Effective EV route planning, especially for long-distance travel, must consider both charging station availability and vehicle range. However, existing studies are limited in providing exact solutions and real-time optimization, especially when considering nonlinear charging processes. This paper introduces a novel approach that simultaneously optimizes both EV routes and charging schedules, delivering exact solutions within seconds while accounting for the nonlinear charging behavior of EVs. The approach begins by approximating the nonlinear charging process using a piecewise linear function. With this approximation, the charging schedule optimization problem is formulated as a Mixed-Integer Programming (MIP) problem, aiming to maximize charging time efficiency along a fixed route. By analyzing the characteristics of the optimal charging schedule, we establish a mapping between charging station selection and optimal charging amount decisions. The joint optimization model is integrated with the route planning model through a State-Space-Time (SST) network. This allows simultaneous optimization of the time-efficient route and charging schedule by identifying a 3-dimensional route within the SST network. Energy consumption estimates during travel are incorporated to limit the number of charging events, further narrowing the search space. Finally, the real-world highway data are used for line and network simulations. The results of the line simulations demonstrate the model’s effectiveness in enhancing EV charging efficiency. Network simulations confirm that the joint model consistently identifies the optimal routes and charging schedules within seconds, proving its practicality and efficiency.