Abstract We study the problem of an Electric Vehicle (EV) having to travel from an origin to a destination in the shortest amount of time. We focus on long-distance settings, where the shortest path between the origin and the destination has energy requirements exceeding the EV autonomy. The EV may charge its battery at public Charging Stations (CSs), which are subject to unknown arrivals of exogenous vehicles requiring uncertain charging times. Thus, the waiting times at CSs are uncertain. Similar to other contributions in the literature, we model CSs using appropriately defined queues, whose status is revealed upon the EV arrival. However, following recent technological advances, we also consider that the status of each CS is updated in real-time via binary Occupancy Indicator (OI) information signaling if a CS is busy or not. Therefore, we assume that the EV continuously receives OI updates on all CSs. At each update, we determine the sequence of CSs to visit along with associated charging quantities. We name the resulting problem as the Electric Vehicle Shortest Path Problem with charging station Occupancy Indicator information (EVSPP-OI). In this problem, we consider that the EV is allowed to partially charge its battery, and we model charging times via piecewise linear charging functions that depend on the CS technology. We propose a Markov Decision Process formulation for the EVSPP-OI, which aims at optimizing the EV routing and charging policy. To solve the problem, we develop a reoptimization algorithm that establishes the sequence of CS visits and charging amounts based on system updates. Specifically, we propose a simulation-based approach to estimate the waiting time of the EV at a CS as a function of its arrival time. As the path to a CS may consist of multiple intermediate CS stops, estimating the arrival times at each CS is fairly intricate. To this end, we propose an efficient heuristic that yields approximate lower bounds on the arrival time of the EV at each CS, which are used to derive an estimation of the waiting time at each CS. We use these estimations to define a compatible deterministic version of the EVSPP, which we solve with an existing algorithm. We conduct a comprehensive computational study and compare the performance of our methodology with a benchmark that observes the status of CSs only upon arrival (i.e., with no OI information). Results show that our method reduces waiting times and total trip duration by an average of 23.7%–95.4% and 1.4%–18.5%, respectively.

    Highlights We present the EVSPP-OI, an EVSPP variant factoring charging stations’ online status. We suggest an MDP model for EVSPP-OI to develop an optimal route policy for the EV. We develop a method to reoptimize the EV route and charging amount with system updates. Our method surpasses a benchmark that does not use real-time charging station status.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

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


    Beteiligte:
    Dastpak, Mohsen (Autor:in) / Errico, Fausto (Autor:in) / Jabali, Ola (Autor:in) / Malucelli, Federico (Autor:in)


    Erscheinungsdatum :

    2023-11-06




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Electric vehicle charging station occupancy prediction system

    HYEON SU YEONG | Europäisches Patentamt | 2024

    Freier Zugriff



    Deep Information Fusion for Electric Vehicle Charging Station Occupancy Forecasting

    Sao, Ashutosh / Tempelmeier, Nicolas / Demidova, Elena | IEEE | 2021


    The Shortest Path Problem Revisited: Optimal Routing for Electric Vehicles

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

    Freier Zugriff