Investing in the Links of a Stochastic Network to Minimize Expected Shortest Path. Length

We consider a network whose links are subject to independent, random failures due to a disruptive event. The survival probability of a link is increased, if it is strengthened by investment. A given budget is to be allocated among the links with the objective of optimizing the post-event performances of the network. Specifically, we seek to minimize the expected shortest path Length between a specified origin node and destination node in the network. This criterion is defined through the use of a fixed penalty cost for those network realizations in the expectation, that do not have a path connecting the origin node to the destination node. This problem type arises in the pre-disasters, by upgrading its weakest elements. We model the problem as a two-stage stochastic program in which the underlying probability distribution of the random variables is dependent on the first stage decision variables. Using a path-based approach we construct its equivalent deterministic program and derive structural results for the objective function. We then propose an approximate solution procedure based on a first order approximation the objective function. The procedure is tested by numerical experiments on a small-size network. The test results show that it yields very good performance on the instances solved.