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.
Citation
University of Waterloo, (2015)
Article
View Models and algorithms for the robust resource constrained shortest path problem