Benders decomposition for capacitated multi-period maximal covering location problem with server uncertainty

Abstract

Primary Health Centers (PHCs), which are single doctor clinics and vital to health care in rural areas of developing countries, often remain inoperative due to shortage of doctors. When doctors become available, the health administrator needs to decide that which of the inoperative PHCs should the doctor be assigned. For transparency and operational efficiency, the sequence in which the inoperative PHCs will be assigned doctors needs to be decided in advance at the start of the planning horizon. Further, the number of doctors that will become available in each period of the planning horizon is uncertain. Moreover, the health guidelines set the capacity target, i.e. the maximum population a PHC can provide service to. We introduce and study the capacitated multi period maximal covering facility location problem under server uncertainty. We provide a formulation for the problem based on the minimax regret approach. Further, we solve the problem using CPLEX MIP solver and observe that it can only solve very small instances. Hence, we provide Benders decomposition based solution methods and refinements thereof, which is 100 − 5000 times faster and could solve practical size instances in reasonable time.