License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2021.11
URN: urn:nbn:de:0030-drops-148807
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14880/
Rajan, Payas ;
Baum, Moritz ;
Wegner, Michael ;
Zündorf, Tobias ;
West, Christian J. ;
Schieferdecker, Dennis ;
Delling, Daniel
Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles
Abstract
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.
BibTeX - Entry
@InProceedings{rajan_et_al:OASIcs.ATMOS.2021.11,
author = {Rajan, Payas and Baum, Moritz and Wegner, Michael and Z\"{u}ndorf, Tobias and West, Christian J. and Schieferdecker, Dennis and Delling, Daniel},
title = {{Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {11:1--11:18},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14880},
URN = {urn:nbn:de:0030-drops-148807},
doi = {10.4230/OASIcs.ATMOS.2021.11},
annote = {Keywords: Electric Vehicles, Route Planning}
}
|
Keywords: |
|
Electric Vehicles, Route Planning |
|
Collection: |
|
21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
27.09.2021 |
