Maximum probability shortest path problem

Jianqiang Cheng; Abdel Lisser

doi:10.1016/j.dam.2014.05.009

Maximum probability shortest path problem

Jianqiang Cheng, Abdel Lisser

Research output: Contribution to journal › Article › peer-review

17 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	40-48
Number of pages	9
Journal	Discrete Applied Mathematics
Volume	192
DOIs	https://doi.org/10.1016/j.dam.2014.05.009
State	Published - Sep 10 2015
Externally published	Yes

Keywords

Branch-and-bound
Resource constrained shortest path
Second-order cone programming
Stochastic programming

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2014.05.009

Cite this

@article{ffa7c7df7c844f91b6626e66d4175689,

title = "Maximum probability shortest path problem",

abstract = "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.",

keywords = "Branch-and-bound, Resource constrained shortest path, Second-order cone programming, Stochastic programming",

author = "Jianqiang Cheng and Abdel Lisser",

year = "2015",

month = sep,

day = "10",

doi = "10.1016/j.dam.2014.05.009",

language = "English (US)",

volume = "192",

pages = "40--48",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Maximum probability shortest path problem

AU - Cheng, Jianqiang

AU - Lisser, Abdel

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 -

Maximum probability shortest path problem

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this