A Multi-objective variable neighborhood search for the maximal covering location problem with customer preferences

Abstract

This paper considers a variant of maximal covering location problem with customer preferences and two objectives involved: maximization of the weighted sum of the covered demand and minimization of the number of uncovered customers. The problem has important applications in service network design, such as telecommunication and computer networks, service placement problem, etc. This paper proposes a multi-objective variable neighborhood search (MO-VNS) as a metaheuristic approach for the considered problem. Following the concepts of basic, reduced, and general VNS in single-objective optimization, three MO-VNS variants are proposed: MO-BVNS, MO-RVNS, and MO-GVNS. The proposed MO-VNS implementations were compared with each other and with the existing multi-objective evolutionary algorithms (MOEAs). The MO-VNS concept showed to be superior over MOEA, as all MO-VNS variants outperform MOEAs in the sense of solution quality, especially on the largest size test instances.