Robust Shortest Path Problems with Two Uncertain Multiplicative Cost Coefficients
Changhyun Kwon (chkwonbuffalo.edu)
Abstract: We consider a robust shortest path problem when the cost coefficient is the product of two uncertain factors. We first show that the robust problem can be solved in polynomial time by a dual variable enumeration with shortest path problems as subproblems. We also propose a path enumeration approach using a $K$-shortest paths finding algorithm that may be efficient in many real cases. An application in hazardous materials transportation is discussed and the solution methods are illustrated by numerical examples.
Keywords: robust shortest path; budgeted uncertainty; hazardous materials transportation
Category 1: Robust Optimization
Category 2: Applications -- OR and Management Sciences (Transportation )
Category 3: Network Optimization
Citation: http://dx.doi.org/10.1002/nav.21540 accepted in Naval Research Logistics.
Entry Submitted: 04/25/2013
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|