Document Open Access Logo

Stochastic Route Planning for Electric Vehicles

Authors Payas Rajan , Chinya V. Ravishankar

PDF
Thumbnail PDF

File

LIPIcs.SEA.2022.15.pdf
  • Filesize: 1.1 MB
  • 17 pages

Document Identifiers

Author Details

Payas Rajan
  • Department of Computer Science, University of California, Riverside, CA, USA
Chinya V. Ravishankar
  • Department of Computer Science, University of California, Riverside, CA, USA

Acknowledgements

The authors would like to thank the Mapbox Community team for access to the Mapbox Traffic Data used in our experiments.

Cite As Get BibTex

Payas Rajan and Chinya V. Ravishankar. Stochastic Route Planning for Electric Vehicles. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SEA.2022.15

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Shortest paths
  • Theory of computation → Stochastic control and optimization
Keywords
  • Stochastic Routing
  • Electric Vehicles
  • Route Planning Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Niklas Akerblöm, Yuxin Chen, and Morteza Haghir Chehreghani. An online learning framework for Energy-Efficient navigation of electric vehicles. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20), pages 2051-2057, 2020. Google Scholar
  2. Yazan Al-Wreikat, Clara Serrano, and José Ricardo Sodré. Driving behaviour and trip condition effects on the energy consumption of an electric vehicle under real-world driving. Appl. Energy, 297:117096, September 2021. Google Scholar
  3. Andreas Artmeier, Julian Haselmayr, Martin Leucker, and Martin Sachenbacher. The shortest path problem revisited: Optimal routing for electric vehicles. In KI 2010: Advances in Artificial Intelligence, Lecture Notes in Computer Science, pages 309-316. Springer, Berlin, Heidelberg, September 2010. Google Scholar
  4. Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F Werneck. Route planning in transportation networks. In Algorithm Engineering, Lecture Notes in Computer Science, pages 19-80. Springer, Cham, 2016. Google Scholar
  5. Lucas S Batista, Felipe Campelo, Frederico G Guimarães, and Jaime A Ramírez. A comparison of dominance criteria in many-objective optimization problems. In 2011 IEEE Congress of Evolutionary Computation (CEC), pages 2359-2366, June 2011. Google Scholar
  6. Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner. Search-space size in contraction hierarchies. Theor. Comput. Sci., 645:112-127, September 2016. Google Scholar
  7. Moritz Baum. Engineering Route Planning Algorithms for Battery Electric Vehicles. PhD thesis, Karlsruhe Institute of Technology, 2018. Google Scholar
  8. Moritz Baum, Julian Dibbelt, Andreas Gemsa, Dorothea Wagner, and Tobias Zündorf. Shortest feasible paths with charging stops for battery electric vehicles. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, page 44. ACM, November 2015. Google Scholar
  9. Moritz Baum, Julian Dibbelt, Andreas Gemsa, Dorothea Wagner, and Tobias Zündorf. Shortest feasible paths with charging stops for battery electric vehicles. Transportation Science, 53(6):1627-1655, November 2019. Google Scholar
  10. Roger L Berger. A nonparametric, intersection-union test for stochastic order. Technical report, North Carolina State University. Dept. of Statistics, 1986. Google Scholar
  11. Dimitri P Bertsekas and John N Tsitsiklis. An analysis of stochastic shortest path problems. Math. Oper. Res., 16(3):580-595, August 1991. Google Scholar
  12. Anthony Chen and Zhaowang Ji. Path finding under uncertainty. J. Adv. Transp., 39(1):19-37, September 2005. Google Scholar
  13. Xiao-Wei Chen, Bi Yu Chen, William H K Lam, Mei Lam Tam, and Wei Ma. A bi-objective reliable path-finding algorithm for battery electric vehicle routing. Expert Syst. Appl., 182:115228, November 2021. Google Scholar
  14. Jochen Eisner, Stefan Funke, and Sabine Storandt. Optimal route planning for electric vehicles in large networks. In AAAI, 2011. Google Scholar
  15. Y Y Fan, R E Kalaba, and J E Moore. Arriving on time. J. Optim. Theory Appl., 127(3):497-513, December 2005. Google Scholar
  16. Chiara Fiori, Kyoungho Ahn, and Hesham A Rakha. Power-based electric vehicle energy consumption model: Model development and validation. Appl. Energy, 168:257-268, April 2016. Google Scholar
  17. Chiara Fiori, Vittorio Marzano, Vincenzo Punzo, and Marcello Montanino. Energy consumption modeling in presence of uncertainty. IEEE Trans. Intell. Transp. Syst., pages 1-12, 2020. Google Scholar
  18. Matthew William Fontana. Optimal routes for electric vehicles facing uncertainty, congestion, and energy constraints. PhD thesis, Massachusetts Institute of Technology, 2013. Google Scholar
  19. Mogens Fosgerau. The valuation of travel time variability. Technical report, International Transport Forum, 2016. Google Scholar
  20. H Frank. Shortest paths in probabilistic graphs. Oper. Res., 17(4):583-599, 1969. Google Scholar
  21. Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Experimental Algorithms, pages 319-333. Springer, Berlin, Heidelberg, May 2008. Google Scholar
  22. Michael T Goodrich and Paweł Pszona. Two-phase bicriterion search for finding fast and efficient electric vehicle routes. In Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 193-202. ACM, November 2014. Google Scholar
  23. Ming Hua and Jian Pei. Probabilistic path queries in road networks: traffic uncertainty aware path selection. In Proceedings of the 13th International Conference on Extending Database Technology, EDBT '10, pages 347-358, New York, NY, USA, March 2010. Association for Computing Machinery. Google Scholar
  24. Gerhard Huber, Klaus Bogenberger, and Hans van Lint. Optimization of charging strategies for battery electric vehicles under uncertainty. IEEE Trans. Intell. Transp. Syst., pages 1-17, 2020. Google Scholar
  25. Ehsan Jafari and Stephen D Boyles. Multicriteria stochastic shortest path problem for electric vehicles. Networks Spat. Econ., 17(3):1043-1070, September 2017. Google Scholar
  26. H C Joksch. The shortest route problem with constraints. J. Math. Anal. Appl., 14(2):191-197, May 1966. Google Scholar
  27. Moritz Kobitzsch, Samitha Samaranayake, and Dennis Schieferdecker. Pruning techniques for the stochastic on-time arrival problem- an experimental study. arXiv, July 2014. URL: http://arxiv.org/abs/1407.8295.
  28. Sejoon Lim, Christian Sommer, Evdokia Nikolova, and Daniela Rus. Practical route planning under delay uncertainty: Stochastic shortest path queries. In Robotics: Science and Systems, volume 8, pages 249-256. books.google.com, 2013. Google Scholar
  29. Antonio Lima, Rade Stanojevic, Dina Papagiannaki, Pablo Rodriguez, and Marta C González. Understanding individual routing behaviour. J. R. Soc. Interface, 13(116), March 2016. Google Scholar
  30. Sören Merting, Christian Schwan, and Martin Strehler. Routing of electric vehicles: Constrained shortest path problems with resource recovering nodes. In OASIcs-OpenAccess Series in Informatics, volume 48. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany, 2015. Google Scholar
  31. Sebastiano Milardo, Punit Rathore, Marco Amorim, Umberto Fugiglando, Paolo Santi, and Carlo Ratti. Understanding drivers' stress and interactions with vehicle systems through naturalistic data analysis. IEEE Trans. Intell. Transp. Syst., pages 1-12, 2021. Google Scholar
  32. Elise D Miller-Hooks and Hani S Mahmassani. Least expected time paths in stochastic, Time-Varying transportation networks. Transportation Science, 34(2):198-215, May 2000. Google Scholar
  33. Elise Deborah Miller-Hooks. Optimal routing in time-varying, stochastic networks: Algorithms and implementations. PhD thesis, The University of Texas at Austin, 1997. Google Scholar
  34. J P L Nasa. NASADEM merged DEM global 1 arc second V001 [dataset], 2020. Accessed: 2021-6-9. URL: https://doi.org/10.5067/MEaSUREs/NASADEM/NASADEM_HGT.001.
  35. Yu (marco) Nie and Xing Wu. Shortest path problem considering on-time arrival probability. Trans. Res. Part B: Methodol., 43(6):597-613, July 2009. Google Scholar
  36. Patrick Niklaus. A unified framework for electric vehicle routing. Master’s thesis, Karlsruhe Institute of Technology, 2017. Google Scholar
  37. Mehrdad Niknami and Samitha Samaranayake. Tractable pathfinding for the stochastic On-Time arrival problem. In Experimental Algorithms, pages 231-245. Springer International Publishing, 2016. Google Scholar
  38. Evdokia Nikolova. Approximation algorithms for reliable stochastic combinatorial optimization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 338-351. Springer Berlin Heidelberg, 2010. Google Scholar
  39. Evdokia Nikolova, Matthew Brand, and David R Karger. Optimal route planning under uncertainty. ICAPS, 2006. Google Scholar
  40. Evdokia Nikolova, Jonathan A Kelner, Matthew Brand, and Michael Mitzenmacher. Stochastic shortest paths via quasi-convex maximization. In Algorithms - ESA 2006, pages 552-563. Springer Berlin Heidelberg, 2006. Google Scholar
  41. Axel Parmentier and Frédéric Meunier. Stochastic shortest paths and risk measures. arXiv, August 2014. URL: http://arxiv.org/abs/1408.0272.
  42. Simon Aagaard Pedersen, Bin Yang, and Christian S Jensen. Fast stochastic routing under time-varying uncertainty. VLDB J., October 2019. Google Scholar
  43. Simon Aagaard Pedersen, Bin Yang, and Christian S Jensen. Anytime stochastic routing with hybrid learning. Proceedings VLDB Endowment, 13(9):1555-1567, May 2020. Google Scholar
  44. Simon Aagaard Pedersen, Bin Yang, and Christian S Jensen. A hybrid learning approach to stochastic routing. In 2020 IEEE 36th International Conference on Data Engineering (ICDE), pages 1910-1913, April 2020. Google Scholar
  45. Payas Rajan, Moritz Baum, Michael Wegner, Tobias Zündorf, Christian J West, Dennis Schieferdecker, and Daniel Delling. Robustness generalizations of the shortest feasible path problem for electric vehicles. In Matthias And Federico, Müller-Hannemann, editor, Proceedings of 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021), Open Access Series in Informatics (OASIcs), pages 11:1-11:18, Dagstuhl, Germany, September 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Google Scholar
  46. Payas Rajan and Chinya V Ravishankar. The phase abstraction for estimating energy consumption and travel times for electric vehicle route planning. In Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL '19, pages 556-559, New York, NY, USA, 2019. ACM. Google Scholar
  47. Payas Rajan and Chinya V Ravishankar. Tiering in contraction and edge hierarchies for stochastic route planning. In Proceedings of the 29th International Conference on Advances in Geographic Information Systems, SIGSPATIAL '21, pages 616-625, New York, NY, USA, November 2021. Association for Computing Machinery. Google Scholar
  48. Guillaume Sabran, Samitha Samaranayake, and Alexandre Bayen. Precomputation techniques for the stochastic on-time arrival problem. In 2014 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), Proceedings, pages 138-146. Society for Industrial and Applied Mathematics, December 2013. Google Scholar
  49. M Sachenbacher, M Leucker, A Artmeier, and J Haselmayr. Efficient Energy-Optimal routing for electric vehicles. AAAI, 2011. Google Scholar
  50. Moshe Shaked and J George Shanthikumar. Stochastic Orders. Springer New York, October 2006. Google Scholar
  51. Liang Shen, Hu Shao, Ting Wu, William H K Lam, and Emily C Zhu. An energy-efficient reliable path finding algorithm for stochastic road networks with electric vehicles. Transp. Res. Part C: Emerg. Technol., 102:450-473, May 2019. Google Scholar
  52. Kenneth A Small, Clifford Winston, and Jia Yan. Uncovering the distribution of motorists' preferences for travel time and reliability. Econometrica, 73(4):1367-1382, July 2005. Google Scholar
  53. Christian Sommer. Shortest-path queries in static networks. ACM Computing Surveys (CSUR), 46(4):45, April 2014. Google Scholar
  54. Sabine Storandt. Quick and energy-efficient routes: Computing constrained shortest paths for electric vehicles. In Proceedings of the 5th ACM SIGSPATIAL International Workshop on Computational Transportation Science, IWCTS '12, pages 20-25, New York, NY, USA, 2012. ACM. Google Scholar
  55. Sabine Storandt. Route planning for bicycles - exact constrained shortest paths made practical via contraction hierarchy. In Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling, 2012. Google Scholar
  56. Sabine Storandt and Stefan Funke. Cruising with a Battery-Powered vehicle and not getting stranded. In AAAI, volume 3, page 46, 2012. Google Scholar
  57. Martin Strehler, Sören Merting, and Christian Schwan. Energy-efficient shortest routes for electric and hybrid vehicles. Trans. Res. Part B: Methodol., 103(Supplement C):111-135, September 2017. Google Scholar
  58. Christoph Witzgall and Alan J Goldman. Most profitable routing before maintenance. In OPERATIONS RESEARCH, page B82. INST OPERATIONS RESEARCH MANAGEMENT SCIENCES 901 ELKRIDGE LANDING RD, STE 400, LINTHICUM HTS, MD, USA, 1965. Google Scholar
  59. Bin Yang, Chenjuan Guo, Christian S Jensen, Manohar Kaul, and Shuo Shang. Stochastic skyline route planning under time-varying uncertainty. In 2014 IEEE 30th International Conference on Data Engineering, pages 136-147, March 2014. Google Scholar
  60. Shanjiang Zhu and David Levinson. Do people use the shortest path? an empirical test of wardrop’s first principle. PLoS One, 10(8):e0134322, August 2015. Google Scholar
  61. Weiwei Zhuang, Yadong Li, and Guoxin Qiu. Statistical inference for a relaxation index of stochastic dominance under density ratio model. J. Appl. Stat., pages 1-19, August 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact