TY - JOUR
T1 - New reformulations of distributionally robust shortest path problem
AU - Cheng, Jianqiang
AU - Leung, Janny
AU - Lisser, Abdel
N1 - Funding Information:
This research benefited from the support of the FMJH Program Gaspard Monge in optimization and operation research , and from the support to this program from EDF. PGMO/IROE Grant no. 2012-042H .
Publisher Copyright:
© 2016 Elsevier Ltd. All rights reserved.
PY - 2016/10/1
Y1 - 2016/10/1
N2 - 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.
AB - 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.
KW - Distributionally robust optimization
KW - Semidefinite programming
KW - Shortest path
KW - Stochastic programming
UR - http://www.scopus.com/inward/record.url?scp=84969257722&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84969257722&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2016.05.002
DO - 10.1016/j.cor.2016.05.002
M3 - Article
AN - SCOPUS:84969257722
SN - 0305-0548
VL - 74
SP - 196
EP - 204
JO - Computers and Operations Research
JF - Computers and Operations Research
ER -