Multiperiod reliable uncapacitated facility location problem

Abstract

Facility location problem is a class of combinatorial optimization problems that has been extensively studied in the literature. Different variants of facility location problems have been used to model a wide variety of problems ranging from location of servers in communication networks to warehouses in a supply chain network to location of emergency services such as ambulances in public service systems. While the conventional models have been successful in providing solution to many real life location problems, these models make the assumption that facilities, once located, remain functional forever. This assumption is far from reality as facilities at times become non-functional (or fail) due to a variety of reasons including natural calamities, union strikes, terrorist attacks etc. The effects of such failures have become more pronounced due to the increased dependence on facilities because of adoption of lean paradigm. Therefore, researchers have proposed reliable facility location models, which incorporate the failure prone nature of the facilities. However, the RUFLP models studied in the literature can be classified as Single Period RUFLP, as these models make two implicit assumptions. First, they assume that a facility, if failed, remains failed through out the rest of the horizon, and similarly, a facility, if functional, remains functional through out. Second, they also assume that all the facility failures are realized simultaneously. Both of these assumptions are rather restrictive and do not hold true for many real life situations. Therefore, in this paper, we introduce the Multiperiod Reliable Uncapacitated Facility Location Problem (MRUFLP) that relaxes these assumptions by accounting for facility recovery after a failure, and allowing the facility failures to realize at different times in the planning horizon. More specifically, we present a two stage stochastic programming formulation, an extensive formulation and a non-linear integer programming formulation for the MRUFLP. We present a constant factor approximation algorithm for the problem and also present a fast heuristic to solve real life instances of the problem. © IEOM Society International.