Multi-Period Facility Location Problem With an Uncertain Number of Servers

Abstract

Facility location problems reported in the literature generally assume the problem parameter values (like cost, budget, etc.) to be known with complete certainty, even if they change over time (as in multi-period versions). However, in reality, there may be some uncertainty about the exact values of these parameters. Specifically, in the context of locating primary health centers (PHCs) in developing countries, there is generally a high level of uncertainty in the availability of servers (doctors) joining the facilities in different time periods. Furthermore, for transparency and efficient assignment of the doctors to PHCs, it is desirable to decide the facility opening sequence (assigning doctors to unmanned PHCs) at the start of the planning horizon.

The extant facility location literature does not account for such an uncertainty regarding server availability. This uncertainty may lead to a facility opening sequence being considered, which may be far from an optimal ex post decision. We work on the uncapacitated and capacitated versions of this problem where facilities can only meet demand which falls within a covering distance. Further, in place of a crisp covering distance, we generalize the problems by considering a gradual covering where coverage function is a non-increasing function of distance. We provide two formulations for each of these versions using minimax regret approach and show that one of the formulations is stronger.

We provide Benders' decomposition based solution method, along with several refinements for each of the problem variants. For instances that CPLEX MIP solver could solve within a time limit of 20 hours, our proposed solution methods turns out to be of the order of 100 - 5000 times faster. To solve larger size problem instances, we also provide tabu search (TS) implementations that gives good solution for most of the test instances.