Document Open Access Logo

Consumption Profiles in Route Planning for Electric Vehicles: Theory and Applications

Authors Moritz Baum, Jonas Sauer, Dorothea Wagner, Tobias Zündorf

PDF
Thumbnail PDF

File

LIPIcs.SEA.2017.19.pdf
  • Filesize: 0.49 MB
  • 18 pages

Document Identifiers

Author Details

Moritz Baum
Jonas Sauer
Dorothea Wagner
Tobias Zündorf

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SEA.2017.19

Abstract

In route planning for electric vehicles (EVs), consumption profiles are a functional representation of optimal energy consumption between two locations, subject to initial state of charge. Efficient computation of profiles is a relevant problem on its own, but also a fundamental ingredient to many route planning approaches for EVs. In this work, we show that the complexity of a profile is at most linear in the graph size. Based on this insight, we derive a polynomial-time algorithm for the problem of finding an energy-optimal path between two locations that allows stops at charging stations. Exploiting efficient profile search, our approach also allows partial recharging at charging stations to save energy. In a sense, our results close the gap between efficient techniques for energy-optimal routes (based on simpler models) and NP-hard time-constrained problems involving charging stops for EVs. We propose a practical implementation, which we carefully integrate with Contraction Hierarchies and A* search. Even though the practical variant formally drops correctness, a comprehensive experimental study on a realistic, large-scale road network reveals that it always finds the optimal solution in our tests and computes even long-distance routes with charging stops in less than 300 ms.
Keywords
  • electric vehicles
  • charging station
  • shortest paths
  • route planning
  • profile search
  • algorithm engineering

Metrics

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

