The problem of minimizing the overall travel time, considering the one spent at charging stations, with the aim to improve the cruising range for Electric Vehicles (EVs) in road networks, is examined in this paper. Since the battery capacity of EVs is limited, it is inevitable for them to stop at charging stations. As they are lacking and the recharging process is time-consuming, an efficient route planning is essential. This paper extends a previously presented approach, i.e., EVRC (Electric Vehicle Route Planning with Recharging). In detail, the solution presented in this work considers a set of factors into account simultaneously and introduces a functional approach that estimates time-optimal routes for road networks with realistic models of charging stops. The key features include the efficient computation of the recharging station’s locations, the battery charging amount under a partial charging scheme, the nonlinear charging functions, and the service time duration at recharging stations. The experimental results highlight that the proposed approach outperforms other similar methods in facing the same problem. The extensive experimental evaluations show that refusing partial charging and neglecting nonlinear charging, as well as servicing time, may generate some infeasible or too costly solutions.