10
$\begingroup$

Motivation

The other day, I was travelling around the city with public transport and I made up an interesting graph problem modelling the problem of finding the shortest-time connection between two places.

We all know the classical "Shortest path problem": Given a directed graph $G=(V,E)$ with edge-lengths $w_e\in\mathbb{R}_0^+,\,e\in E$ and two vertices $s,t\in V$, find the the shortest path between $s$ and $t$ (i.e., the path minimizing the total edge-length). Assuming non-negative edge-lengths, there are various algorithms and the problem is easy.

This is a good model for the case that we are walking, for example. The vertices are crossroads in our network of roads and each edge has fixed length -- in meters, for instance. Another possible interpretation of the edge-weights $w_e$ is the time that it takes us to go from one of its vertices to the other. This is the interpretation that interests me now.

Problem

I now want to model the following situation. I want to travel from point A to point B in a city via public transport and minimize time. The public transport network can be easily modelled as a directed graph as you would expect. The interesting part are the edge-weights (that model time) -- public transport (buses, for instance) leave only in certain intervals, which are different for every stop (vertex in graph). In other words -- the edge-weights are not constant, they change depending on the time we want to use the edge.

How to model this situation: We have a directed graph $G=(V,E)$ and an edge-weight function $w\colon E\times \mathbb{R}_0^+\rightarrow\mathbb{R}_0^+$ that takes time as its argument and returns time that it takes to use the edge in our path. For example, if the bus from vertex $v$ to vertex $u$ leaves at $t=10$ and it takes $5$ time and we arrive at vertex $v$ at $t=8$, then $w(vu,8)=7$ is the edge-weight. Clearly, $w(vu,10)=5$.

It is slightly tricky to define total weight of path, but we can do it recursively. Let $P=v_1v_2\ldots v_{k-1} v_k$ be a directed path. If $k=1$ then $w(P)=0$. Otherwise, $w(P)=w(P')+w(v_{k-1}v_k,w(P'))$, where $P'$ is the sub-path of $P$ without $v_k$. This is a natural definition corresponding to the real-world situation.

We can now study the problem under various assumptions on the function $w$. The natural assumption is $$w(e,t)\leq w(e,t+\Delta)+\Delta \text{ for all }e\in E,\Delta\geq 0,$$ which models "waiting for $\Delta$ time".

If the function "behaves nicely" it may be possible to reduce this problem to the classical Shortest path problem. But we could ask what happens when the weight-functions get wild. And what if we drop the assumption on waiting?

Questions

My questions are the following.

  • Has this problem been asked before? It seems kind of natural.
  • Is there any research on it? It seems to me that there are various subproblems to be asked and studied -- mainly regarding the properties of the weight-function.
  • Can we reduce this problem (possibly under some assumptions) to the classical shortest path problem?
Improve this question
$\endgroup$
2
  • $\begingroup$ Here's a natural baseline approach against which more research-level answers can be compared. Model it as a reachability problem by discretizing the time units into a collection of instants $T$, and make a new graph with vertices $V' = T \times V$. You can then put edges $(t_0,v_0) \to (t_1,v_1)$ where $t_1 = w((v_0,v_1),t_0)$. This is already efficient for a lot of use-cases (eg with bus schedules, you just let $T$ be the times when the buses arrive/leave their stops), but doesn't work perfectly all the time (consider when $w$ varies continuously over time), and is slow if $T$ is large. $\endgroup$
    – Andrew Morgan
    Aug 12, 2016 at 22:15
  • $\begingroup$ One simple variant of this problem (where edge weights depend linearly on time) is called "parametric shortest path". $\endgroup$
    – Neal Young
    Aug 13, 2016 at 21:11

3 Answers 3

Reset to default
8
$\begingroup$

This is known as the "time-dependent shortest path" problem. Indeed research has been done for this problem; see for example the classical paper by Orda and Rom, and this recent SODA paper which proves that when the weight function of each edge is polynomial-size piecewise-linear, then the shortest path between two fixed points changes $n^{\Theta(\log n)}$ times.

Dijkstra's algorithm can indeed be used for this problem, when the waiting policy is imposed, that is, wait at a node if that reduces the final arriving time. Without the waiting policy the situation is much wilder: the shortest path may not be simple, subpath of a shortest path might not be the shortest between the two endpoints of the subpath, paths traversing through infinite number of edges may have finite arriving time, etc. See again the paper by Orda and Rom for more discussion.

Improve this answer
$\endgroup$
3
$\begingroup$

Are you aware of the "shortest nondecreasing paths" problem? It was defined to model situations such as these. Although it's a bit less expressive compared to your formulation, there are fast algs for it.

Improve this answer
$\endgroup$
1
$\begingroup$

If you assume that the times are integral (which makes sense in the case of public transit), you can make a time-expanded network, similar to the one suggested by Ford-Fulkerson for max-flow over time (or quickest flow) and find the shortest path in this graph instead.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.