Variable Neighborhood Search para el problema de Cyclic Min-Max Sitting Arrangement

M. Robles Rodríguez, S. Cavero, E. G. Pardo

El problema Cyclic Min-Max Sitting Arrangement (CMMSA) es un problema de optimización de embebido de grafos donde los vértices de un grafo con signo deben asignarse a los de un grafo ciclo. El grafo de entrada contiene aristas con pesos +1 o -1, representando relaciones positivas y negativas entre vértices. Para cada vértice la función objetivo cuenta las situaciones en las que vértices conectados por aristas negativas están más cerca que aquellos conectados por aristas positivas. El objetivo es minimizar el número máximo de penalizaciones en cualquier vértice individual. Al enfocarse en minimizar las penalizaciones máximas, el CMMSA asegura un reparto más equilibrado de conflictos comparado con la variante que minimiza la suma de penalizaciones. Este artículo presenta un estudio de metodologías de Variable Neighborhood Search para resolver el CMMSA, analizando múltiples variantes algorítmicas. Nuestros experimentos computacionales demuestran la efectividad de los métodos propuestos.

Palabras clave: Variable Neighborhood Search, Embebido de grafos, Grafo con signos, Minimum Sitting Arrangement

Heurísticas y Metaheurísticas I
10 de junio de 2025  15:30
MR 1

J. Serrano Roig, A. Martinez Gavara, M. Reula Martin

J. Sánchez Díaz, S. Cavero, E. G. Pardo

X. Benavides Canta, L. Hernando Rodriguez, J. Ceberio Uribe, J. A. Lozano Alonso

M. Malagón, H. F. Iñigo, E. Irurozki, J. A. Lozano Alonso, J. Ceberio