Question

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

Answer 1

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).