General Variable Neighborhood Search for Maximum Diversity Problem with Capacity and Budget Constraints

Abstract

We consider a resource allocation problem, referred to as the Maximum Diversity Problem with Capacity and Budget Constraints. It involves establishing some facilities in such a way that the distance between the two closest established facilities is maximized. The number of facilities to be established is not predefined. We developed a General Variable Neighborhood Search (GVNS) approach that uses a combinatorial formulation of the considered problem. Three types of neighborhoods are defined and explored within the proposed GVNS. The proposed method is compared to a Mixed-Integer Linear Program (MILP) for a subset of small-sized test instances. The efficiency of the proposed approach is additionally tested on the set of hard test instances from the literature and the results are compared against the existing methods, in particular, the state-of-the-art algorithm that explores Basic VNS.