Algoritmo para el 4ap haciendo uso de la metaheuristica sistema hormiga

Resumen

La metaheurística sistema hormiga consiste en la analogía entre el procedimiento que utilizan las hormigas reales para la búsqueda de alimentos, encontrando la ruta más corta, y los problemas de optimización combinatoria para encontrar la mejor solución. Entre estos problemas se encuentra el de asignación multidimensional (mAP), el cual es un problema NP-difícil para m > 2. En la actualidad no se ha desarrollado trabajo alguno sobre el 4AP (mAP con m=4), tampoco existe publicación sobre la aplicación del sistema hormiga para el mAP. En este trabajo se desarrolló un software que hace uso de la metaheurística sistema hormiga para encontrar la mejor solución o aproximada al 4AP, con problemas generados aleatoriamente. Se implementó una metodología híbrida entre la metodología de Investigación de Operaciones descrita por Taha (1991) y la ingeniería de software (1990). El número de asignaciones tomadas en cuenta para verificar qué tan buenas son las soluciones arrojadas por el software, varía desde n=2 hasta n=25, obteniéndose soluciones exactas para 2 £ n £ 6, ya que al compararse dichas soluciones con las dadas por XPRESS (software de programación lineal que se usa para resolver modelos matemáticos) se observa la igualdad en los resultados. Para n _ 7, XPRESS (la versión utilizada) no ofrece respuesta alguna, pero el software desarrollado arroja buenos resultados en un tiempo computacional razonable, considerando el número de asignaciones que se procesan en cada n.

The metaheuristic ant system consists on the analogy among the procedure used by the real ants for searching food, for finding the shortest route; and the problems of combinatoria optimization to find the best solution. Among these problems we can find the multidimensional assignment problem (mAP), which is a NP-difficult problem for m > 2. At the present time, there isn‘t any work that has been developed, on this topic about the 4AP (mAP with m=4), neither publication exists on the application of the ant system for the mAP. In this work a software was developed using the metaheurística ant system, in order to find the best solution or an approximate solution for the 4AP, with aleatorily generated problems. A hybrid methodology was implemented among methodology of Investigation of Operations described by Taha (1991) and the software engineering by Pressman (1990). The number of assignments taken into account to verify how good the solutions given by the software are; varies from n=2 until n=25, obtaining exact solutions for 2 £ n £ 6, since when they are compared with those given by XPRESS (software of lineal programming that is used to solve mathematical models), the equality is observed in the results. For n _ 7, XPRESS (the used version) doesn’t offer any answer, but the developed software gives good results at one reasonable computational time, considering the number of assignments that are processed in each n.