Cluster-based route planning for electric vehicles travel time optimization

Private mobility electrification is slowed down by technical limitations, such as the low autonomy of electric vehicles (EVs) compared to internal combustion engine vehicles (ICEVs). As a consequence, accurate planning of the route is needed before a travel with an EV begins. Routing algorithms are of crucial importance to identify the route which allows to minimize total travel time, reducing the drawbacks of battery’s limited energy density. The complexity of the problem and the size of road networks considered for this task imply computational times which are not in line with users’ needs. The method proposed in this article employs clustering and pruning techniques to speed up planning by downsizing the network analyzed during route planning. By reducing the computational cost, it is possible to apply Dijkstra algorithm, which provides an exact minimization of total travel time.