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: | Sforza Antonio, Avella Pasquale, Boccia Maurizio |
Keywords: | heuristics |
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.