The Reliable Facility Location Problem: Formulations, Heuristics, and Approximation Algorithms
Zuo-Jun Max Shen, Roger Lezhou Zhan, Jiawei Zhang
INFORMS Journal on Computing · 2011 · Volume 23 · Issue 3
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.
Keywords
reliable facility location problem, uncertainty, heuristics, approximation algorithm
Enable JavaScript for citation tools and additional paper interactions.