Cross-Entropy Method for the Maximal Covering Location Problem

The maximal covering location problem (MCLP) involves identifying optimal locations to maximize the covered demand with constraints from the number of facilities or budget limitations. This paper introduces a new MCLP formulation and a metaheuristic, the cross-entropy method, to solve the problem. The method refers to a sampling-based solution construction from statistically tractable distribution models with iterative updates via inclusion probabilities in which a Pareto order sampling and a new local search are introduced. Extensive experiments are carried out on, to our knowledge, the most complete eight benchmark data of three network types and two MCLP settings with 100–100,000 demand nodes. It demonstrates that (i) the proposed model is more compact with the number of variables and constraints, and (ii) the cross-entropy method is highly effective in finding optimal solutions and competitive with other proposals and state-of-the-art CPLEX 20.1 considering the involved large or massive instances. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This work was supported by the China Scholarship Council [Grant 202006890026] and the National Natural Science Foundation of China [Grant 71872110]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0611 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0611 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .