Evaluación del rendimiento de técnicas heurísticas para el S-labeling

Abstract

El 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.