Name
Abstract | ||
|---|---|---|
This paper considers a stochastic version of the shortest path problem, namely the Distributionally Robust Stochastic Shortest Path Problem (DRSSPP) on directed graphs. In this model, each arc has a deterministic cost and a random delay. The mean vector and the second-moment matrix of the uncertain data are assumed to be known, but the exact information of the distribution is unknown. A penalty occurs when the given delay constraint is not satisfied. The objective is to minimize the sum of the path cost and the expected path delay penalty. As this problem is NP-hard, we propose new reformulations and approximations using a sequence of semidefinite programming problems which provide tight lower bounds. Finally, numerical tests are conducted to illustrate the tightness of the bounds and the value of the proposed distributionally robust approach. HighlightsWe study new reformulations of distributionally robust shortest path problem.We propose new reformulations and approximations to come up with tight lower bounds.We propose copositive reformulations of the two deterministic formulations.We apply an alternating directions' algorithm to compute upper bounds.We demonstrate the efficiency of the lower bounds in solving large size instances. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.cor.2016.05.002 | Computers & OR |
Keywords | Field | DocType |
Stochastic programming,Shortest path,Distributionally robust optimization,Semidefinite programming | Numerical tests,Mathematical optimization,Shortest path problem,Matrix (mathematics),Directed graph,Constrained Shortest Path First,Uncertain data,Stochastic programming,Mathematics,Semidefinite programming | Journal |
Volume | Issue | ISSN |
74 | C | 0305-0548 |
Citations | PageRank | References |
1 | 0.36 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jianqiang Cheng | 1 | 72 | 9.66 |
| Janny Leung | 2 | 15 | 5.52 |
| Abdel Lisser | 3 | 168 | 29.93 |