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 -