DESARROLLO DE UN PROGRAMA PARA RESOLVER EL PROBLEMA DE ASIGNACIÓN 3-DIMENSIONAL A TRAVÉS DE UN ALGORITMO GENÉTICO

Resumen

En el presente trabajo se desarrolla un programa para resolver el problema en el cual dados tres (3) conjuntos disjuntos, cada uno conteniendo n elementos, y dado el costo de toda tripleta conteniendo un elemento de cada conjunto, se desea computar n tripletas disjuntas minimizando la suma de los costos. Este problema es conocido como el problema de asignación 3-dimensional y es NP-duro en el sentido fuerte. Para su resolución, se diseñó y analizó una metaheurística denominada Algoritmo Genético, la cual es un método de búsqueda en el que las soluciones al problema son capaces de reproducirse entre sí, generándose nuevas soluciones cada vez más próximas al óptimo.

PALABRAS CLAVES: Genético, asignación, NP-duro, IO.

ABSTRACT

In this work, we developed a program to solve the problem in which, given three disjoint sets, each one containing n items, and given the cost of any triplet containing one item from each set, one wishes to compute n disjoint triplets minimizing the sum of costs. This problem is known as the 3-dimensional assignment problem and it is NP-hard in the strong sense. To solve it, we designed and analyzed a metaheuristic called a Genetic Algorithm, which is a searching method wherein the solutions to the problem are able to reproduce among themselves, generating new solutions closer and closer to the optimum.

KEY WORDS: Genetic, assignment, NP-hard, OR.