Speed-Consumption Tradeoff for Electric Vehicle Route Planning

Authors Moritz Baum, Julian Dibbelt, Lorenz Hübschle-Schneider, Thomas Pajor, Dorothea Wagner



PDF
Thumbnail PDF

File

OASIcs.ATMOS.2014.138.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Moritz Baum
Julian Dibbelt
Lorenz Hübschle-Schneider
Thomas Pajor
Dorothea Wagner

Cite AsGet BibTex

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. Open Access Series in Informatics (OASIcs), Volume 42, pp. 138-151, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/OASIcs.ATMOS.2014.138

Abstract

We study the problem of computing routes for electric vehicles (EVs) in road networks. Since their battery capacity is limited, and consumed energy per distance increases with velocity, driving the fastest route is often not desirable and may even be infeasible. On the other hand, the energy-optimal route may be too conservative in that it contains unnecessary detours or simply takes too long. In this work, we propose to use multicriteria optimization to obtain Pareto sets of routes that trade energy consumption for speed. In particular, we exploit the fact that the same road segment can be driven at different speeds within reasonable intervals. As a result, we are able to provide routes with low energy consumption that still follow major roads, such as freeways. Unfortunately, the size of the resulting Pareto sets can be too large to be practical. We therefore also propose several nontrivial techniques that can be applied on-line at query time in order to speed up computation and filter insignificant solutions from the Pareto sets. Our extensive experimental study, which uses a real-world energy consumption model, reveals that we are able to compute diverse sets of alternative routes on continental networks that closely resemble the exact Pareto set in just under a second---several orders of magnitude faster than the exhaustive algorithm.
Keywords
  • electric vehicles
  • shortest paths
  • route planning
  • bicriteria optimization
  • algorithm engineering

Metrics

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

References

  1. 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, volume 6359 of Lecture Notes in Computer Science, pages 309-316. Springer, 2010. Google Scholar
  2. 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. Technical Report MSR-TR-2014-4, Microsoft Research, 2014. Google Scholar
  3. 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 IEEE Congress on Evolutionary Computation, pages 2359-2366. IEEE, 2011. Google Scholar
  4. 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, pages 54-63. ACM Press, 2013. Google Scholar
  5. Richard Bellman. On a Routing Problem. Quarterly of Applied Mathematics, 16:87-90, 1958. Google Scholar
  6. Lee R. Dice. Measures of the Amount of Ecologic Association between Species. Ecology, 26(3):297-302, 1945. Google Scholar
  7. Edsger W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1:269-271, 1959. Google Scholar
  8. Yann Disser, Matthias Müller-Hannemann, and Mathias Schnee. Multi-Criteria Shortest Paths in Time-Dependent Train Networks. In Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08), volume 5038 of Lecture Notes in Computer Science, pages 347-361. Springer, 2008. Google Scholar
  9. Jochen Eisner, Stefan Funke, and Sabine Storandt. Optimal Route Planning for Electric Vehicles in Large Network. In Proceedings of the 25th AAAI Conference on Artificial Intelligence. AAAI Press, 2011. Google Scholar
  10. 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
  11. Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD'96), pages 226-231. AAAI Press, 1996. Google Scholar
  12. Stefan Funke and Sabine Storandt. Polynomial-Time Construction of Contraction Hierarchies for Multi-criteria Objectives. In Proceedings of the 15th Meeting on Algorithm Engineering and Experiments (ALENEX'13), pages 31-54. SIAM, 2013. Google Scholar
  13. Michael R. Garey and David S. Johnson. Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979. Google Scholar
  14. Robert Geisberger, Moritz Kobitzsch, and Peter Sanders. Route Planning with Flexible Objective Functions. In Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX'10), pages 124-137. SIAM, 2010. Google Scholar
  15. Pierre Hansen. Bricriteria Path Problems. In Multiple Criteria Decision Making - Theory and Application -, pages 109-127. Springer, 1979. Google Scholar
  16. Peter E. Hart, Nils Nilsson, and Bertram Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4:100-107, 1968. Google Scholar
  17. 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
  18. Lorenz Hübschle-Schneider. Speed-Consumption Trade-Off for Electric Vehicle Routing. Bachelor thesis, Karlsruhe Institute of Technology, 2013. Google Scholar
  19. Enrique Machuca and Lawrence Mandow. Multiobjective Heuristic Search in Road Maps. Expert Systems with Applications, 39(7):6435-6445, 2012. Google Scholar
  20. 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
  21. Ernesto Queiros Martins. On a Multicriteria Shortest Path Problem. European Journal of Operational Research, 26(3):236-245, 1984. Google Scholar
  22. Matthias Müller-Hannemann and Karsten Weihe. Pareto Shortest Paths is Often Feasible in Practice. In Proceedings of the 5th International Workshop on Algorithm Engineering (WAE'01), volume 2141 of Lecture Notes in Computer Science, pages 185-197. Springer, 2001. Google Scholar
  23. 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 Press, 2011. Google Scholar
  24. Peter Sanders and Lawrence Mandow. Parallel Label-Setting Multi-Objective Shortest Path Search. In Proceedings of the 27th International Parallel and Distributed Processing Symposium (IPDPS'13), pages 215-224. IEEE Computer Society, 2013. Google Scholar
  25. 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, pages 20-25. ACM Press, 2012. Google Scholar
  26. 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
  27. Eckart Zitzler and Lothar Thiele. Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. Evolutionary Computation, IEEE Transactions on, 3(4):257-271, 1999. 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