Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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