Cross-Entropy Method for the Maximal Covering Location Problem

Abstract

[EN] 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-ofthe-art CPLEX 20.1 considering the involved large or massive instances.