  


Models and algorithms for the robust resource constrained shortest path problem
Da Lu(d4luuwaterloo.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 labelsetting algorithm that introduces a new dominance rule. We perform extensive numerical testing to compare the modified labelsetting algorithm with direct solution of an equivalent deterministic mixedinteger programming model, a sequential algorithm that solves a series of deterministic RCSPP, and a labelsetting algorithm proposed by Pessoa et. al. 2015. The labelsetting algorithm is comparable to the labelsetting algorithm by Pessoa et. al. 2015 and outperforms all other approaches significantly. Keywords: robust resource constrained shortest path, robust optimization, graph reduction, labelsetting 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  