Optimization Online


Models and algorithms for the robust resource constrained shortest path problem

Da Lu(d4lu***at***uwaterloo.ca)
Fatma Gzara(fgzara***at***uwaterloo.ca)

Abstract: We study the robust resource constrained shortest path problem (RCSPP) under uncertainty in cost and multiple resource consumption. Contrary to the deterministic RCSPP where the cost and the consumption of resources on an arc are known and fixed, the robust RCSPP models the case where both the cost and the resource consumption are random, and it determines a robust minimum cost path that is feasible with respect to multiple resource constraints. We present a robust optimization model, propose graph reduction techniques tailored for the robust problem, and develop a modified label-setting algorithm that introduces a new dominance rule. We perform extensive numerical testing to compare the modified label-setting algorithm with direct solution of an equivalent deterministic mixed-integer programming model, a sequential algorithm that solves a series of deterministic RCSPP, and a label-setting algorithm proposed by Pessoa et. al. 2015. The label-setting algorithm is comparable to the label-setting algorithm by Pessoa et. al. 2015 and outperforms all other approaches significantly.

Keywords: robust resource constrained shortest path, robust optimization, graph reduction, label-setting

Category 1: Robust Optimization

Category 2: Applications -- OR and Management Sciences (Transportation )

Category 3: Network Optimization

Citation: University of Waterloo, (2015)

Download: [PDF]

Entry Submitted: 03/09/2018
Entry Accepted: 03/09/2018
Entry Last Modified: 03/09/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society