Publisher： John Wiley & Sons Inc
E-ISSN： 1467-8667|30|6|433-448
ISSN： 1093-9687
Source： COMPUTER-AIDED CIVIL AND INFRASTRUCTURE ENGINEERING, Vol.30, Iss.6, 2015-06, pp. : 433-448
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
AbstractThis article employs a robust optimization approach for the shortest path problem where travel cost is uncertain and exact information on the distribution function is unavailable. We show that under such conditions the robust shortest path problem can be formulated as a binary nonlinear integer program, which can then be reformulated as a mixed integer conic quadratic program. Based on this reformulation, we present an outer approximation algorithm as a solution algorithm which is shown to be highly efficient for this class of programs. Numerical experiments conducted on small to large networks further compare the robust optimization‐based strategy to the classical deterministic shortest path in terms of the uncertainty in the network.
Related content
Access to resources
Recommend
Robust constrained shortest path problems under budgeted uncertainty
NETWORKS: AN INTERNATIONAL JOURNAL, Vol. 66, Iss. 2, 2015-09 ,pp. :
A shortest path problem on a network with fuzzy arc lengths
Fuzzy Sets and Systems, Vol. 109, Iss. 1, 2000-01 ,pp. :
An Incremental Algorithm for a Generalization of the Shortest-Path Problem
Journal of Algorithms, Vol. 21, Iss. 2, 1996-09 ,pp. :