The shortest path problem with forbidden paths

The shortest path problem with forbidden paths

0.00 Avg rating0 Votes
Article ID: iaor20061808
Country: Netherlands
Volume: 165
Issue: 1
Start Page Number: 97
End Page Number: 107
Publication Date: Aug 2005
Journal: European Journal of Operational Research
Authors: ,
Abstract:

We consider a variant of the constrained shortest path problem, where the constraints come from a set of forbidden paths (arc sequences) that cannot be part of any feasible solution. Two solution approaches are proposed for this variant. The first uses Aho and Corasick's keyword matching algorithm to filter paths produced by a k-shortest paths algorithm. The second generalizes Martins' deviation path approach for the k-shortest paths problem by merging the original graph with a state graph derived from Aho and Corasick's algorithm. Like Martins' approach, the second method amounts to a polynomial reduction of the shortest path problem with forbidden paths to a classic shortest path problem. Its significant advantage over the first approach is that it allows considering forbidden paths in more general shortest path problems such as the shortest path problem with resource constraints.

Reviews

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