Diseño de una metaheurístico para la solución del problema de la mochila múltiple con configuraciones
Trabajo de grado - Pregrado
2021-11-25
En el presente proyecto se busca desarrollar una metaheurística para resolver una variante del problema de la mochila múltiple, basada en una metaheurística recientemente desarrollada para resolver problemas de dominio continuo. Para lograrlo, se desarrolló un algoritmo que mantiene la lógica del modelo inicial y se agregaron nuevas funciones para que funcionase adecuadamente con la codificación binaria de las variables de decisión del problema. Con el fin de realizar comparaciones, se diseñaron variantes del algoritmo principal y se construyó un experimento en el que se realizaron varias corridas, con instancias predefinidas y probadas con otros algoritmos, en un orden aleatorio para cada variante, para al final obtener algunos datos descriptivos, los GAP’s y los tiempos de ejecución medios. Los resultados indican un desempeño competente con respecto a algoritmos exactos como CPLEX, mientras que es inferior a otras metaheurísticas desarrolladas con anterioridad para este tipo problemas de optimización, en términos tanto de valor objetivo como de tiempo de ejecución en el presente proyecto se busca desarrollar una metaheurística para resolver una variante del problema de la mochila múltiple, basada en una metaheurística recientemente desarrollada para resolver problemas de dominio continuo. Para lograrlo, se desarrolló un algoritmo que mantiene la lógica del modelo inicial y se agregaron nuevas funciones para que funcionase adecuadamente con la codificación binaria de las variables de decisión del problema. Con el fin de realizar comparaciones, se diseñaron variantes del algoritmo principal y se construyó un experimento en el que se realizaron varias corridas, con instancias predefinidas y probadas con otros algoritmos, en un orden aleatorio para cada variante, para al final obtener algunos datos descriptivos, los GAP’s y los tiempos de ejecución medios. Los resultados indican un desempeño competente con respecto a algoritmos exactos como CPLEX, mientras que es inferior a otras metaheurísticas desarrolladas con anterioridad para este tipo problemas de optimización, en términos tanto de valor objetivo como de tiempo de ejecución.