License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2022.15
URN: urn:nbn:de:0030-drops-165497
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16549/
Go to the corresponding LIPIcs Volume Portal

Rajan, Payas ; Ravishankar, Chinya V.

Stochastic Route Planning for Electric Vehicles

pdf-format:
LIPIcs-SEA-2022-15.pdf (1 MB)

Abstract

Electric Vehicle routing is often modeled as a generalization of the energy-constrained shortest path problem, taking travel times and energy consumptions on road network edges to be deterministic. In practice, however, energy consumption and travel times are stochastic distributions, typically estimated from real-world data. Consequently, real-world routing algorithms can make only probabilistic feasibility guarantees. Current stochastic route planning methods either fail to ensure that routes are energy-feasible, or if they do, have not been shown to scale well to large graphs. Our work bridges this gap by finding routes to maximize on-time arrival probability and the set of non-dominated routes under two criteria for stochastic route feasibility: ?-feasibility and p-feasibility. Our ?-feasibility criterion ensures energy-feasibility in expectation, using expected energy values along network edges. Our p-feasibility criterion accounts for the actual distribution along edges, and keeps the stranding probability along the route below a user-specified threshold p. We generalize the charging function propagation algorithm to accept stochastic edge weights to find routes that maximize the probability of on-time arrival, while maintaining ?- or p-feasibility. We also extend multi-criteria Contraction Hierarchies to accept stochastic edge weights and offer heuristics to speed up queries. Our experiments on a real-world road network instance of the Los Angeles area show that our methods answer stochastic queries in reasonable time, that the two criteria produce similar routes for longer deadlines, but that ?-feasibility queries can be much faster than p-feasibility queries.

BibTeX - Entry

@InProceedings{rajan_et_al:LIPIcs.SEA.2022.15,
  author =	{Rajan, Payas and Ravishankar, Chinya V.},
  title =	{{Stochastic Route Planning for Electric Vehicles}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16549},
  URN =		{urn:nbn:de:0030-drops-165497},
  doi =		{10.4230/LIPIcs.SEA.2022.15},
  annote =	{Keywords: Stochastic Routing, Electric Vehicles, Route Planning Algorithms}
}

Keywords: Stochastic Routing, Electric Vehicles, Route Planning Algorithms
Collection: 20th International Symposium on Experimental Algorithms (SEA 2022)
Issue Date: 2022
Date of publication: 11.07.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI