The p-Next Center Problem: Discrete Location with Backups

In the last years, many researches have dealt with discrete facility location problems where the possibility that some of the located facilities might fail has been taken into account. Such problems are known as reliable facility location problems. Under the assumption of independent facility failures, which is most commonly made, some authors have observed that, with the considered models, located facilities tend to centralize and even co-location has proved to be optimal in some cases. However, in real situations, it is not rare that facility failures are correlated, and they tend to concentrate in geographical regions (for instance, if they are caused by natural disasters or accidents with hazardous materials). In these situations, having a very centralized location pattern can be catastrophic. In this work we present a new discrete location problem, called the p-Next Center Problem (pCP) that aims at identifying system configurations that guarantee small service distances both, when all established facilities work properly and also when one of them fails, without pushing excessively towards centralization. This new problem considers the system from a center perspective and it does not require any knowledge about the facility failure probabilities although, if desired, they can be easily incorporated. As opposite to most reliable location references, it is assumed that customers do not have complete information on the facilities status. That is, they do not know beforehand whether their closest open facility is available or it has failed. Therefore, they travel first to their reference center, and in the case they dont find it operative, they move to the open facility that is closest to it (backup center). The goal of the pCP is to identify a set of p facilities that minimizes the distance associated with the longest path from a customer to its backup center going through its reference center. This talk explores the structure of the optimal solutions to this problem, and analyzes different formulations of the pCP, based on different sets of binary variables. As opposite to the classical p-center problem, in this situation, for a given customer it might be profitable to choose as its reference center a facility that is not the one closest to it. However, since we are assuming that the first choice of a customer is made before knowing whether the reference center is working or not, the reference center of a customer must be among its closest open centers. Therefore, in the proposed formulations we need to guarantee that the primary assignment of any customer is to one of its closest facilities. This requires including closest assignment constraints to any formulation, which has a great impact on the difficulty of solving this problem using standard MIP solvers. This is a joint work with Alfredo Marin, from Universidad de Murcia, and Yolanda Hinojosa and Justo Puerto, form Universidad de Sevilla.