An integer L-shaped algorithm for the integrated location and network restoration problem in disaster relief

You are here: Homepage > Search

An integer L-shaped algorithm for the integrated location and network restoration problem in disaster relief

Sanci, Ece / Daskin, Mark S.

Highlights • We develop a methodology for the integrated location and network restoration model. • This model is a two-stage stochastic program with integer recourse. • We propose an exact algorithm based on the integer L-shaped method. • This algorithm accommodates the binary decision variables in the second stage. • The solution time increases only linearly as the number of scenarios increases.

Abstract Being prepared for potential disaster scenarios enables government agencies and humanitarian organizations to respond effectively once the disaster hits. In the literature, two-stage stochastic programming models are commonly employed to develop preparedness plans before anticipated disasters. These models can be very difficult to solve as the complexity increases with several sources of uncertainty and interdependent decisions. In this study, we propose an integer L-shaped algorithm to solve the integrated location and network restoration model, which is a two-stage stochastic programming model determining the number and locations of the emergency response facilities and restoration resources under uncertainty. Our algorithm accommodates the second-stage binary decision variables which are required to indicate undamaged and restored roads of the network that can be used for relief distribution. Our computational results show that our algorithm outperforms CPLEX for the larger number of disaster scenarios as the solution time of our algorithm increases only linearly as the number of scenarios increases.