Groupe d’études et de recherche en analyse des décisions


The Shortest Path Problem with Forbidden Paths


We consider a new variant of 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 solution method amounts to polynomially reduce the shortest path problem with forbidden paths to a classic shortest path problem. Its significant advantage over the first approach is that it allows for applications of forbidden paths based on more general shortest path problems such as the shortest path problem with resource constraints.

, 26 pages