Document Open Access Logo

Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles

Authors Payas Rajan , Moritz Baum, Michael Wegner, Tobias Zündorf, Christian J. West, Dennis Schieferdecker, Daniel Delling

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2021.11.pdf
  • Filesize: 0.77 MB
  • 18 pages

Document Identifiers

Author Details

Payas Rajan
  • Department of Computer Science & Engineering, University of California, Riverside, CA, USA
Moritz Baum
  • Apple, Cupertino, CA, USA
Michael Wegner
  • Apple, Cupertino, CA, USA
Tobias Zündorf
  • Apple, Cupertino, CA, USA
Christian J. West
  • Apple, Cupertino, CA, USA
Dennis Schieferdecker
  • Apple, Cupertino, CA, USA
Daniel Delling
  • Apple, Cupertino, CA, USA

Funding

  • Rajan, Payas: This work was done while the author was an intern at Apple Inc.

Cite As Get BibTex

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 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/OASIcs.ATMOS.2021.11

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Paths and connectivity problems
Keywords
  • Electric Vehicles
  • Route Planning

Metrics

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

References

  1. 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
  2. Alternative Fuels Data Center. Electric vehicle charging station locations. https://afdc.energy.gov/fuels/electricity_locations.html, 2021. Accessed: 2021-6-9.
  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, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, , and Dorothea Wagner. Combining hierarchical and goal-directed speed-up techniques for dijkstra’s algorithm. Algorithms, 2008. Google Scholar
  7. 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
  8. 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
  9. Moritz Baum, Julian Dibbelt, Lorenz Hübschle-Schneider, Thomas Pajor, and Dorothea Wagner. Speed-Consumption tradeoff for electric vehicle route planning. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, OpenAccess Series in Informatics (OASIcs), pages 138-151. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014. Google Scholar
  10. Moritz Baum, Julian Dibbelt, Thomas Pajor, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Energy-Optimal routes for battery electric vehicles. Algorithmica, December 2019. Google Scholar
  11. Moritz Baum, Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. Dynamic Time-Dependent route planning in road networks with user preferences. In Experimental Algorithms, volume 9685 of Lecture Notes in Computer Science, pages 33-49, Cham, 2016. Springer International Publishing. Google Scholar
  12. Moritz Baum, Julian Dibbelt, Dorothea Wagner, and Tobias Zündorf. Modeling and engineering constrained shortest path algorithms for battery electric vehicles. In LIPIcs-Leibniz International Proceedings in Informatics, volume 87, 2017. Google Scholar
  13. Moritz Baum, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Consumption profiles in route planning for electric vehicles: Theory and applications. In 16th International Symposium on Experimental Algorithms (SEA 2017). drops.dagstuhl.de, 2017. Google Scholar
  14. Cedric De Cauwer, Wouter Verbeke, Thierry Coosemans, Saphir Faid, and Joeri Van Mierlo. A Data-Driven method for energy consumption prediction and Energy-Efficient routing of electric vehicles in Real-World conditions. Energies, 10(5):608, May 2017. Google Scholar
  15. Daniel Delling, Andrew V Goldberg, Thomas Pajor, and Renato F Werneck. Customizable route planning. In Experimental Algorithms, pages 376-387. Springer, Berlin, Heidelberg, May 2011. Google Scholar
  16. Daniel Delling, Andrew V Goldberg, Thomas Pajor, and Renato F Werneck. Customizable route planning in road networks. Transportation Science, 51(2):566-591, May 2015. Google Scholar
  17. Daniel Delling and Dorothea Wagner. Time-Dependent route planning. In Robust and Online Large-Scale Optimization, Lecture Notes in Computer Science, pages 207-230. Springer, Berlin, Heidelberg, 2009. Google Scholar
  18. Matthias Eisel, Ilja Nastjuk, and Lutz M Kolbe. Understanding the influence of in-vehicle information systems on range stress - insights from an electric vehicle field experiment. Transp. Res. Part F Traffic Psychol. Behav., 43:199-211, November 2016. Google Scholar
  19. Jochen Eisner, Stefan Funke, and Sabine Storandt. Optimal route planning for electric vehicles in large networks. AAAI, 25(1), August 2011. Google Scholar
  20. 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
  21. 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
  22. Matthew William Fontana. Optimal routes for electric vehicles facing uncertainty, congestion, and energy constraints. PhD thesis, Massachusetts Institute of Technology, 2013. Google Scholar
  23. Luca Foschini, John Hershberger, and Subhash Suri. On the complexity of Time-Dependent shortest paths. Algorithmica, 68(4):1075-1097, April 2014. Google Scholar
  24. Thomas Franke and Josef F Krems. Interacting with limited mobility resources: Psychological range levels in electric vehicle use. Transp. Res. Part A: Policy Pract., 48:109-122, February 2013. Google Scholar
  25. Thomas Franke, Isabel Neumann, Franziska Bühler, Peter Cocron, and Josef F Krems. Experiencing range in an electric vehicle: Understanding psychological barriers: Experiencing range. Appl. Psychol., 61(3):368-391, July 2012. Google Scholar
  26. Thomas Franke, Nadine Rauh, Madlen Günther, Maria Trantow, and Josef F Krems. Which factors can protect against range stress in everyday usage of battery electric vehicles? toward enhancing sustainability of electric mobility systems. Hum. Factors, 58(1):13-26, February 2016. Google Scholar
  27. Stefan Funke and Sabine Storandt. Polynomial-time construction of contraction hierarchies for multi-criteria objectives. In Proceedings of the Meeting on Algorithm Engineering & Expermiments, pages 41-54, Philadelphia, PA, USA, 2013. Society for Industrial and Applied Mathematics. Google Scholar
  28. Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. Exact routing in large road networks using contraction hierarchies. Transportation Science, 46(3):388-404, August 2012. Google Scholar
  29. 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
  30. 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
  31. Malte F Jung, David Sirkin, Turgut M Gür, and Martin Steinert. Displayed uncertainty improves driving experience and behavior: The case of range anxiety in an electric car. In Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems, pages 2201-2210. ACM, April 2015. Google Scholar
  32. Johannes Kester. Security in transition(s): The low-level security politics of electric vehicle range anxiety. Security Dialogue, 50(6):547-563, December 2019. Google Scholar
  33. Yan Li, Pratik Kotwal, Pengyue Wang, Yiqun Xie, Shashi Shekhar, and William Northrop. Physics-guided energy-efficient path selection using on-board diagnostics data. ACM/IMS Trans. Data Sci., 1(3):1-28, September 2020. Google Scholar
  34. Yan Li, Shashi Shekhar, Pengyue Wang, and William Northrop. Physics-guided energy-efficient path selection: a summary of results. In Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 99-108. ACM, November 2018. Google Scholar
  35. Ernesto Queirós Vieira Martins. On a multicriteria shortest path problem. Eur. J. Oper. Res., 16(2):236-245, May 1984. Google Scholar
  36. Michail Masikos, Konstantinos Demestichas, Evgenia Adamopoulou, and Michael Theologou. Energy-efficient routing based on vehicular consumption predictions of a mesoscopic learning model. Appl. Soft Comput., 28:114-124, March 2015. Google Scholar
  37. 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
  38. J P L Nasa. NASADEM merged DEM global 1 arc second V001 [dataset]. http://dx.doi.org/10.5067/MEaSUREs/NASADEM/NASADEM_HGT.001, 2020. Accessed: 2021-6-9.
  39. Zachary A Needell, James McNerney, Michael T Chang, and Jessika E Trancik. Potential for widespread electrification of personal vehicle travel in the united states. Nature Energy, 1:16112, August 2016. Google Scholar
  40. Dario Pevec, Jurica Babic, Arthur Carvalho, Yashar Ghiassi-Farrokhfal, Wolfgang Ketter, and Vedran Podobnik. Electric vehicle range anxiety: An obstacle for the personal transportation (r)evolution? In 2019 4th International Conference on Smart and Sustainable Technologies (SpliTech), pages 1-8, June 2019. Google Scholar
  41. Dario Pevec, Jurica Babic, Arthur Carvalho, Yashar Ghiassi-Farrokhfal, Wolfgang Ketter, and Vedran Podobnik. A survey-based assessment of how existing and potential electric vehicle owners perceive range anxiety. J. Clean. Prod., 276:122779, December 2020. Google Scholar
  42. Xuewei Qi, Guoyuan Wu, Kanok Boriboonsomsin, and Matthew J Barth. Data-driven decomposition analysis and estimation of link-level electric vehicle energy consumption under real-world traffic conditions. Transp. Res. Part D: Trans. Environ., 64:36-52, October 2018. Google Scholar
  43. 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
  44. Nadine Rauh, Thomas Franke, and Josef F Krems. User experience with electric vehicles while driving in a critical range situation - a qualitative approach. IET Intel. Transport Syst., 9(7):734-739, July 2015. Google Scholar
  45. Martin Sachenbacher, Martin Leucker, Andreas Artmeier, and Julian Haselmayr. Efficient energy-optimal routing for electric vehicles. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI'11, pages 1402-1407. AAAI Press, August 2011. Google Scholar
  46. Stefan Sautermeister, Max Falk, Bernard Bäker, Frank Gauterin, and Moritz Vaillant. Influence of measurement and prediction uncertainties on range estimation for electric vehicles. IEEE Trans. Intell. Transp. Syst., 19(8):2615-2626, August 2018. Google Scholar
  47. René Schönfelder and Martin Leucker. Abstract routing models and abstractions in the context of vehicle routing. In Twenty-Fourth International Joint Conference on Artificial Intelligence, June 2015. Google Scholar
  48. 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
  49. Sabine Storandt and Stefan Funke. Cruising with a Battery-Powered vehicle and not getting stranded. In AAAI, volume 3, page 46, 2012. Google Scholar
  50. 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
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