An enhanced benders decomposition method and a matheuristic algorithm for solving the stochastic capacitated facility location problem with shortages Academic Article in Scopus uri icon

abstract

  • The Capacitated Facility Location Problem (CFLP) is a well-known combinatorial optimization problem extensively studied in the field of location sciences. It has numerous applications in industrial engineering, humanitarian logistics, telecommunication networks, and other domains. Incorporating uncertainties in demands, stochastic programming emerges as a suitable approach to address this problem. Therefore, due to the inherent stochasticity, not all customers demand may be satisfied. To address this issue, we incorporate the concept of shortages into the CFLP. As a result, the CFLP with shortages and normally distributed demands is proposed, where the cost of losing a customer is considered as a penalty cost in the objective function. To address the problem, we propose three exact methods and a matheuristic algorithm. The exact methods are grounded in Benders decomposition: a straightforward implementation, a refined version adding a set of valid inequalities, and an enhanced approach based on Branch-and-Cut. The matheuristic algorithm follows a Fixing-First scheme based on pricing strategies, efficiently solving the problem within a reasonable computational time. The effectiveness of the proposed algorithms is evaluated by comparing it against a deterministic equivalent solution given by the general-purpose solver Gurobi. Computational experiments are conducted on a set of challenging instances using a sample average approximation scheme. To validate the applicability of the problem under study, a real case study involving Mobile Health Clinics (MHCs) located in Mexico was analyzed. Interesting managerial insights were obtained, highlighting the importance of having at least 271 MHCs to achieve the objectives that the government has set for medical coverage of acute respiratory infections for socially vulnerable people through its healthcare programs. © 2024 Elsevier Ltd

publication date

  • December 1, 2024