Document Open Access Logo

Optimal Energetic Paths for Electric Cars

Authors Dani Dorfman , Haim Kaplan , Robert E. Tarjan , Uri Zwick

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.42.pdf
  • Filesize: 0.82 MB
  • 17 pages

Document Identifiers

Author Details

Dani Dorfman
  • Tel Aviv University, Israel
Haim Kaplan
  • Tel Aviv University, Israel
Robert E. Tarjan
  • Princeton University, NJ, USA
Uri Zwick
  • Tel Aviv University, Israel

Funding

  • Dorfman, Dani: Supported by ISF grant 2854/20.
  • Kaplan, Haim: Supported by ISF grant 1595/19 and the Blavatnik Family Foundation.
  • Tarjan, Robert E.: Partially supported by a gift from Microsoft.
  • Zwick, Uri: Supported by ISF grant 2854/20.

Acknowledgements

We would like to thank the anonymous reviewers for their comments, for pointing out reference [Jochen Eisner et al., 2011], and for pointing out the relation to the 1-VASS problem.

Cite As Get BibTex

Dani Dorfman, Haim Kaplan, Robert E. Tarjan, and Uri Zwick. Optimal Energetic Paths for Electric Cars. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.42

Abstract

A weighted directed graph G = (V,A,c), where A ⊆ V× V and c:A → ℝ, naturally describes a road network in which an electric car, or vehicle (EV), can roam. An arc uv ∈ A models a road segment connecting the two vertices (junctions) u and v. The cost c(uv) of the arc uv is the amount of energy the car needs to travel from u to v. This amount can be positive, zero or negative. We consider both the more realistic scenario where there are no negative cycles in the graph, as well as the more challenging scenario, which can also be motivated, where negative cycles may be present.
The electric car has a battery that can store up to B units of energy. The car can traverse an arc uv ∈ A only if it is at u and the charge b in its battery satisfies b ≥ c(uv). If the car traverses the arc uv then it reaches v with a charge of min{b-c(uv),B} in its battery. Arcs with a positive cost deplete the battery while arcs with negative costs may charge the battery, but not above its capacity of B. If the car is at a vertex u and cannot traverse any outgoing arcs of u, then it is stuck and cannot continue traveling.
We consider the following natural problem: Given two vertices s,t ∈ V, can the car travel from s to t, starting at s with an initial charge b, where 0 ≤ b ≤ B? If so, what is the maximum charge with which the car can reach t? Equivalently, what is the smallest depletion δ_{B,b}(s,t) such that the car can reach t with a charge of b-δ_{B,b}(s,t) in its battery, and which path should the car follow to achieve this? We also refer to δ_{B,b}(s,t) as the energetic cost of traveling from s to t. We let δ_{B,b}(s,t) = ∞ if the car cannot travel from s to t starting with an initial charge of b. The problem of computing energetic costs is a strict generalization of the standard shortest paths problem.
When there are no negative cycles, the single-source version of the problem can be solved using simple adaptations of the classical Bellman-Ford and Dijkstra algorithms. More involved algorithms are required when the graph may contain negative cycles.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Electric cars
  • Optimal Paths
  • Battery depletion

Metrics

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

