A Heuristic for Solving the Maximum Dispersion Problem

In this paper, we investigate solving the Maximum Dispersion Problem (MaxDP). For a given set of weighted objects, the MaxDP consists in partitioning this set into a predefined number of groups, such that the overall dispersion of elements, assigned to the same group, is maximized. Furthermore, each group has a target weight and the total weight of each group must be within a specific interval around the target weight. It has been proven that the MaxDP is NP-hard and, consequently, difficult to solve by classical exact methods. In this work, we use variants of Variable Neighborhood Search (VNS) for solving the MaxDP. In order to evaluate the efficiency of VNS, we carried out some numerical experiments on randomly generated instances. The results of the VNS is compared with the solutions provided by the solver Gurobi. According to our results, the VNS gives high quality solutions for small instances and, in solving large instances, it provides some decent solutions for all instances; however, Gurobi fails to provide any solution for some of them.