The Shortest Path Problem Revisited: Optimal Routing for Electric Vehicles

Electric vehicles (EV) powered by batteries will play a sig- nificant role in the road traffic of the future. The unique characteristics of such EVs – limited cruising range, long recharge times, and the ability to regain energy during deceleration – require novel routing algorithms, since the task is now to determine the most economical route rather than just the shortest one. This paper proposes extensions to general shortest- path algorithms that address the problem of energy-optimal routing. Specifically, we (i) formalize energy-efficient routing in the presence of rechargeable batteries as a special case of the constrained shortest path problem (CSPP) with hard and soft constraints, and (ii) present an adap- tion of a general shortest path algorithm (using an energy graph, i.e., a graph with a weight function representing the energy consumption) that respects the given constraints and has a worst case complexity of O(n3). The presented algorithms have been implemented and evaluated within a prototypic navigation system for energy-efficient routing.     «

Electric vehicles (EV) powered by batteries will play a sig- nificant role in the road traffic of the future. The unique characteristics of such EVs – limited cruising range, long recharge times, and the ability to regain energy during deceleration – require novel routing algorithms, since the task is now to determine the most economical route rather than just the shortest one. This paper proposes extensions to general shortest- path algorithms that address the problem of energy-optimal routing....     »