TY - GEN
T1 - Stochastic shortest path problem with uncertain delays
AU - Cheng, Jianqiang
AU - Kosuch, Stefanie
AU - Lisser, Abdel
PY - 2012
Y1 - 2012
N2 - This paper considers a stochastic version of the shortest path problem, the Stochastic Shortest Path Problem with Delay Excess Penalty on directed, acyclic graphs. In this model, the arc costs are deterministic, while each arc has a random delay, assumed normally distributed. 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. In order to solve the model, a Stochastic Projected Gradient method within a branch-and-bound framework is proposed and numerical examples are given to illustrate its effectiveness. We also show that, within given assumptions, the Stochastic Shortest Path Problem with Delay Excess Penalty can be reduced to the classic shortest path problem.
AB - This paper considers a stochastic version of the shortest path problem, the Stochastic Shortest Path Problem with Delay Excess Penalty on directed, acyclic graphs. In this model, the arc costs are deterministic, while each arc has a random delay, assumed normally distributed. 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. In order to solve the model, a Stochastic Projected Gradient method within a branch-and-bound framework is proposed and numerical examples are given to illustrate its effectiveness. We also show that, within given assumptions, the Stochastic Shortest Path Problem with Delay Excess Penalty can be reduced to the classic shortest path problem.
KW - Active set methods
KW - Branch-and-bound
KW - Projected gradient algorithm
KW - Shortest path
KW - Stochastic programming
UR - http://www.scopus.com/inward/record.url?scp=84861986584&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84861986584&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84861986584
SN - 9789898425973
T3 - ICORES 2012 - Proceedings of the 1st International Conference on Operations Research and Enterprise Systems
SP - 256
EP - 264
BT - ICORES 2012 - Proceedings of the 1st International Conference on Operations Research and Enterprise Systems
T2 - 1st International Conference on Operations Research and Enterprise Systems, ICORES 2012
Y2 - 4 February 2012 through 6 February 2012
ER -