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
2016
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01342548
Contributeur : Michael Poss <>
Soumis le : mercredi 6 juillet 2016 - 12:06:07
Dernière modification le : mercredi 28 novembre 2018 - 10:54:08

Fichier

Paper-DP-RCSP.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01342548, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

323

Téléchargements de fichiers

108