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$
  • $\begingroup$ i don't get the waiting at the nodes part $\endgroup$ – Sasho Nikolov 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$ – Marzio De Biasi Apr 19 '12 at 18:27
  • $\begingroup$ You need to wait at a node in order to use an edge (when it reactivates) $\endgroup$ – Suresh Venkat 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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