A polynomial-time algorithm to find shortest paths with recourse

A polynomial-time algorithm to find shortest paths with recourse

0.00 Avg rating0 Votes
Article ID: iaor20032481
Country: United States
Volume: 41
Issue: 2
Start Page Number: 115
End Page Number: 125
Publication Date: Feb 2003
Journal: Networks
Authors:
Abstract:

The Shortest Path with Recourse Problem involves finding the shortest expected-length paths in a directed network, each of whose arcs have stochastic traversal lengths (or delays) that become known only upon arrival at the tail of that arc. The traveler starts at a given source node and makes routing decisions at each node in such a way that the expected distance to a given sink node is minimized. We develop an extension of Dijkstra's algorithm to solve the version of the problem where arclengths are nonnegative and reset after each arc traversal. All known no-reset versions of the problem are NP-hard. We make a partial extension to the case where negative arclengths are present.

Reviews

Required fields are marked *. Your email address will not be published.