Metaheuristika za rešavanje uopštenog problema disperzije

Abstract

The generalized dispersion problem is a natural extension of the well-known NP-hard p -dispersion problem. The considered problem arises from practical situations when it is necessary to find the optimal set of locations for establishing objects of the same type, such that the minimal distance between the two chosen locations is maximized. Differently from the classical p-dispersion problem, in the considered generalization, the number of locations to be selected is not fixed and additional constraints are imposed on the total value and total costs of the selected locations. As the generalized dispersion problem is also NP-hard, this paper proposes a mathematical heuristic for solving this problem, based on a combination of variable descent heuristics and exact integer linear programming methods. The presented results of matheuristic on test examples from the literature show that the proposed matheuristic approach is successful in solving problem instances of real-life dimensions.