OCP: Proactive Optimal Charging Planning for Electric Vehicles

Due to the limited driving range, insufficient charging facilities, and time-consuming recharging, optimizing charging routes for electric vehicles (EVs) presents unique challenges compared to conventional vehicles. The time and location of EV charging during a trip not only affect an individual EV’s travel time but also influence others, as queues may form at charging station(s). This issue is at large seen as a significant constraint for uplifting EV sales in many countries. In this study, we introduce a novel EV Route Planning problem, which involves two parts: (i) finding the fastest route with recharging for an EV routing request. We model the problem as a new graph problem and prove its NP-hardness. We propose an innovative two-phase algorithm that efficiently traverses the graph to identify the optimal charging route for each EV. (ii) We find routes with minimized travel time for an EV while strategically avoid charging stations and time to recharge at those stations which can lead to minimized travel time for upcoming EVs. For this purpose, we introduce the concept of an “influence factor” to guide heuristic decisions. Our results demonstrate that this method reduces total travel time by 50% compared to the state-of-the-art on real-world datasets, with benefits becoming more significant as the number of EVs on the road increases.