• Journals
  • Discipline
  • Indexed
  • Institutions
  • About
JavaScript is disabled for your browser. Some features of this site may not work without it.
View Item 
  •   Home
  • Universidad del Bío-Bío
  • Revista Ingeniería Industrial
  • View Item
  •   Home
  • Universidad del Bío-Bío
  • Revista Ingeniería Industrial
  • View Item

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

Author
Centeno Romero, Manuel Vicente

Salazar Salazar, Hebel Alexander

Full text
http://revistas.ubiobio.cl/index.php/RI/article/view/105
Abstract
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.
Metadata
Show full item record
Discipline
Artes, Arquitectura y UrbanismoCiencias Agrarias, Forestales y VeterinariasCiencias Exactas y NaturalesCiencias SocialesDerechoEconomía y AdministraciónFilosofía y HumanidadesIngenieríaMedicinaMultidisciplinarias
Institutions
Universidad de ChileUniversidad Católica de ChileUniversidad de Santiago de ChileUniversidad de ConcepciónUniversidad Austral de ChileUniversidad Católica de ValparaísoUniversidad del Bio BioUniversidad de ValparaísoUniversidad Católica del Nortemore

Browse

All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

LoginRegister
Dirección de Servicios de Información y Bibliotecas (SISIB) - Universidad de Chile
© 2019 Dspace - Modificado por SISIB