The Reliable Facility Location Problem: Formulations, Heuristics, and Approximation Algorithms

We study a reliable facility location problem wherein some facilities are subject to failure from time to time. If a facility fails, customers originally assigned to it have to be reassigned to other (operational) facilities. We formulate this problem as a two‐stage stochastic program and then as a nonlinear integer program. Several heuristics that can produce near‐optimal solutions are proposed for this NP‐hard problem. For the special case where the probability that a facility fails is a constant (independent of the facility), we provide an approximation algorithm with a worst‐case bound of 4. The effectiveness of our heuristics is tested by extensive computational studies, which also lead to some managerial insights.