<p>I have recently been examining the following recently published papers related to the 'Gas Station Problem,' a generalization of the shortest path problem that accounts for fuel consumption by the moving agent initially investigated by <a href="https://www.cs.umd.edu/users/samir/grant/gas-j.pdf" rel="nofollow noreferrer">Khuller et al</a>:</p>
<ol>
<li><p><a href="https://arxiv.org/pdf/2305.19015" rel="nofollow noreferrer">Optimal energetic paths for electric cars</a></p>
</li>
<li><p><a href="https://epubs.siam.org/doi/pdf/10.1137/1.9781611977936.34" rel="nofollow noreferrer">Minimum-cost paths for electric cars</a></p>
</li>
</ol>
<p>These papers present algorithms that appear very similar, perhaps trivially equivalent to the algorithms of these earlier papers without mentioning any of them which I find curious since the papers citing Khuller are very few:</p>
<ol>
<li><p><a href="https://citeseerx.ist.psu.edu/document?repid=rep1&amp;type=pdf&amp;doi=d4c4ecaf63c1d6b27c85683d810f233ac0969911" rel="nofollow noreferrer">Finding Optimal Refueling Policies in Transportation Networks</a></p>
</li>
<li><p><a href="https://arxiv.org/pdf/1706.00195" rel="nofollow noreferrer">A FAST ALGORITHM FOR THE GAS STATION PROBLEM</a></p>
</li>
</ol>
<p>The problems presented in the first two papers appear to be just trivial variations of the gas station problem and their non-trivial solutions appear to be essentially the same as those of the last two papers.It seems to me that one can always take a graph for these problems and trivially construct a graph for the gas station problem and vice versa that give equivalent answers. I am just looking to confirm it.</p>
<p>Here is the definition of the gas station problem:
Given a graph <span class="math-container">$G = (V, E)$</span> where each vertex <span class="math-container">$v \in V$</span> represents a location, and each edge <span class="math-container">$e \in E$</span> has an associated distance or length <span class="math-container">$d(e)$</span>.
A vehicle with a fuel tank capacity of <span class="math-container">$U$</span> units (representing the maximum distance the vehicle can travel on a full tank).
A starting node <span class="math-container">$s \in V$</span> where the vehicle begins its journey with an initial amount of gas <span class="math-container">$\mu_s \leq U$</span>.
A target node <span class="math-container">$t \in V$</span> that the vehicle needs to reach.
Gas prices <span class="math-container">$c(v)$</span> at each vertex <span class="math-container">$v \in V$</span>, representing the cost per unit of gas at that location.
Optionally, a maximum number of refueling stops <span class="math-container">$\Delta$</span> allowed during the journey.
Find the cheapest possible route for the vehicle to travel from the start node <span class="math-container">$s$</span> to the target node <span class="math-container">$t$</span>, deciding both the path taken and the refueling strategy (i.e., where to stop for gas and how much to purchase at each stop), such that the total cost, including the cost of gas purchased along the way, is minimized.</p>
<p>Also the definition of the Optimal Energetic Paths for Electric Cars is as follows:</p>
<p>Given:
A weighted directed graph <span class="math-container">$G = (V, A, c)$</span>, where:
<span class="math-container">$V$</span> is the set of vertices (locations). <span class="math-container">$A \subseteq V \times V$</span> is the set of arcs (roads). <span class="math-container">$c: A \rightarrow \mathbb{R}$</span> assigns a cost to each arc, representing the energy required to traverse it. The cost <span class="math-container">$c(uv)$</span> can be positive, zero, or negative. An electric car with a battery capacity of <span class="math-container">$B$</span> units of energy.</p>
<p>Two vertices <span class="math-container">$s, t \in V$</span>, representing the starting point and the destination.</p>
<p>The car starts at vertex <span class="math-container">$s$</span> with an initial battery charge of <span class="math-container">$b$</span>, where <span class="math-container">$0 \leq b \leq B$</span>.</p>
<p>The car can traverse an arc <span class="math-container">$uv \in A$</span> only if it has sufficient energy, i.e., if the battery charge <span class="math-container">$b$</span> satisfies <span class="math-container">$b \geq c(uv)$</span>.</p>
<p>After traversing an arc <span class="math-container">$uv$</span>, the battery charge updates to: <span class="math-container">$ b' = \min{ b - c(uv), , B } $</span> This accounts for energy consumption (if <span class="math-container">$c(uv) &gt; 0$</span>) or energy gain (if <span class="math-container">$c(uv) &lt; 0$</span>), without exceeding the battery capacity <span class="math-container">$B$</span>.</p>
<p>The graph contains no negative cycles to ensure that the problem is well-defined and solvable.</p>
<p>Objective:</p>
<p>Find a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> such that:</p>
<p>The car can travel from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> starting with the initial battery charge <span class="math-container">$b$</span>.</p>
<p>Determine the maximum possible battery charge upon arrival at <span class="math-container">$t$</span>.</p>
<blockquote>
<p>Are the algorithms developed for the 'gas station problem' and some
seemingly derivative problems equivalent?</p>
</blockquote>

