2026-07-20T14:51:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14880 2024-03-06T10:31:35Z ddc:004 open_access

Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles Rajan, Payas Baum, Moritz Wegner, Michael Zündorf, Tobias West, Christian J. Schieferdecker, Dennis Delling, Daniel Electric Vehicles Route Planning Electric Vehicle routing is often modeled as a Shortest Feasible Path Problem (SFPP), which minimizes total travel time while maintaining a non-zero State of Charge (SoC) along the route. However, the problem assumes perfect information about energy consumption and charging stations, which are difficult to even estimate in practice. Further, drivers might have varying risk tolerances for different trips. To overcome these limitations, we propose two generalizations to the SFPP; they compute the shortest feasible path for any initial SoC and, respectively, for every possible minimum SoC threshold. We present algorithmic solutions for each problem, and provide two constructs: Starting Charge Maps and Buffer Maps, which represent the tradeoffs between robustness of feasible routes and their travel times. The two constructs are useful in many ways, including presenting alternate routes or providing charging prompts to users. We evaluate the performance of our algorithms on realistic input instances. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Payas Rajan and Moritz Baum and Michael Wegner and Tobias Zündorf and Christian J. West and Dennis Schieferdecker and Daniel Delling 2021 Is Part Of OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2021.11 urn:nbn:de:0030-drops-148807 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.11 eng https://creativecommons.org/licenses/by/4.0/legalcode