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 (PFH) 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.

An exponential penalty function heuristic for the Resource Constrained Shortest Path Problem

AVELLA P;
2002-01-01

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 (PFH) 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.
File in questo prodotto:
File Dimensione Formato  
EJOR_2002.pdf

non disponibili

Licenza: Non specificato
Dimensione 120.75 kB
Formato Adobe PDF
120.75 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12070/1235
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 20
  • ???jsp.display-item.citation.isi??? ND
social impact