Large Neighborhood Search for the Capacitated P-Median Problem

Abstract

As a location-allocation problem, the goal of the p-median problem is to find the optimal selection of p medians that results in the minimum total distance from these medians to their assigned objects. The capacitated p-median problem (CPMP) is a version of the p-median problem that sets maximum values for the capacities of the medians in order to fulfill the demand arising from these objects. Considering the numerous application cases of the CPMP, in this paper we present a large neighborhood search (LNS) algorithm for solving it. We propose and analyze various destruction operators within the framework of LNS to efficiently explore diverse neighborhoods. A MIP solver is used in the repair phase. We evaluated LNS across different data sets available in the literature and show that this method provides a lower average GAP value for instances up to 5000 facilities. Additionally, our LNS algorithm found new best solutions for seven evaluated instances.