| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 421098 | Discrete Applied Mathematics | 2015 | 9 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jianqiang Cheng, Abdel Lisser,