A general variable neighborhood search for Cyclic Antibandwidth Problem

Resumen

Los Problemas de Diseño de Grafos se refieren a una familia de problemas de optimización donde el objetivo es asignar los vértices de un grafo de entrada a los vértices de un grafo huésped estructurado, optimizando una función objetivo determinada. En este artículo, abordamos uno de estos problemas, llamado Problema de Antibandwidth Cíclico, donde el objetivo es maximizar la distancia mínima de todos los vértices adyacentes, computada en un grafo huésped cíclico. Específicamente, proponemos una Búsqueda de Vecindarios Variables General que combina un Descenso de Vecindarios Variables eficiente con un procedimiento novedoso de destrucción-reconstrucción. Adicionalmente, nuestra propuesta aprovecha dos nuevas estrategias de exploración para este problema: un criterio para romper empates de soluciones con la misma función objetivo y una evaluación eficiente de soluciones vecinas. Además, se proponen dos nuevas estrategias de reducción de vecindarios. Realizamos una experiencia computacional exhaustiva comparando el algoritmo propuesto con los métodos estado del arte actuales sobre un conjunto de instancias previamente reportadas. Los resultados asociados muestran el mérito del algoritmo introducido, emergiendo como el método de mejor rendimiento en aquellas instancias donde los óptimos son desconocidos. Estos resultados se confirman además con pruebas estadísticas no paramétricas.

Citar Esta Publicación

Cavero, S., Pardo, E. G., & Duarte, A. (2022). A general variable neighborhood search for the cyclic antibandwidth problem. Computational Optimization and Applications, 81(2), 657-687.