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

Improve this question
$\endgroup$
5
  • $\begingroup$ i don't get the waiting at the nodes part $\endgroup$
    – Sasho Nikolov
    Commented Apr 19, 2012 at 14:44
  • $\begingroup$ Is there any cost in waiting at a node? $\endgroup$
    – kunigami
    Commented Apr 19, 2012 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
    Commented Apr 19, 2012 at 18:27
  • $\begingroup$ You need to wait at a node in order to use an edge (when it reactivates) $\endgroup$
    – Suresh Venkat
    Commented Apr 20, 2012 at 7:41
  • 1
    $\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
    Commented Apr 20, 2012 at 9:08

1 Answer 1

Reset to default
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)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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