Document Open Access Logo

Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles

Authors Moritz Baum, Julian Dibbelt, Dorothea Wagner, Tobias Zündorf

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.11.pdf
  • Filesize: 0.54 MB
  • 16 pages

Document Identifiers

Author Details

Moritz Baum
Julian Dibbelt
Dorothea Wagner
Tobias Zündorf

Cite As Get BibTex

Moritz Baum, Julian Dibbelt, Dorothea Wagner, and Tobias Zündorf. Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.11

Abstract

We study the problem of computing constrained shortest paths for battery electric vehicles. Since battery capacities are limited, fastest routes are often infeasible. Instead, users are interested in fast routes where the energy consumption does not exceed the battery capacity. For that, drivers can deliberately reduce speed to save energy. Hence, route planning should provide both path and speed recommendations. To tackle the resulting NP-hard optimization problem, previous work trades correctness or accuracy of the underlying model for practical running times. In this work, we present a novel framework to compute optimal constrained shortest paths for electric vehicles that uses more realistic physical models, while taking speed adaptation into account. Careful algorithm engineering makes the approach practical even on large, realistic road networks: We compute optimal solutions in less than a second for typical battery capacities, matching performance of previous inexact methods. For even faster performance, the approach can easily be extended with heuristics that provide high quality solutions within milliseconds.

Subject Classification

Keywords
  • electric vehicles
  • constrained shortest paths
  • algorithm engineering

Metrics

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

