TY - JOUR
T1 - Maximum probability shortest path problem
AU - Cheng, Jianqiang
AU - Lisser, Abdel
N1 - Funding Information:
This work was supported by the Fondation Mathématiques Jacques Hadamard , PGMO/IROE Grant No. 2012-042H .
Publisher Copyright:
© 2015 Elsevier B.V. All rights reserved.
PY - 2015/9/10
Y1 - 2015/9/10
N2 - The maximum probability shortest path problem involves the constrained shortest path problem in a given graph where the arcs resources are independent normally distributed random variables. We maximize the probability that all resource constraints are jointly satisfied while the path cost does not exceed a given threshold. We use a second-order cone programming approximation for solving the continuous relaxation problem. In order to solve this stochastic combinatorial problem, a branch-and-bound algorithm is proposed, and numerical examples on randomly generated instances are given.
AB - The maximum probability shortest path problem involves the constrained shortest path problem in a given graph where the arcs resources are independent normally distributed random variables. We maximize the probability that all resource constraints are jointly satisfied while the path cost does not exceed a given threshold. We use a second-order cone programming approximation for solving the continuous relaxation problem. In order to solve this stochastic combinatorial problem, a branch-and-bound algorithm is proposed, and numerical examples on randomly generated instances are given.
KW - Branch-and-bound
KW - Resource constrained shortest path
KW - Second-order cone programming
KW - Stochastic programming
UR - http://www.scopus.com/inward/record.url?scp=84930864497&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84930864497&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2014.05.009
DO - 10.1016/j.dam.2014.05.009
M3 - Article
AN - SCOPUS:84930864497
VL - 192
SP - 40
EP - 48
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
SN - 0166-218X
ER -