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

Zuo‐Jun Max Shen, Roger Lezhou Zhan, Jiawei Zhang

INFORMS journal on computing · 2010 · 233 citations · 23 references

Concepts

TL;DR

We study a reliable facility location problem where facilities may fail, requiring customers to be reassigned to operational facilities. The study proposes several heuristics to obtain near‑optimal solutions for this NP‑hard reliable facility location problem. The authors formulate the problem as a two‑stage stochastic program and a nonlinear integer program, and for the constant‑failure‑probability case provide a 4‑approximation algorithm. Extensive computational studies confirm the effectiveness of the heuristics and yield managerial insights.

Abstract

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.

References

23