RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación
Artículo científico (JournalArticle)
A Biased-Randomized Algorithm for the Bi-Objective Capacitated Dispersion Problem with Symmetries
[EN] 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 & varepsilon;-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., This work has been partially supported by the Spanish Ministry of Science, Innovation and Universities/AEI (PID2022-138860NB-I00, AIA2025-163553-C44) and the Generalitat Valenciana (2024 CIAICO 117).