Robles, MarcosCavero, SergioG. Pardo, Eduardo2024-07-022024-07-022024-06-19M. Robles, S. Cavero, E. G. Pardo. El problema del MinSA en el ciclo. XX Conferencia de la Asociación Española para la Inteligencia Artificial (CAEPIA 2024). Organizado por la Asociación Española para la Inteligencia Artificial (AEPIA). A Coruña, España. Del 19 al 21 de junio de 2024. ISBN del Libro de Actas: 978-84-09-62724-0. Páginas: 462-467.978-84-09-62724-0https://hdl.handle.net/10115/36205El problema de S-labeling es un problema de etiquetado de grafos que asigna etiquetas numéricas a los vértices de un grafo, con el objetivo de minimizar una función objetivo. Concretamente, para cada par de vértices adyacentes se anota la etiqueta más pequeña del par. Una vez que se han revisado todos los pares, la función objetivo se calcula como la suma de todas las etiquetas anotadas. En este trabajo preliminar se realiza una propuesta que utiliza la metaheurística GRASP. Concretamente, se analizan un total de cuatro métodos constructivos aleatorizados, dos de ellos tomados de la literatura y dos de esta propuesta. Como método de mejora se proponen dos búsquedas locales y el uso de VND para combinarlas. El mejor algoritmo propuesto se compara con el mejor algoritmo del estado del arte (PIG), utilizando un conjunto de instancias de referencia. Los resultados muestran que uno de los métodos constructivos presentados es capaz de obtener soluciones competitivas con una desviación baja. También se comprueba que la fase de mejora es capaz de refinar las soluciones propuestas por el constructivo, obteniendo soluciones similares a las que se consiguen utilizando el algoritmo del estado del arte. Finalmente, se discuten los puntos fuertes y débiles de esta propuesta y se sugieren algunas líneas de investigación futuras.ATTRIBUTION-NONCOMMERCIAL-NODERIVS 4.0 INTERNATIONALhttps://creativecommons.org/licenses/by-nc-nd/4.0/Etiquetado de grafosVariable Neighborhood SearchS-labelinginfo:eu-repo/semantics/workingPaperinfo:eu-repo/semantics/openAccess