Shortest path problems with time windows on nodes and arcs (Q1340512)

The author models shortest path problems, where the arrival and stop on nodes is restricted to certain intervals (time windows) as well as travelling along arcs, too. A simple generalization of Bellman-Ford's shortest path formulation yields a recurrence equation, which can be solved by dynamic programming techniques even in the case of undirected networks. More interestingly is the problem where there are given two measures \(c\) (cost) and \(t\) (duration) for each arc and one has to find a minimum cost path obeying certain time-window restrictions on nodes and arcs additionally. A dynamic programming algorithm can solve the recurrence equation under these time constraints too. Experimental results and complexity analysis are missing.