References

  1. Shubham Agrawal, Hong Zheng, Srinivas Peeta, and Amit Kumar. Routing Aspects of Electric Vehicle Drivers and their Effects on Network Performance. Transportation Research Part D: Transport and Environment, 46:246-266, 2016. Google Scholar
  2. Johannes Asamer, Anita Graser, Bernhard Heilmann, and Mario Ruthmair. Sensitivity Analysis for Energy Demand Estimation of Electric Vehicles. Transportation Research Part D: Transport and Environment, 46:182-199, 2016. Google Scholar
  3. 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. In Algorithm Engineering: Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 19-80. Springer, 2016. Google Scholar
  4. 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 Proceedings of the 13th IEEE Congress on Evolutionary Computation (CEC'11), pages 2359-2366. IEEE, 2011. Google Scholar
  5. Gernot V. Batz, Robert Geisberger, Peter Sanders, and Christian Vetter. Minimum Time-Dependent Travel Times with Contraction Hierarchies. ACM Journal of Experimental Algorithmics, 18:1.4:1-1.4:43, 2013. 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. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2014.138.
  9. Moritz Baum, Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. Energy-Optimal Routes for Electric Vehicles. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS'13), pages 54-63. ACM, 2013. Google Scholar
  10. Luca Bedogni, Luciano Bononi, Marco Di Felice, Alfredo D'Elia, Randolf Mock, Francesco Morandi, Simone Rondelli, Tullio Salmon Cinotti, and Fabio Vergari. An Integrated Simulation Framework to Model Electric Vehicles Operations and Services. IEEE Transactions on Vehicular Technology, 65(8):5900-5917, 2016. Google Scholar
  11. Marco Blanco, Ralf Borndörfer, Nam-Dung Hoang, Anton Kaier, Adam Schienle, Thomas Schlechte, and Swen Schlobach. Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind. In Proceedings of the 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'16), volume 54 of OpenAccess Series in Informatics (OASIcs), pages 12:1-12:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2016.12.
  12. Karin Brundell-Freij and Eva Ericsson. Influence of Street Characteristics, Driver Category and Car Performance on Urban Driving Patterns. Transportation Research Part D: Transport and Environment, 10(3):213-229, 2005. Google Scholar
  13. Daniel Delling and Dorothea Wagner. Time-Dependent Route Planning. In Robust and Online Large-Scale Optimization, volume 5868 of Lecture Notes in Computer Science, pages 207-230. Springer, 2009. Google Scholar
  14. Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. User-Constrained Multi-Modal Route Planning. ACM Journal of Experimental Algorithmics, 19:3.2:1-3.2:19, 2015. Google Scholar
  15. Edsger W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1(1):269-271, 1959. Google Scholar
  16. 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
  17. Stephan Erb, Moritz Kobitzsch, and Peter Sanders. Parallel Bi-Objective Shortest Paths Using Weight-Balanced B-Trees with Bulk Updates. In Proceedings of the 13th International Symposium on Experimental Algorithms (SEA'14), volume 8504 of Lecture Notes in Computer Science, pages 111-122. Springer, 2014. Google Scholar
  18. Chiara Fiori, Kyoungho Ahn, and Hesham A. Rakha. Power-Based Electric Vehicle Energy Consumption Model: Model Development and Validation. Applied Energy, 168:257-268, 2016. Google Scholar
  19. Carlos Flores, Vicente Milanés, Joshué Pérez, David González, and Fawzi Nashashibi. Optimal Energy Consumption Algorithm Based on Speed Reference Generation for Urban Electric Vehicles. In Proceedings of the 11th IEEE Intelligent Vehicles Symposium (IV'15), pages 730-735. IEEE, 2015. Google Scholar
  20. Luca Foschini, John Hershberger, and Subhash Suri. On the Complexity of Time-Dependent Shortest Paths. Algorithmica, 68(4):1075-1097, 2014. Google Scholar
  21. Stefan Funke and Sabine Storandt. Polynomial-Time Construction of Contraction Hierarchies for Multi-Criteria Objectives. In Proceedings of the 15th Meeting on Algorithm Engineering &Experiments (ALENEX'13), pages 31-54. SIAM, 2013. Google Scholar
  22. Robert Geisberger, Moritz Kobitzsch, and Peter Sanders. Route Planning with Flexible Objective Functions. In Proceedings of the 12th Workshop on Algorithm Engineering &Experiments (ALENEX'10), pages 124-137. SIAM, 2010. Google Scholar
  23. 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
  24. 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
  25. 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
  26. Gabriel Y. Handler and Israel Zang. A Dual Algorithm for the Constrained Shortest Path Problem. Networks, 10(4):293-309, 1980. Google Scholar
  27. 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
  28. Frederik Hartmann and Stefan Funke. Energy-Efficient Routing: Taking Speed into Account. In Proceedings of the 37th Annual German Conference on Advances in Artificial Intelligence (KI'14), volume 8736 of Lecture Notes in Computer Science, pages 86-97. Springer, 2014. Google Scholar
  29. 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
  30. James Larminie and John Lowry. Electric Vehicle Technology Explained, 2nd Edition. John Wiley &Sons, Ltd., 2012. Google Scholar
  31. Mingsong Lv, Nan Guan, Ye Ma, Dong Ji, Erwin Knippel, Xue Liu, and Wang Yi. Speed Planning for Solar-Powered Electric Vehicles. In Proceedings of the 7th International Conference on Future Energy Systems (e-Energy'16), pages 6:1-6:10. ACM, 2016. Google Scholar
  32. Enrique Machuca and Lawrence Mandow. Multiobjective Heuristic Search in Road Maps. Expert Systems with Applications, 39(7):6435-6445, 2012. Google Scholar
  33. Lawrence Mandow and José-Luis Pérez-de-la-Cruz. Multiobjective A* Search with Consistent Heuristics. Journal of the ACM, 57(5):27:1-27:24, 2010. 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. 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
  36. Peter Sanders and Lawrence Mandow. Parallel Label-Setting Multi-Objective Shortest Path Search. In Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS'13), pages 215-224. IEEE, 2013. Google Scholar
  37. 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
  38. Sabine Storandt. Route Planning for Bicycles - Exact Constrained Shortest Paths Made Practical via Contraction Hierarchy. In Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS'12), pages 234-242. AAAI Press, 2012. Google Scholar
  39. Tessa Tielert, David Rieger, Hannes Hartenstein, Raphael Luz, and Stefan Hausberger. Can V2X Communication Help Electric Vehicles Save Energy? In Proceedings of the 12th International Conference on ITS Telecommunications (ITST'12), pages 232-237. IEEE, 2012. Google Scholar
  40. Chi Tung Tung and Kim Lin Chew. A Multicriteria Pareto-Optimal Path Algorithm. European Journal of Operational Research, 62(2):203-209, 1992. Google Scholar
  41. 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
  42. Enjian Yao, Zhiqiang Yang, Yuanyuan Song, and Ting Zuo. Comparison of Electric Vehicle’s Energy Consumption Factors for Different Road Types. Discrete Dynamics in Nature and Society, 2013. 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