Optimal Route And Charging Planning For Electric Vehicles

The importance of electric vehicles has increased steadily in recent years.Different from route planning for conventional combustion-engine cars,routing for EVs has to consider distinctive features of the car.Such as battery capacity,say it the distance the vehicle may travel on a full battery of energy,also charging time and the location of charging stations.In this thesis we study the problem of electric vehicle routing.The objective is to find time-optimal route to go from source to target via charging stations.At each charging station we may recharge some amount of energy to "extend" the range of the vehicle by a certain amount.Moreover,recharging time vary depending on the available SoC and further demand energy.Optimization problem related to computing the shortest tour visiting a set of charging stations is NP-hard.We propose an algorithm to compute time-optimal solutions and augment it with a CH speedup technique to enable computing solutions on large-sized graphs in a sensible time.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 stations.The key features include the efficient computation of the recharging station’s location,the battery charging amount under a partial charging strategy,the nonlinear charging functions,and the service time duration at recharging stations.Our experimental evaluations show that regarding query time our optimized approach outperform the base algorithm.