<p>Unfortunately I am not aware of any complete and sound algorithm for solving this task. As far as I am aware, most techniques consist of Stochastic Local Search algorithms.</p>

<p>TSPTW (Traveling Salesman Problem with Time Windows) is a good example of your problem. For the particular case where constraints are not hard so that they result in a penalty, the best results have been derived with Ant Colony Optimization [1]. Another algorithm known as the Nested Rollout Policy Adaptation [2] has been used as well. Finally, Monte-carlo has been tried (I cite [3] but there are surely a number of references in this regard)</p>

<p>Hope this helps,</p>

<p><strong>Bibliography</strong></p>

<p>[1] Manuel López Ibáñez and Christian Blum, "Beam-ACO for the tranveling salesman problem with time windows", Computers &amp; OR 37 (9), 1570--1583 (2010)</p>

<p>[2] T. Cazenave and F. Teytaud, "Application of the nested rollout policy adaptation algorithm to the traveling salesman problem with time windows", LION 6, Springer (2012)</p>

<p>[3] A. Rimmel, F. Teytaud, and T. Cazenave, "Optimization of the nested monte-carlo algorithm on the Traveling salesman problem with time windows", Applications of Evolutionary Computation, 501--510 (2011)</p>

CC BY-SA 3.0
2012-04-20T07:26:47.817Z
2012-04-20T07:26:47.817Z
Carlos Linares López
<p>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).</p>

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

<p>Greetings, Christoph</p>

CC BY-SA 3.0
2012-04-19T14:44:03.197Z
i don't get the waiting at the nodes part
Sasho Nikolov
CC BY-SA 3.0
2012-04-19T16:19:02.683Z
Is there any cost in waiting at a node?
kunigami
CC BY-SA 3.0
2012-04-19T18:27:51.970Z
Have you seen the paper: [Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length](http://students.csci.unt.edu/~kea0043/References/PaperThree.pdf) by A.Orda and R.Rom (1989)?
Marzio De Biasi
CC BY-SA 3.0
2012-04-20T07:41:47.113Z
You need to wait at a node in order to use an edge (when it reactivates)
Suresh Venkat
CC BY-SA 3.0
2012-04-20T09:08:58.640Z
Using the time-space network, you can solve the problem with Dijkstra's algorithm.  If you don't know the time-space network, you should investigate it (and the question might not be research-level).  If you know it but you cannot use it for some reason, you should clarify your problem.
Snowie
<ds.algorithms><graph-theory><graph-algorithms><shortest-path>
Do you know a shortest path algorithm for weighted graphs with hard time windows on the edges and waiting allowed?
Christoph
# Do you know a shortest path algorithm for weighted graphs with hard time windows on the edges and waiting allowed?

(Asked by: username_0 on 2012-04-19)

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

**Tags:** ds.algorithms, graph-theory, graph-algorithms, shortest-path
> **Comments:**
> **username_1**: i don't get the waiting at the nodes part  
> **username_2**: Is there any cost in waiting at a node?  
> **username_3**: Have you seen the paper: [Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length](http://students.csci.unt.edu/~kea0043/References/PaperThree.pdf) by A.Orda and R.Rom (1989)?  
> **username_4**: You need to wait at a node in order to use an edge (when it reactivates)  
> **username_5**: Using the time-space network, you can solve the problem with Dijkstra's algorithm.  If you don't know the time-space network, you should investigate it (and the question might not be research-level).  If you know it but you cannot use it for some reason, you should clarify your problem.  

---

## 1 answers

### Answer by username_6 on 2012-04-20. Score: 2

Unfortunately I am not aware of any complete and sound algorithm for solving this task. As far as I am aware, most techniques consist of Stochastic Local Search algorithms.

TSPTW (Traveling Salesman Problem with Time Windows) is a good example of your problem. For the particular case where constraints are not hard so that they result in a penalty, the best results have been derived with Ant Colony Optimization [1]. Another algorithm known as the Nested Rollout Policy Adaptation [2] has been used as well. Finally, Monte-carlo has been tried (I cite [3] but there are surely a number of references in this regard)

Hope this helps,

**Bibliography**

[1] Manuel López Ibáñez and Christian Blum, "Beam-ACO for the tranveling salesman problem with time windows", Computers & OR 37 (9), 1570--1583 (2010)

[2] T. Cazenave and F. Teytaud, "Application of the nested rollout policy adaptation algorithm to the traveling salesman problem with time windows", LION 6, Springer (2012)

[3] A. Rimmel, F. Teytaud, and T. Cazenave, "Optimization of the nested monte-carlo algorithm on the Traveling salesman problem with time windows", Applications of Evolutionary Computation, 501--510 (2011)


---

