Shortest path problem with forbidden paths: The elementary version

Shortest path problem with forbidden paths: The elementary version

0.00 Avg rating0 Votes
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: ,
Keywords: graphs, programming: branch and bound, programming: dynamic
Abstract:

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.

Reviews

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