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.

Palabras clave: maximal covering location problem, cross-entropy method, metaheuristic, Pareto sampling

Métodos y Aplicaciones de la IO II
5 de septiembre de 2026  10:00
Aula 24

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

J. C. Yepes Borrero, W. Guerrero