# Do you know a shortes path algorithm for weighted graphs with hard time windows on the edges and waiting allowed?

Title says it all. I have a weighted Graph G={V,E,ETW} where V is the node set, E the edge set and ETW is a set of edge time windows. A edge time window is a 3-Tuple (edge, starttime, endtime) with the meaning that in the intervall [starttime, endtime] the given edge is not available. The problem now is to find a shortest path from a start node to an end node in which it is allowed to wait at the nodes (to use a edge after it´s time window).

Does anybody know a algorithm for this problem? (and in the best case the paper in which the algorithm was published)

Greetings, Christoph

-

## 1 Answer

I believe you can model your problem via a time-dependent graph, which is a graph with the traversal cost for each edge a function of time. You could model your time window by setting the cost to $\infty$ inside your window, making it effectively unavailable, and constant outside. Shortest paths in time-dependent graphs have been studied since 1966 (Cooke and Halsey), and there is a vast literature. Here are a two recent references to get you started:

(1) Demiryurek, Banaei-Kashani, Shahabi, "A Case for Time-Dependent Shortest Path Computation in Spatial Networks." 2010 (ACM link; PDF link)

(2) Ding, Yu, Qin, "Finding time-dependent shortest paths over large graphs." 2008 (ACM link).

-
Something like this was my first ideal also. But these approaches (at least the ones i know) don´t allow waiting at the nodes. Am i wrong here? – Christoph Apr 18 '12 at 14:35
@Christoph: My understanding is that implicitly they do encompass waiting. – Joseph O'Rourke Apr 18 '12 at 14:43