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.


    Access

    Download


    Export, share and cite



    Title :

    The Shortest Path Problem Revisited: Optimal Routing for Electric Vehicles



    Publication date :

    2010-08-19


    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English


    Keywords :

    Classification :

    DDC:    000 / 629



    Dynamic routing for the Electric Vehicle Shortest Path Problem with charging station occupancy information

    Dastpak, Mohsen / Errico, Fausto / Jabali, Ola et al. | Elsevier | 2023


    Shortest safe path planning for vehicles

    Lambert, A. / Bouaziz, S. / Reynaud, R. | IEEE | 2003


    Electric vehicle shortest path problem with replenishment constraint

    Baouche, Fouad / Trigui, Rochdi / Billot, Romain et al. | IEEE | 2014



    Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles

    Baum, Moritz / Dibbelt, Julian / Wagner, Dorothea | BASE | 2017

    Free access