A reference point approach for the resource constrained shortest path problems

The Resource Constrained Shortest Path Problem (RCSPP) is a variant of the classical shortest path problem and is of great practical importance. The aim is to find the shortest path between a given pair of nodes under additional constraints representing upper bounds on the consumption of resources along the path. In the scientific literature, different approaches have been defined to solve the RCSPP. In this work we propose an innovative interactive method to address the RCSPP, based on a novel search strategy of the criteria space. The performance of the proposed approach is evaluated on the basis of an extensive computational study by considering benchmark instances. A comparison with the state-of-the-art approaches developed for the RCSPP is also carried out. The computational results have shown that the developed solution strategy is competitive with the most efficient strategies known thus far. © 2013 INFORMS.