A Biased-Randomized Algorithm for the Bi-Objective Capacitated Dispersion Problem with Symmetries

Given a network of nodes and a certain demand that needs to be satisfied, the capacitated dispersion problem (CDP) involves selecting a subset of nodes to maximize dispersion between them. In many practical instances, symmetry in the structure of the selected nodes (e.g., using nodes of the same type) can lead to synergies. Hence, this paper studies a bi-objective variant of the CDP to account for these symmetries. The first goal seeks to maximize the minimum distance between opened nodes, while the second goal accounts for symmetry by penalizing the use of nodes of different types (in our case, represented by different colors). We formalize the problem as a bi-objective mathematical program and address it through a classical multiobjective strategy, the ϵ-constraint method. Exact methods are used when the problem size allows, even though the problem is NP-hard. To tackle larger instances, we design a biased-randomized algorithm based on a constructive heuristic. Computational experiments show that our biased-randomized algorithm provides high-quality approximations of the Pareto frontier.