Robust Shortest Path Problems with Two Uncertain Multiplicative Cost Coefficients

Authors

Changhyun Kwon, University at BuffaloFollow
Taehan Lee, Chonbuk National University
Paul G. Berglund, Norfolk Southern Corporation

Document Type

Article

Publication Date

8-2013

Keywords

robust shortest path, budgeted uncertainty, hazardous materials transportation

Digital Object Identifier (DOI)

https://doi.org/10.1002/nav.21540

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.

Was this content written or created while at USF?

No

Citation / Publisher Attribution

Naval Research Logistics, v. 60, issue 5, p. 375-394

Scholar Commons Citation

Kwon, Changhyun; Lee, Taehan; and Berglund, Paul G., "Robust Shortest Path Problems with Two Uncertain Multiplicative Cost Coefficients" (2013). Industrial and Management Systems Engineering Faculty Publications. 28.
https://digitalcommons.usf.edu/egs_facpub/28