Anything new in the classical Maximal Covering Location Problem?
H. Wang, J. Zhou
The maximal covering location problem (MCLP) involves identifying optimal locations to maximize the covered demand with constraints with the number of facilities or budget limitations. We introduce 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 where a Pareto order sampling and 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 to 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 considering the involved large or massive instances.
Keywords: maximal covering location problem, cross-entropy method, metaheuristic, Pareto sampling
Scheduled
Methods and Applications of OR II
September 5, 2026 10:00 AM
Aula 24
Other papers in the same session
R. de Andres Calle, J. M. Cascón, S. Prieto-Herraez
M. Moreno-Faguett, J. Castillo-Mandujano, J. Salgado-Rojas, V. Hermoso, M. J. Martínez-Harms, B. Larraín-Barrios, E. Álvarez-Miranda