Abstract
Electric vehicles (EV) powered by batteries will play a significant role in the road traffic of the future. The unique characteristics of such EVs – limited cruising range, long recharge times, and the ability to regain energy during deceleration – require novel routing algorithms, since the task is now to determine the most economical route rather than just the shortest one. This paper proposes extensions to general shortest-path algorithms that address the problem of energy-optimal routing. Specifically, we (i) formalize energy-efficient routing in the presence of rechargeable batteries as a special case of the constrained shortest path problem (CSPP) with hard and soft constraints, and (ii) present an adaption of a general shortest path algorithm (using an energy graph, i.e., a graph with a weight function representing the energy consumption) that respects the given constraints and has a worst case complexity of O(n 3). The presented algorithms have been implemented and evaluated within a prototypic navigation system for energy-efficient routing.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Dijkstra, E.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271 (1959)
Bellman, R.: On a routing problem. Quart. of Appl. Math. 16(1), 87–90 (1958)
Ford Jr., L.R.: Network flow theory. Technical report, RAND (1956)
Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 319–333. Springer, Heidelberg (2008)
Sanders, P., Schultes, D.: Highway Hierarchies Hasten Exact Shortest Path Queries. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 568–579. Springer, Heidelberg (2005)
Bast, H., Funke, S., Sanders, P., Schultes, D.: Fast routing in road networks with transit nodes. Science 316(5824), 566 (2007)
Joksch, H.C.: The shortest route problem with constraints. Journal of Mathematical Analysis and Applications 14, 191–197 (1966)
Garey, M., Johnson, D.: Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)
Gallo, G., Pallottino, S.: Shortest path methods: A unifying approach. Mathematical Programming Studies, vol. 26. Springer, Heidelberg (1986)
Cherkassky, B.V., Goldberg, A.V., Radzik, T.: Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming 73(2) (1993)
Johnson, D.B.: A note on Dijkstra’s shortest path algorithm. Journal of the ACM 20(3), 385–388 (1973)
Zhan, F.B., Noon, C.E.: A comparison between label-setting and label-correcting algorithms for computing one-to-one shortest paths. Journal of Geographic Information and Decision Analysis 4(2), 1–11 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Artmeier, A., Haselmayr, J., Leucker, M., Sachenbacher, M. (2010). The Shortest Path Problem Revisited: Optimal Routing for Electric Vehicles. In: Dillmann, R., Beyerer, J., Hanebeck, U.D., Schultz, T. (eds) KI 2010: Advances in Artificial Intelligence. KI 2010. Lecture Notes in Computer Science(), vol 6359. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16111-7_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-16111-7_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16110-0
Online ISBN: 978-3-642-16111-7
eBook Packages: Computer ScienceComputer Science (R0)