Shortest path problem with forbidden paths: The elementary version |
| |
Authors: | Luigi Di Puglia Pugliese Francesca Guerriero |
| |
Institution: | Department of Mechanical, Energy and Management Engineering, University of Calabria, 87036 Rende, CS, Italy |
| |
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. |
| |
Keywords: | Combinatorial optimization Shortest paths Forbidden paths Branch and bound approach Dynamic programming approach |
本文献已被 ScienceDirect 等数据库收录! |