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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles


    Beteiligte:
    Baum, Moritz (Autor:in) / Dibbelt, Julian (Autor:in) / Wagner, Dorothea (Autor:in)

    Erscheinungsdatum :

    2017-01-01



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    004 / 629




    The Variance-Constrained Shortest Path Problem

    Sivakumar, Raj A. | Online Contents | 1994


    The multi-criteria constrained shortest path problem

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


    Shortest safe path planning for vehicles

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


    The Shortest Path Problem Revisited: Optimal Routing for Electric Vehicles

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

    Freier Zugriff

    Resource Constrained Shortest Path Problems in Path Planning for Fleet Management

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