References

  1. Shaull Almagor, Nathann Cohen, Guillermo A. Pérez, Mahsa Shirmohammadi, and James Worrell. Coverability in 1-vass with disequality tests. In Proc. of 31st CONCUR, volume 171 of LIPIcs, pages 38:1-38:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2020.38.
  2. Andreas Artmeier, Julian Haselmayr, Martin Leucker, and Martin Sachenbacher. The shortest path problem revisited: Optimal routing for electric vehicles. KI, 6359:309-316, 2010. Google Scholar
  3. Moritz Baum, Julian Dibbelt, Thomas Pajor, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Energy-optimal routes for battery electric vehicles. Algorithmica, 82:1490-1546, 2020. Google Scholar
  4. Richard Bellman. On a routing problem. Quarterly of Applied Mathematics, 16:87-90, 1958. Google Scholar
  5. Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen. Negative-weight single-source shortest paths in near-linear time. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 600-611. IEEE, 2022. URL: https://doi.org/10.1109/FOCS54457.2022.00063.
  6. Lubos Brim and Jakub Chaloupka. Using strategy improvement to stay alive. Int. J. Found. Comput. Sci., 23(3):585-608, 2012. URL: https://doi.org/10.1142/S0129054112400291.
  7. Lubos Brim, Jakub Chaloupka, Laurent Doyen, Raffaella Gentilini, and Jean-François Raskin. Faster algorithms for mean-payoff games. Formal methods in system design, 38(2):97-118, 2011. Google Scholar
  8. Karl Bringmann, Alejandro Cassis, and Nick Fischer. Negative-weight single-source shortest paths in near-linear time: Now faster! CoRR, abs/2304.05279, 2023. URL: https://doi.org/10.48550/arXiv.2304.05279.
  9. Shiri Chechik, Haim Kaplan, Mikkel Thorup, Or Zamir, and Uri Zwick. Bottleneck Paths and Trees and Deterministic Graphical Games. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), pages 27:1-27:13, 2016. Google Scholar
  10. Boris V. Cherkassky, Loukas Georgiadis, Andrew V. Goldberg, Robert E. Tarjan, and Renato F. Werneck. Shortest-path feasibility algorithms: An experimental evaluation. ACM J. Exp. Algorithmics, 14, 2009. URL: https://doi.org/10.1145/1498698.1537602.
  11. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959. URL: https://doi.org/10.1007/BF01386390.
  12. Dani Dorfman, Haim Kaplan, and Uri Zwick. A faster deterministic exponential time algorithm for energy games and mean payoff games. In Proc. of 46th ICALP, volume 132 of LIPIcs, pages 114:1-114:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.114.
  13. Ran Duan and Seth Pettie. Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. In Proc. of 20th SODA, pages 384-391, 2009. URL: https://doi.org/10.1145/1496770.1496813.
  14. Jochen Eisner, Stefan Funke, and Sabine Storandt. Optimal route planning for electric vehicles in large networks. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2011, San Francisco, California, USA, August 7-11, 2011. AAAI Press, 2011. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3637.
  15. Lester R. Ford. Network flow theory. Technical Report Paper P-923, RAND Corporation, Santa Monica, California, 1956. Google Scholar
  16. Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596-615, 1987. URL: https://doi.org/10.1145/28869.28874.
  17. Harold N. Gabow and Robert E. Tarjan. Algorithms for two bottleneck optimization problems. Journal of Algorithms, 9(3):411-417, 1988. Google Scholar
  18. Judith F. Gilsinn and Christoph Witzgall. A performance comparison of labeling algorithms for calculating shortest path trees. Technical Report 772, US National Bureau of Standards, 1973. Google Scholar
  19. Andrew V. Goldberg. Scaling algorithms for the shortest paths problem. SIAM J. Comput., 24(3):494-504, 1995. URL: https://doi.org/10.1137/S0097539792231179.
  20. Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan, and Uri Zwick. Hollow heaps. ACM Trans. Algorithms, 13(3):42:1-42:27, 2017. URL: https://doi.org/10.1145/3093240.
  21. Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern., 4(2):100-107, 1968. URL: https://doi.org/10.1109/TSSC.1968.300136.
  22. Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, 24(1):1-13, 1977. URL: https://doi.org/10.1145/321992.321993.
  23. Samir Khuller, Azarakhsh Malekian, and Julián Mestre. To fill or not to fill: The gas station problem. ACM Transactions on Algorithms (TALG), 7(3):1-16, 2011. Google Scholar
  24. David A Klarner, editor. The mathematical gardner. Wadsworth International, 1982. Google Scholar
  25. Donald E. Knuth. A generalization of Dijkstra’s algorithm. Information Processing Letters, 6(1):1-5, 1977. URL: https://doi.org/10.1016/0020-0190(77)90002-3.
  26. Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, and Karol Wegrzycki. Coverability in VASS revisited: Improving rackoff’s bound to obtain conditional optimality. CoRR, abs/2305.01581, 2023. URL: https://doi.org/10.48550/arXiv.2305.01581.
  27. Daniel J. Lehmann. Algebraic structures for transitive closure. Theor. Comput. Sci., 4(1):59-76, 1977. URL: https://doi.org/10.1016/0304-3975(77)90056-1.
  28. László Lovász. Combinatorial problems and exercises, volume 361. American Mathematical Soc., 2007. Google Scholar
  29. Omid Madani, Mikkel Thorup, and Uri Zwick. Discounted deterministic markov decision processes and discounted all-pairs shortest paths. ACM Trans. Algorithms, 6(2):33:1-33:25, 2010. URL: https://doi.org/10.1145/1721837.1721849.
  30. Mehryar Mohri. Semiring frameworks and algorithms for shortest-distance problems. J. Autom. Lang. Comb., 7(3):321-350, 2002. URL: https://doi.org/10.25596/jalc-2002-321.
  31. Seth Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comput. Sci., 312(1):47-74, 2004. URL: https://doi.org/10.1016/S0304-3975(03)00402-X.
  32. Robert E. Tarjan. Shortest paths. Technical report, AT&T Bell Laboratories, 1981. Google Scholar
  33. Robert E. Tarjan. A unified approach to path problems. Journal of the ACM, 28(3):577-593, 1981. URL: https://doi.org/10.1145/322261.322272.
  34. Robert E. Tarjan. Data structures and network algorithms. SIAM, 1983. Google Scholar
  35. Virginia Vassilevska. Nondecreasing paths in a weighted graph or: how to optimally read a train schedule. In Proc. of 19th SODA, pages 465-472, 2008. URL: https://doi.org/10.1145/1347082.1347133.
  36. Virginia Vassilevska, Ryan Williams, and Raphael Yuster. All pairs bottleneck paths and max-min matrix products in truly subcubic time. Theory Comput., 5(1):173-189, 2009. URL: https://doi.org/10.4086/toc.2009.v005a009.
  37. Peter Winkler. Mathematical puzzles: a connoisseur’s collection. A K Peters, 2004. Google Scholar
  38. Uri Zwick. Exact and approximate distances in graphs - A survey. In Proc. of 9th ESA, volume 2161 of Lecture Notes in Computer Science, pages 33-48. Springer, 2001. URL: https://doi.org/10.1007/3-540-44676-1_3.
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