<p>In general, finding least-cost paths with arbitrary time-dependent edge costs is NP-hard, assuming that either (a) waiting at nodes is forbidden and your costs are not FIFO-preserving (e.g., see here for brief discussion on this complexity, as well as others: <a href="https://www.cs.ucsb.edu/~suri/psdir/soda11.pdf" rel="nofollow">https://www.cs.ucsb.edu/~suri/psdir/soda11.pdf</a>) or (b) the cost you are trying to optimize is not simply pure travel time itself (e.g., see <a href="http://algo2.iti.kit.edu/download/gen_obj_func_tch.pdf" rel="nofollow">http://algo2.iti.kit.edu/download/gen_obj_func_tch.pdf</a>).</p>

<p>As an illustrative example of this latter situation (which seems most similar to yours) and continuing with your suggested notation, it is shown in the second paper above that it is NP-hard for the case in which the time-dependent edge cost is defined in the form $c_e(t) = f_e(t) + d_e$, where $f_e$ is the (typical) time-dependent travel-time function that returns the travel time along the edge for a particular time of day $t$ and $d_e$ is some arbitrary time-neutral cost function. It is not hard to show that similar hardness results for other such cases as well, where, e.g., the function uses a multiplier instead of addition (i.e., $c_e(t) = f_e(t) \cdot d_e$), and so on.</p>

<p>Regardless, one can derive pseudo-polynomial time bounds on such cases if, e.g., you are representing your time instants as integer values and assuming there are only a finite number of possible time instants bounded by $T$. In this way, you only need to maintain a single least-cost path <strong>per time instant</strong> $t$ for any given node in the graph, which would give you the running time of $O(T(m + nlogn))$, assuming non-negative cost functions. Taking this idea a step further, since your particular use case assumes that "each edge takes one unit of time to traverse", then this automatically gives you a strongly-polynomial-time algorithm since, in your case, $T \in O(n)$ (because each such path contains $\leq n-1$ edges).</p>

CC BY-SA 3.0
2016-09-09T20:19:16.837Z
2016-09-09T20:19:16.837Z
Michael N. Rice
<p>I'm working on a research project which involves iterative pathfinding over a space whose cells have danger values that change over time.</p>

<p>More specifically, the danger values represent bad weather, and the program uses ten days of weather predictions to find the best route across a section of the earth.</p>

<p><strong>Formalized:</strong>
We're given a graph where, for each edge $e$, the cost on that edge when starting at time t is $c_e(t)$. Each edge takes one unit of time to traverse. Find the min-cost route from $u$ to $v$.</p>

<p>Up until now we've been using a modified A* search, however it is extremely inefficient and has become almost exhaustive.</p>

<p>Is there a better algorithm already out there for such a problem?</p>

<p>I've started to take a look at D* lite, but I don't believe it's the best solution, because we already know what the cost at time t.</p>

<p>Any advice is much appreciated.</p>

<p>Cheers,</p>

<p>Arek Sredzki</p>

CC BY-SA 3.0
2015-10-01T13:50:31.193Z
Can you formalize the problem? How's this: We're given a graph where, for each edge $e$, the cost on that edge when starting at time $t$ is $c_e(t)$. Each edge takes one unit of time to traverse. Find the min-cost route from $u$ to $v$.
usul
<cc.complexity-theory><ds.algorithms><optimization><heuristics>
Pathfinding search over a space with known changing costs
Arek Sredzki
# Pathfinding search over a space with known changing costs

(Asked by: username_0 on 2015-10-01)

I'm working on a research project which involves iterative pathfinding over a space whose cells have danger values that change over time.

More specifically, the danger values represent bad weather, and the program uses ten days of weather predictions to find the best route across a section of the earth.

**Formalized:**
We're given a graph where, for each edge $e$, the cost on that edge when starting at time t is $c\_e(t)$. Each edge takes one unit of time to traverse. Find the min-cost route from $u$ to $v$.

Up until now we've been using a modified A\* search, however it is extremely inefficient and has become almost exhaustive.

Is there a better algorithm already out there for such a problem?

I've started to take a look at D\* lite, but I don't believe it's the best solution, because we already know what the cost at time t.

Any advice is much appreciated.

Cheers,

username_0

**Tags:** cc.complexity-theory, ds.algorithms, optimization, heuristics

> **Comments:**
> **username_1**: Can you formalize the problem? How's this: We're given a graph where, for each edge $e$, the cost on that edge when starting at time $t$ is $c_e(t)$. Each edge takes one unit of time to traverse. Find the min-cost route from $u$ to $v$.  

---

## 1 answers

### Answer by username_2 on 2016-09-09. Score: 2 | Accepted answer

In general, finding least-cost paths with arbitrary time-dependent edge costs is NP-hard, assuming that either (a) waiting at nodes is forbidden and your costs are not FIFO-preserving (e.g., see here for brief discussion on this complexity, as well as others: <https://www.cs.ucsb.edu/~suri/psdir/soda11.pdf>) or (b) the cost you are trying to optimize is not simply pure travel time itself (e.g., see <http://algo2.iti.kit.edu/download/gen_obj_func_tch.pdf>).

As an illustrative example of this latter situation (which seems most similar to yours) and continuing with your suggested notation, it is shown in the second paper above that it is NP-hard for the case in which the time-dependent edge cost is defined in the form $c\_e(t) = f\_e(t) + d\_e$, where $f\_e$ is the (typical) time-dependent travel-time function that returns the travel time along the edge for a particular time of day $t$ and $d\_e$ is some arbitrary time-neutral cost function. It is not hard to show that similar hardness results for other such cases as well, where, e.g., the function uses a multiplier instead of addition (i.e., $c\_e(t) = f\_e(t) \cdot d\_e$), and so on.

Regardless, one can derive pseudo-polynomial time bounds on such cases if, e.g., you are representing your time instants as integer values and assuming there are only a finite number of possible time instants bounded by $T$. In this way, you only need to maintain a single least-cost path **per time instant** $t$ for any given node in the graph, which would give you the running time of $O(T(m + nlogn))$, assuming non-negative cost functions. Taking this idea a step further, since your particular use case assumes that "each edge takes one unit of time to traverse", then this automatically gives you a strongly-polynomial-time algorithm since, in your case, $T \in O(n)$ (because each such path contains $\leq n-1$ edges).


---

