Efficient Routing Decisions for Electric Vehicles in a Congested Network

Abstract

The Electric Vehicle Routing Problem (E-VRP) is an extension of the infamous Vehicle Routing Problem which asks which routing decisions an electric vehicle needs to take in order to traverse the network efficiently. Many extensions of this problem have been subject to research in the last decade and now that electric vehicles are starting to pop up in more and more cities, questions are asked about how an electric vehicle should decide which charging station to charge at to minimize their lateness. This problem is of growing significance due to the growth of the amount of electric vehicles and the disruptions which are caused by the longer recharging times of an electrical vehicle when compared to fossil fuel-based vehicles. Since there are countless possibilities and variables to consider in this problem (e.g. the price of electricity or the distance to a charging station), research should be conducted to see which kind of algorithm most satisfies the need of the end-user. To address this problem, this paper proposes several algorithms and compares them to each other based on algorithmic efficiency, average travel time of the vehicles and possible disadvantages when using the algorithms. Through simulations we show that the IARS algorithm as proposed in an earlier paper leads to the overall best performance, but that it lacks efficiency in terms of algorithmical complexity. We also show that when using a shortest path algorithm, the addition of a greedy geometric spanner significantly decreases the time complexity of the algorithm, in some cases reducing the average timespan of the simulation of 1 day by as much as 34%.