Accelerated bender’s decomposition algorithm and hybrid heuristics for multi-period planning of maternal healthcare facilities in India

This work addresses the challenge of improving availability and accessibility of maternal healthcare in India by presenting a multi-period planning problem of hierarchical and successively inclusive healthcare facilities. The problem is formulated as a mixed-integer linear programming model to minimize the overall cost, including the cost of establishing and upgrading the facilities, the cost of allocating/referring the mothers-to-be to the respective facilities and the penalty cost of demotivating the overburdening of the facilities in each time period. To solve the model effectively and efficiently, a Bender’s Decomposition Algorithm (BDA) with several acceleration strategies such as valid inequalities, disaggregated Benders cuts, rolling horizon heuristic and parallelism is developed. A Bender’s type heuristic is also tested by solving the master problem heuristically. Additionally, a Fix-and-Optimize (F&O) heuristic hybridized with Simulated Annealing (SA) enhanced by various search space reduction techniques is developed to obtain good quality solutions in a reasonable time for large instances. It is evident from the results of the computational experiments that the accelerated BDA and Bender type heuristic outperforms Gurobi. The hybrid F&O and SA is observed to be the most computationally efficient approach. A representative scenario in the Indian setting presents further evidence of the model’s applicability.