A penalty function heuristic for the resource constrained shortest path problem

A penalty function heuristic for the resource constrained shortest path problem

0.00 Avg rating0 Votes
Article ID: iaor20032041
Country: Netherlands
Volume: 142
Issue: 2
Start Page Number: 221
End Page Number: 230
Publication Date: Oct 2002
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics
Abstract:

The resource constrained shortest path problem (RCSP) consists of finding the shortest path between two nodes of an assigned network, with the constraint that traversing an arc of the network implies the consumption of certain limited resources. In this paper we propose a new heuristic for the solution of the RCSP problem in medium and large scale networks. It is based on the extension to the discrete case of the penalty function heuristic approach for the fast ϵ-approximate solution of difficult large-scale continuous linear programming problems. Computational experience on test instances has shown that the proposed penalty function heuristic is very effective in the solution of medium and large scale RCSP instances. For all the tests reported it provides very good upper bounds (in many cases the optimal solution) in less than 26 iterations, where each iteration requires only the computation of a shortest path.

Reviews

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