VNS-based Solution Approaches to the Maximal Covering Location Problem with Customer Preference Order

Abstract

This study considers Maximal Covering Location Problem with Customer Preference Ordering. The goal of the problem is to find optimal locations for establishing p facilities and optimal allocations of customers to facilities that are located within given coverage radius, such that the demand of customers is maximized. It is assumed that a set of facilities belonging to other firms are already present at the market and that customers are free to choose facilities based on their preferences. As the considered problem is NP-hard, metaheuristic approaches are required to solve problem instances of large dimensions. In this study, two meteheuristic metods are proposed: Variable Neighborhood Search (VNS) and a hybridization of Reduced Variable Neighborhood Search (RVNS), Tabu Search (TS) and VNS, denoted as RVNS-TS-VNS. The performance of VNS and RVNS-TS-VNS is evaluated on the set of 60 test instances and compared with the existing solution approach from the literature. The obtained computational results show the potential of both proposed VNS and RVNS-TS-VNS approaches when solving the considered variant of MCLP