Risk Averse Maximum Expected Covering Location Problem

This paper considers the class of facility location models known as the maximum expected covering location model, in which located facilities are subject to random failures and the objective is to maximize the expected value of served (or covered) locations. We introduce a risk averse version of the problem that focuses on maximizing the conditional expectation of coverage over a specially defined “risk” set of facility failure scenarios. The risk set of failure scenarios is appropriately defined to address the outcomes when large losses of coverage are especially probable. The development of the new model relies on the stationary assumption that every t facilities in any covering set of size k fail with the same probability. In some service providing applications, failure of a facility in a covering set can depend on the size of neighborhood that such facility covers, and hence the above assumption may appear unrealistic. For this reason, we further propose a class of load balanced risk averse maximum expected covering location models that involve a set of parameters that specify the maximum possible load assigned for service to every facility. Thus, the load balanced models not only find the positions to locate facilities, but also make the assignment – which nodes in the neighborhoods of every facility should be considered actually covered. In our computational studies we illustrate the difference between the standard expectation-based optimal covering locations and risk averse ones. At the same time, we demonstrate that risk averse location models allow to handle real-world network instances with over 11,000 nodes using standard MIP solvers within minutes of computer time.