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

SN - 0166-218X

VL - 192

SP - 40

EP - 48

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -