Publicación:

Diseño de un algoritmo memético para resolver el problema de coloración del vértice

Resumen

El problema de coloración del vértice consiste en colorear todos los vértices de un grafo de manera que los vértices que están conectados por una arista o borde no compartan el mismo color, esto dado que son vértices adyacentes y el hecho de tener el mismo color representa un conflicto en la coloración, a su vez se busca minimizar el número de colores usados. En el mundo real dicho problema es usado para resolver problemas tales como asignación de asientos, tareas, horarios, la planificación de actividades, la asignación de recursos, en problemas de control de producción, para proyectar redes de ordenadores, en la logística, robótica, genética, sociología, el diseño de redes, el cálculo de rutas óptimas y los problemas de almacenamiento, donde se tiene un conjunto de elementos que deben ser asignados a determinados recursos mientras se optimiza una función objetivo y se satisfacen las restricciones planteadas. En la presente investigación se usa el problema de coloración del vértice para resolver un problema de programación de horario a través de un algoritmo memético programado en Matlab, dicho algoritmo es validado con datos aleatorios donde a través de un diseño factorial completo se evalúan los factores que influyen en el desempeño del mismo con el fin de decidir el valor que van a tomar al implementar el algoritmo en el caso de estudio de Escuela de Estudios Industriales y Empresariales de la Universidad Industrial de Santander, se concluye que el algoritmo tiene un mejor desempeño al emplear un conjunto reducido de datos y a su vez se reduce el tiempo de ejecución por lo cual se decide dividir los datos del caso de estudio en 4 subproblemas obteniendo resultados aceptables.