Maximum probability shortest path problem

Jianqiang Cheng, Abdel Lisser

Research output: Contribution to journalArticlepeer-review

16 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 languageEnglish (US)
Pages (from-to)40-48
Number of pages9
JournalDiscrete Applied Mathematics
Volume192
DOIs
StatePublished - Sep 10 2015
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Maximum probability shortest path problem'. Together they form a unique fingerprint.

Cite this