Abstract
Over the last decades, graph domination problems have attracted the attention of both scientists and practitioners. Among the different variants, the Roman Domination Problem is one of the most studied problems in the literature. Since its definition, several variants with different constraints have been proposed, with the Minimum Roman 3-Domination Problem being one of the most recent proposals. This problem has been mainly addressed from theoretical and exact perspectives, but it has been almost ignored from the heuristic perspective. In this paper, a hybrid algorithm that combines Greedy Randomized Adaptive Search Procedure with Iterated Greedy is proposed, as well as extensive computational experimentation that evaluates the performance of the proposed method by comparing it with the state of the art. A new movement operator, named Crater, is proposed in order to provide a better exploration of the search space. The results, supported by statistical tests, show that the proposal emerges as the most competitive method for the addressed problem when considering challenging instances where the exact model is not able to guarantee optimality.
Jesús Sánchez-Oro
Associate Professor
Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.
Alejandra Casado
Collaborator
My research interests include metaheuristics and combinatorial optimization.
Abraham Duarte
Full Professor
Abraham Duarte is Full Professor in the Computer Science Department at the Rey Juan Carlos University (Madrid, Spain). He has done extensive research in the interface between computer science, artificial intelligence, and operations research to develop solution methods based on Computational Intelligence (metaheuristics) for practical problems in operations-management areas such as logistics and supply chains, telecommunications, decision-making under uncertainty and optimization of simulated systems.