2
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Christoph
    Commented Apr 18, 2012 at 14:35
  • $\begingroup$ @Christoph: My understanding is that implicitly they do encompass waiting. $\endgroup$
    – Joseph O'Rourke
    Commented Apr 18, 2012 at 14:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .