El problema de asignación de frecuencias generalizado con pesos y su solución
The generalized frequency assignment problem and its solution
David F. Muñoz
Departamento de Ingeniería Industrial y Operaciones, Instituto Tecnológico Autónomo de México, Río Hondo 1, 01080 Ciudad de México, México
E-mail: davidm@itam.mx
Recibido 17 de octubre del 2016; aceptado el 10 de diciembre del 2016
DOI: https://doi.org/10.33017/RevECIPeru2016.0012/
Resumen
En este artículo se reporta el desempeño de 15 métodos heurísticos para encontrar soluciones iniciales y 4 meta-heurísticas para resolver un problema de asignación de frecuencias en el que el valor de las frecuencias asignadas depende de pesos correspondientes a los sitios donde se asigna la frecuencia. Los diferentes algoritmos fueron probados en un conjunto de problemas que se generaron utilizando un generador que representa situaciones similares a la asignación de frecuencias FM en México. Los resultados experimentales mostraron que las heurísticas que consideran los pesos de los sitios tienen un mejor desempeño y, de entre las 4 meta-heurísticas probadas, el mejor desempeño lo obtuvo el algoritmo basado en templado simulado.
Descriptores: asignación de frecuencias, asignación de canales, problema de T-coloreo, meta-heurísticas
Abstract
We report performance of 15 heuristics and 4 metaheuristics to solve a frequency assignment problem where the value of an assigned frequency depends on the weights of the corresponding site where the frequency is assigned. Different algorithms where tested on two sets of problems, the first one corresponds to the well-known Philadelphia problems and the second one to situations similar to the assignment of FM frequencies in Mexico. Experimental results showed that the heuristics that take into account the site weights performed the best and, among the four metaheuristics tested, the algorithm based on simulated annealing performed the best.
Keywords: frequency assignment, channel assignment, T-coloring problem, metaheuristics