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

$\endgroup$
5
  • $\begingroup$ i don't get the waiting at the nodes part $\endgroup$ Apr 19 '12 at 14:44
  • $\begingroup$ Is there any cost in waiting at a node? $\endgroup$
    – kunigami
    Apr 19 '12 at 16:19
  • 2
    $\begingroup$ Have you seen the paper: Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length by A.Orda and R.Rom (1989)? $\endgroup$ Apr 19 '12 at 18:27
  • $\begingroup$ You need to wait at a node in order to use an edge (when it reactivates) $\endgroup$ Apr 20 '12 at 7:41
  • $\begingroup$ 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. $\endgroup$
    – Snowie
    Apr 20 '12 at 9:08
2
$\begingroup$

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)

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

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