References

  1. Andreas Artmeier, Julian Haselmayr, Martin Leucker, and Martin Sachenbacher. The Optimal Routing Problem in the Context of Battery-Powered Electric Vehicles. In Proceedings of the 2nd CPAIOR Workshop on Constraint Reasoning and Optimization for Computational Sustainability (CROCS'10), 2010. Google Scholar
  2. Andreas Artmeier, Julian Haselmayr, Martin Leucker, and Martin Sachenbacher. The Shortest Path Problem Revisited: Optimal Routing for Electric Vehicles. In Proceedings of the 33rd Annual German Conference on Advances in Artificial Intelligence (KI'10), volume 6359 of Lecture Notes in Computer Science, pages 309-316. Springer, 2010. Google Scholar
  3. Mikhail J. Atallah. Some Dynamic Computational Geometry Problems. Computers &Mathematics with Applications, 11(12):1171-1181, 1985. Google Scholar
  4. Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route Planning in Transportation Networks, volume 9220 of Lecture Notes in Computer Science, pages 19-80. Springer, 2016. Google Scholar
  5. Gernot V. Batz and Peter Sanders. Time-Dependent Route Planning with Generalized Objective Functions. In Proc. of the 20th Annual European Symp. on Algorithms (ESA'12), volume 7501 of Lecture Notes in Computer Science, pages 169-180. Springer, 2012. 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. ACM Journal of Experimental Algorithmics, 15:2.3:1-2.3:31, 2010. 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 ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS'15), pages 44:1-44:10. ACM, 2015. Google Scholar
  8. Moritz Baum, Julian Dibbelt, Lorenz Hübschle-Schneider, Thomas Pajor, and Dorothea Wagner. Speed-Consumption Tradeoff for Electric Vehicle Route Planning. In Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'14), volume 42 of OpenAccess Series in Informatics (OASIcs), pages 138-151. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. Google Scholar
  9. Moritz Baum, Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. Energy-Optimal Routes for Electric Vehicles. In Proc. of the 21st ACM SIGSPATIAL Int'l Conference on Advances in Geographic Information Systems (GIS'13), pages 54-63. ACM, 2013. Google Scholar
  10. Moritz Baum, Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. Dynamic Time-Dependent Route Planning in Road Networks with User Preferences. In Proceedings of the 15th International Symposium on Experimental Algorithms (SEA'16), volume 9685 of Lecture Notes in Computer Science, pages 33-49. Springer, 2016. Google Scholar
  11. Brian C. Dean. Shortest Paths in FIFO Time-Dependent Networks: Theory and Algorithms. Technical report, Massachusetts Institute of Technology, 2004. Google Scholar
  12. Daniel Delling. Time-Dependent SHARC-Routing. Algorithmica, 60(1):60-94, 2011. Google Scholar
  13. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Customizable Route Planning in Road Networks. Transportation Science, 2015. Google Scholar
  14. Daniel Delling and Dorothea Wagner. Landmark-Based Routing in Dynamic Graphs. In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07), volume 4525 of Lecture Notes in Computer Science, pages 52-65. Springer, 2007. Google Scholar
  15. Daniel Delling and Dorothea Wagner. Time-Dependent Route Planning, volume 5868 of Lecture Notes in Computer Science, pages 207-230. Springer, 2009. Google Scholar
  16. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Customizable Contraction Hierarchies. ACM Journal of Experimental Algorithmics, 21:1.5:1-1.5:49, 2016. Google Scholar
  17. Edsger W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1(1):269-271, 1959. Google Scholar
  18. Jochen Eisner, Stefan Funke, and Sabine Storandt. Optimal Route Planning for Electric Vehicles in Large Networks. In Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI'11), pages 1108-1113. AAAI Press, 2011. Google Scholar
  19. Luca Foschini, John Hershberger, and Subhash Suri. On the Complexity of Time-Dependent Shortest Paths. Algorithmica, 68(4):1075-1097, 2014. Google Scholar
  20. Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. Exact Routing in Large Road Networks Using Contraction Hierarchies. Transportation Science, 46(3):388-404, 2012. Google Scholar
  21. Andrew V. Goldberg and Chris Harrelson. Computing the Shortest Path: A* Search Meets Graph Theory. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05), pages 156-165. SIAM, 2005. 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 (GIS'14), pages 193-202. ACM, 2014. Google Scholar
  23. Pierre Hansen. Bicriterion Path Problems. In Multiple Criteria Decision Making - Theory and Application, volume 177 of Lecture Notes in Economics and Mathematical Systems, pages 109-127. Springer, 1980. Google Scholar
  24. Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100-107, 1968. Google Scholar
  25. Stefan Hausberger, Martin Rexeis, Michael Zallinger, and Raphael Luz. Emission Factors from the Model PHEM for the HBEFA Version 3. Technical report I-20/2009, University of Technology, Graz, 2009. Google Scholar
  26. Martin Holzer, Frank Schulz, and Dorothea Wagner. Engineering Multilevel Overlay Graphs for Shortest-Path Queries. ACM Journal of Experimental Algorithmics, 13:2.5:1-2.5:26, 2009. Google Scholar
  27. Gerhard Huber and Klaus Bogenberger. Long-Trip Optimization of Charging Strategies for Battery Electric Vehicles. Transportation Research Record: Journal of the Transportation Research Board, 2497:45-53, 2015. Google Scholar
  28. Donald B. Johnson. A Note on Dijkstra’s Shortest Path Algorithm. Journal of the ACM, 20(3):385-388, 1973. Google Scholar
  29. Donald B. Johnson. Efficient Algorithms for Shortest Paths in Sparse Networks. Journal of the ACM, 24(1):1-13, 1977. Google Scholar
  30. Sebastian Kluge, Claudia Sánta, Stefan Dangl, Stefan M. Wild, Martin Brokate, Konrad Reif, and Fritz Busch. On the Computation of the Energy-Optimal Route Dependent on the Traffic Load in Ingolstadt. Transportation Research Part C: Emerging Technologies, 36:97-115, 2013. Google Scholar
  31. Yuichi Kobayashi, Noboru Kiyama, Hirokazu Aoshima, and Masamori Kashiyama. A Route Search Method for Electric Vehicles in Consideration of Range and Locations of Charging Stations. In Proceedings of the 7th IEEE Intelligent Vehicles Symposium (IV'11), pages 920-925. IEEE, 2011. Google Scholar
  32. Chung-Shou Liao, Shang-Hung Lu, and Zuo-Jun Max Shen. The Electric Vehicle Touring Problem. Transportation Research Part B: Methodological, 86:163-180, 2016. Google Scholar
  33. Chensheng Liu, Jing Wu, and Chengnian Long. Joint Charging and Routing Optimization for Electric Vehicle Navigation Systems. In Proceedings of the 19th International Federation of Automatic Control World Congress (IFAC'14), volume 47 of IFAC Proceedings Volumes, pages 9611-9616. Elsevier, 2014. Google Scholar
  34. Ernesto Q. V. Martins. On a Multicriteria Shortest Path Problem. European Journal of Operational Research, 16(2):236-245, 1984. Google Scholar
  35. Sören Merting, Christian Schwan, and Martin Strehler. Routing of Electric Vehicles: Constrained Shortest Path Problems with Resource Recovering Nodes. In Proceedings of the 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'15), volume 48 of OpenAccess Series in Informatics (OASIcs), pages 29-41. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015. Google Scholar
  36. Martin Sachenbacher, Martin Leucker, Andreas Artmeier, and Julian Haselmayr. Efficient Energy-Optimal Routing for Electric Vehicles. In Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI'11), pages 1402-1407. AAAI Press, 2011. Google Scholar
  37. René Schönfelder and Martin Leucker. Abstract Routing Models and Abstractions in the Context of Vehicle Routing. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI'15), pages 2639-2645. AAAI Press, 2015. Google Scholar
  38. René Schönfelder, Martin Leucker, and Sebastian Walther. Efficient Profile Routing for Electric Vehicles. In Proceedings of the 1st International Conference on Internet of Vehicles (IOV'14), volume 8662 of Lecture Notes in Computer Science, pages 21-30. Springer, 2014. Google Scholar
  39. Frank Schulz, Dorothea Wagner, and Christos Zaroliagis. Using Multi-Level Graphs for Timetable Information in Railway Systems. In Proceedings of the 4th Workshop on Algorithm Engineering &Experiments (ALENEX'02), volume 2409 of Lecture Notes in Computer Science, pages 43-59. Springer, 2002. Google Scholar
  40. Olivia J. Smith, Natashia Boland, and Hamish Waterer. Solving Shortest Path Problems with a Weight Constraint and Replenishment Arcs. Computers &Operations Research, 39(5):964-984, 2012. Google Scholar
  41. 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. ACM, 2012. Google Scholar
  42. Sabine Storandt and Stefan Funke. Cruising with a Battery-Powered Vehicle and Not Getting Stranded. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI'12), pages 1628-1634. AAAI Press, 2012. Google Scholar
  43. Zhonghao Sun and Xingshe Zhou. To Save Money or to Save Time: Intelligent Routing Design for Plug-In Hybrid Electric Vehicle. Transportation Research Part D: Transport and Environment, 43:238-250, 2016. Google Scholar
  44. Timothy M. Sweda, Irina S. Dolinskaya, and Diego Klabjan. Adaptive Routing and Recharging Policies for Electric Vehicles. Working paper no. 14-02, Northwestern University, Illinois, 2014. Google Scholar
  45. Yan Wang, Jianmin Jiang, and Tingting Mu. Context-Aware and Energy-Driven Route Optimization for Fully Electric Vehicles via Crowdsourcing. IEEE Transactions on Intelligent Transportation Systems, 14(3):1331-1345, 2013. Google Scholar
  46. Ady Wiernik and Micha Sharir. Planar Realizations of Nonlinear Davenport-Schinzel Sequences by Segments. Discrete &Computational Geometry, 3(1):15-47, 1988. 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 Imprint Privacy Contact