Heuristics for the Bi-Objective Diversity Problem

The Max-Sum diversity and the Max-Min diversity are two well-known optimization models to capture the notion of selecting a subset of diverse points from a given set. The resolution of their associated optimization problems provides solutions of different structures, in both cases with desirable characteristics. They have been extensively studied and we can find many metaheuristic methodologies, such as Greedy Randomized Adaptive Search Procedure, Tabu Search, Iterated Greedy, Variable Neighborhood Search, and Genetic algorithms applied to them to obtain high quality solutions. In this paper we solve the bi-objective problem in which both models are simultaneously optimized. No previous effort has been devoted to study the “combined problem” from a multi-objective perspective. In particular, we adapt the mono-objective methodologies applied to this problem to the resolution of the bi-objective problem, obtaining approximations to its efficient front. An empirical comparison discloses the best alternative to tackle this NP-hard problem.