Bounds and Preprocessing for the Robust Resource Constrained Shortest Path Problem

Abstract : We address a robust version of the Resource Constrained Shortest Path Problem (RCSP P). We assume that the resource consumptions are uncertain and may take any value in the budgeted uncertainty set defined by Bertismas and Sim (2003,2004). We solve the problem to optimality through a dynamic programming approach well-tailored for the robust RCSP P , which adopts state-of-the-art resolution techniques for the deterministic counterpart. In particular, we formulate the robust Lagrangian relaxation and solve the corresponding dual problem. Upper and lower bounds information are used to fathom unpromising states. In addition, nodes and arcs removing procedures are defined by using robust resource consumption associated with forward and backward paths. The proposed dynamic programming is tested on instances inspired by the scientific literature for the RCSP P .
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
Contributeur : Michael Poss <>
Soumis le : mercredi 6 juillet 2016 - 12:06:07
Dernière modification le : jeudi 11 janvier 2018 - 06:26:15


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01342548, version 1



Luigi Di Puglia Pugliese, Francesca Guerriero, Michael Poss. Bounds and Preprocessing for the Robust Resource Constrained Shortest Path Problem. 2016. 〈hal-01342548〉



Consultations de la notice


Téléchargements de fichiers