We study the problem of computing constrained shortest paths for battery electric vehicles. Since battery capacities are limited, fastest routes are often infeasible. Instead, users are interested in fast routes where the energy consumption does not exceed the battery capacity. For that, drivers can deliberately reduce speed to save energy. Hence, route planning should provide both path and speed recommendations. To tackle the resulting NP-hard optimization problem, previous work trades correctness or accuracy of the underlying model for practical running times. In this work, we present a novel framework to compute optimal constrained shortest paths for electric vehicles that uses more realistic physical models, while taking speed adaptation into account. Careful algorithm engineering makes the approach practical even on large, realistic road networks: We compute optimal solutions in less than a second for typical battery capacities, matching performance of previous inexact methods. For even faster performance, the approach can easily be extended with heuristics that provide high quality solutions within milliseconds.


    Access

    Download


    Export, share and cite



    Title :

    Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles


    Contributors:

    Publication date :

    2017-01-01



    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    004 / 629




    The Variance-Constrained Shortest Path Problem

    Sivakumar, Raj A. | Online Contents | 1994


    Shortest safe path planning for vehicles

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


    The multi-criteria constrained shortest path problem

    Shi, Ning / Zhou, Shaorui / Wang, Fan et al. | Elsevier | 2017


    The Shortest Path Problem Revisited: Optimal Routing for Electric Vehicles

    Andreas Artmeier, Julian Haselmayr, Martin Leucker, Martin Sachenbacher | BASE | 2010

    Free access

    Resource Constrained Shortest Path Problems in Path Planning for Fleet Management

    Avella, P. / Boccia, M. / Sforza, A. | British Library Online Contents | 2004