Optimal energetic paths for electric cars
Preprint
Abstract
A weighted directed graph $G=(V,A,c)$, where $A\subseteq V\times V$ and $c:A\to R$, describes a road network in which an electric car can roam. An arc $uv$ models a road segment connecting the two vertices $u$ and $v$. The cost $c(uv)$ of an arc $uv$ is the amount of energy the car needs to traverse the arc. This amount may be positive, zero or negative. To make the problem realistic, we assume there are no negative cycles. The car has a battery that can store up to $B$ units of energy. It can traverse an arc $uv\in A$ only if it is at $u$ and the charge $b$ in its battery satisfies $b\ge c(uv)$. If it traverses the arc, it reaches $v$ with a charge of $\min(b-c(uv),B)$. Arcs with positive costs deplete the battery, arcs with negative costs charge the battery, but not above its capacity of $B$. Given $s,t\in V$, can the car travel from $s$ to $t$, starting at $s$ with an initial charge $b$, where $0\le b\le B$? If so, what is the maximum charge with which the car can reach $t$? Equivalently, what is the smallest $δ_{B,b}(s,t)$ such that the car can reach $t$ with a charge of $b-δ_{B,b}(s,t)$, and which path should the car follow to achieve this? We refer to $δ_{B,b}(s,t)$ as the energetic cost of traveling from $s$ to $t$. We let $δ_{B,b}(s,t)=\infty$ 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. We show that the single-source minimum energetic paths problem can be solved using simple, but subtle, adaptations of the Bellman-Ford and Dijkstra algorithms. To make Dijkstra's algorithm work in the presence of negative arcs, but no negative cycles, we use a variant of the $A^*$ search heuristic. These results are explicit or implicit in some previous papers. We provide a simpler and unified description of these algorithms.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!2023
- Energy-Optimal Routes for Battery Electric VehiclesAlgorithmica, 2019
- USING STRATEGY IMPROVEMENT TO STAY ALIVEInternational Journal of Foundations of Computer Science, 2012
- Discounted deterministic Markov decision processes and discounted all-pairs shortest pathsACM Transactions on Algorithms, 2010
- The Shortest Path Problem Revisited: Optimal Routing for Electric Vehicles2010
- Shortest Path Feasibility Algorithms: An Experimental Evaluation2008
- To Fill or Not to Fill: The Gas Station Problem2007
- Scaling Algorithms for the Shortest Paths ProblemSIAM Journal on Computing, 1995
- Algorithms for two bottleneck optimization problemsJournal of Algorithms, 1988
- A Formal Basis for the Heuristic Determination of Minimum Cost PathsIEEE Transactions on Systems Science and Cybernetics, 1968