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?