Article ID: | iaor20131646 |
Volume: | 227 |
Issue: | 2 |
Start Page Number: | 254 |
End Page Number: | 267 |
Publication Date: | Jun 2013 |
Journal: | European Journal of Operational Research |
Authors: | Guerriero Francesca, Di Puglia Pugliese Luigi |
Keywords: | graphs, programming: branch and bound, programming: dynamic |
This paper addresses the elementary shortest path problem with forbidden paths. The main aim is to find the shortest paths from a single origin node to every other node of a directed graph, such that the solution does not contain any path belonging to a given set (i.e., the forbidden set). It is imposed that no cycle can be included in the solution. The problem at hand is formulated as a particular instance of the shortest path problem with resource constraints and two different solution approaches are defined and implemented. One is a Branch & Bound based algorithm, the other is a dynamic programming approach. Different versions of the proposed solution strategies are developed and tested on a large set of test problems.