Facility networks can be disrupted by, for example, power outages, poor weather conditions, or natural disasters, and the probabilities of these events may be difficult to estimate. This could lead to costly recourse decisions since the customers cannot be served by the planned facilities. In this paper, we study a fixed-charge location problem (FLP) that considers the risk of disruptions. We adopt a two-stage robust optimization method, where facility location decisions are made here-and-now and recourse decisions to reassign customers are made after the uncertainty information on the facility availability has been revealed. We implement a column-and-constraint generation (C&CG) algorithm to solve the robust models exactly. Instead of relying on dualization or reformulation techniques to deal with the subproblem, as is common in the literature, we use an exact enumeration method that allows us to take into account a discrete uncertainty set of facility failures. We also develop an approximation scheme for instances of a realistic size; it requires the adjustable decisions to be an affine function of the uncertain parameters. Numerical experiments show that the proposed C&CG algorithm outperforms existing methods for both the robust FLP and the robust
\(p\)-median problem. We also introduce an enhancement to the formulation that allows the decision-maker to control the trade-off between the nominal cost increase and the robustness of the solution.
Published October 2018 , 32 pages