TY - GEN
T1 - Optimal Energetic Paths for Electric Cars
AU - Dorfman, Dani
AU - Kaplan, Haim
AU - Tarjan, Robert E.
AU - Zwick, Uri
N1 - Publisher Copyright:
© Dani Dorfman, Haim Kaplan, Robert E. Tarjan, and Uri Zwick.
PY - 2023/9
Y1 - 2023/9
N2 - A weighted directed graph G = (V, A, c), where A ⊆ V × V and c : A → R, 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.
AB - A weighted directed graph G = (V, A, c), where A ⊆ V × V and c : A → R, 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.
KW - Battery depletion
KW - Electric cars
KW - Optimal Paths
UR - http://www.scopus.com/inward/record.url?scp=85173461282&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85173461282&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ESA.2023.42
DO - 10.4230/LIPIcs.ESA.2023.42
M3 - Conference contribution
AN - SCOPUS:85173461282
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 31st Annual European Symposium on Algorithms, ESA 2023
A2 - Li Gortz, Inge
A2 - Farach-Colton, Martin
A2 - Puglisi, Simon J.
A2 - Herman, Grzegorz
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 31st Annual European Symposium on Algorithms, ESA 2023
Y2 - 4 September 2023 through 6 September 2023
ER -