Un algoritmo metaheurístico de recocido simulado para el 3ap-axial | A metaheuristic algorithm of simulated annealing for the 3AP- axial

Resumen

En el presente trabajo se desarrolló una metaheurística de recocido simulado para la solución del problema de asignación 3-dimensional axial (3AP-axial). El 3AP-axial es un problema de optimización combinatoria perteneciente a la clase NP-difícil; es decir, no existe un algoritmo exacto que pueda resolverlo en un tiempo de cómputo razonable, en el peor de los casos. Es por ello, que se hace uso de metaheurísticas para la búsqueda de “buenas” soluciones. El algoritmo de recocido simulado es un método global de optimización muy hábil para escapar de óptimos locales, el cual efectúa una búsqueda estocástica sobre el espacio de soluciones. Los resultados obtenidos mejoran la calidad de las soluciones reportadas por otros métodos. Además, se lograron soluciones a problemas de mayor dimensión, en tiempo de cómputo menor o igual a un (1) minuto.

PALABRAS CLAVE: Problema de asignación, recocido simulado, metaheurística.

ABSTRACT
In this paper, we developed a simulated annealing metaheuristic to solve the 3-dimensional assignment problem axial (3AP-axial). The 3AP-axial is a combinatorial optimization problem belonging to the NP-hard class; that is, there are no exact algorithms that can solve it in a reasonable computating time, in the worst case. For this reason, metaheuristics was used in order to find "good" solutions. The simulated annealing algorithm is a global optimization method very clever to escape local optima, which performs a stochastic search on the solution space. The results improve the quality of the solutions reported by other methods. Furthermore, solutions were obtained to bigger size problems in a computing time of less or equal than one minute.

KEY WORDS: Assignment problem, simulated annealing, metaheuristic.