CC BY-SA 4.0
2024-09-24T06:25:57.943Z
Please provide proper references that satisfy scientific standards.  At a minimum, please provide the title, authors, where published, and link to a freely available PDF (if possible).  We want others who are interested in a similar question to be able to find this page via search, so using the paper titles is helpful, and we want people to be able to continue to understand what papers you are referring to even if the links stop working.
D.W.
CC BY-SA 4.0
2024-09-24T06:27:00.420Z
What is your question?  We are a question-and-answer site, so we require you to articulate a specific question.  The question belongs in the body of your post.  The body of your post should stand on its own without having to read the title.  The title should be a short summary of the topic of your post, not the first sentence of your post.  What do you mean by "equivalent"?
D.W.
<ds.algorithms><graph-algorithms><shortest-path>
Are the algorithms developed for the 'gas station problem' and some seemingly derivative problems equivalent?
Ptr
# Are the algorithms developed for the 'gas station problem' and some seemingly derivative problems equivalent?

(Asked by: username_0 on 2024-09-23)

I have recently been examining the following recently published papers related to the 'Gas Station Problem,' a generalization of the shortest path problem that accounts for fuel consumption by the moving agent initially investigated by [Khuller et al](https://www.cs.umd.edu/users/samir/grant/gas-j.pdf):

1. [Optimal energetic paths for electric cars](https://arxiv.org/pdf/2305.19015)
2. [Minimum-cost paths for electric cars](https://epubs.siam.org/doi/pdf/10.1137/1.9781611977936.34)

These papers present algorithms that appear very similar, perhaps trivially equivalent to the algorithms of these earlier papers without mentioning any of them which I find curious since the papers citing Khuller are very few:

1. [Finding Optimal Refueling Policies in Transportation Networks](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=d4c4ecaf63c1d6b27c85683d810f233ac0969911)
2. [A FAST ALGORITHM FOR THE GAS STATION PROBLEM](https://arxiv.org/pdf/1706.00195)

The problems presented in the first two papers appear to be just trivial variations of the gas station problem and their non-trivial solutions appear to be essentially the same as those of the last two papers.It seems to me that one can always take a graph for these problems and trivially construct a graph for the gas station problem and vice versa that give equivalent answers. I am just looking to confirm it.

Here is the definition of the gas station problem:
Given a graph $G = (V, E)$ where each vertex $v \in V$ represents a location, and each edge $e \in E$ has an associated distance or length $d(e)$.
A vehicle with a fuel tank capacity of $U$ units (representing the maximum distance the vehicle can travel on a full tank).
A starting node $s \in V$ where the vehicle begins its journey with an initial amount of gas $\mu\_s \leq U$.
A target node $t \in V$ that the vehicle needs to reach.
Gas prices $c(v)$ at each vertex $v \in V$, representing the cost per unit of gas at that location.
Optionally, a maximum number of refueling stops $\Delta$ allowed during the journey.
Find the cheapest possible route for the vehicle to travel from the start node $s$ to the target node $t$, deciding both the path taken and the refueling strategy (i.e., where to stop for gas and how much to purchase at each stop), such that the total cost, including the cost of gas purchased along the way, is minimized.

Also the definition of the Optimal Energetic Paths for Electric Cars is as follows:

Given:
A weighted directed graph $G = (V, A, c)$, where:
$V$ is the set of vertices (locations). $A \subseteq V \times V$ is the set of arcs (roads). $c: A \rightarrow \mathbb{R}$ assigns a cost to each arc, representing the energy required to traverse it. The cost $c(uv)$ can be positive, zero, or negative. An electric car with a battery capacity of $B$ units of energy.

Two vertices $s, t \in V$, representing the starting point and the destination.

The car starts at vertex $s$ with an initial battery charge of $b$, where $0 \leq b \leq B$.

The car can traverse an arc $uv \in A$ only if it has sufficient energy, i.e., if the battery charge $b$ satisfies $b \geq c(uv)$.

After traversing an arc $uv$, the battery charge updates to: $ b' = \min{ b - c(uv), , B } $ This accounts for energy consumption (if $c(uv) > 0$) or energy gain (if $c(uv) < 0$), without exceeding the battery capacity $B$.

The graph contains no negative cycles to ensure that the problem is well-defined and solvable.

Objective:

Find a path from $s$ to $t$ such that:

The car can travel from $s$ to $t$ starting with the initial battery charge $b$.

Determine the maximum possible battery charge upon arrival at $t$.

> Are the algorithms developed for the 'gas station problem' and some
> seemingly derivative problems equivalent?

**Tags:** ds.algorithms, graph-algorithms, shortest-path

> **Comments:**
> **username_1**: Please provide proper references that satisfy scientific standards.  At a minimum, please provide the title, authors, where published, and link to a freely available PDF (if possible).  We want others who are interested in a similar question to be able to find this page via search, so using the paper titles is helpful, and we want people to be able to continue to understand what papers you are referring to even if the links stop working.  
> **username_1**: What is your question?  We are a question-and-answer site, so we require you to articulate a specific question.  The question belongs in the body of your post.  The body of your post should stand on its own without having to read the title.  The title should be a short summary of the topic of your post, not the first sentence of your post.  What do you mean by "equivalent"?  

---

## 0 answers

