DOI:
https://doi.org/10.14483/22484728.11897Publicado:
2016-12-20Número:
Vol. 10 Núm. 2 (2016)Sección:
Visión InvestigadoraAlgoritmo de optimización de colonias de hormigas para el problema de distribución en planta
Ant colony optimization algorithm for facility layout problem
Palabras clave:
Metaheurísticas, Optimización combinacional, Optimización con colonias de hormigas, Problema de distribución en planta (es).Palabras clave:
metaheuristics, combinatorial optimization, Ants Colonies Optimization, Facility Layout Problem (en).Descargas
Resumen (es)
Este artículo es resultado de un trabajo de investigación sobre las aplicaciones de algoritmos bioinspirados e inteligentes en el ámbito de ingeniería en producción, en la Universidad Distrital Francisco José de Caldas, abarcando las temáticas de investigación de operaciones, distribución en planta industrial de manufactura entre otros. Se pretende buscar la optimización a problemas propios de esos campos, aplicando inteligencia artificial de enjambres, a partir de la implementación de un algoritmo de Optimización de Colonias de Hormigas (Ant Colony Optimization - ACO) como herramienta metaheurística de planificación y optimización del problema de distribución en planta, con el objetivo de buscar la mejor asignación espacial de estaciones o celdas de trabajo. Se presentan los conceptos teóricos explorados y los resultados obtenidos. En primer lugar se efectuó la revisión de estado del arte sobre la temática, luego se evaluaron los posibles algoritmos de solución, para identificar la función objetivo a optimizar, para finalmente aplicar el algoritmo ACO, y evaluar los resultados de desempeño del mismo frente a la configuración inicial que tenía la planta.
Resumen (en)
This paper is the result of a research on the applications of bio-inspired algorithms in the field of production engineering in the District University Francisco José de Caldas, covering the topics of operations research, industrial layout distribution in manufacturing plant among others. It is intended to seek optimization problems of these fields, using artificial intelligence of swarms from the implementation of an ant colony optimization algorithm (Ant Colony Optimization - ACO) as metaheuristic planning tool and optimization of layout problem. It plans, with the goal of finding the best spatial allocation of work stations or cells. Theoretical concepts explored and results are presented. First, a state of the art review on the subject made, then the possible solution algorithms were evaluated to identify the objective function to optimize, to finally apply the ACO algorithm, and evaluate the results of performance against the Initial configuration as the plant.
Referencias
R. H. Ballou. “Logística Administración de la Cadena de Suministro”. Quinta Edición, México: Pearson educación, págs., 14 y 64, 2004
K. Suzuki and M. Yokoo. “Secure Combinatorial Auctions by Dynamic Programming with Polynomial Secret Sharing”. Harvard School of Engineering and Applied Sciences. October 2014. [Online], available: http://www.eecs.harvard.edu/~cat/cs/diss/clock/suzuki02secure.pdf
R. Bellman & S. DreyFus. “Applied Dynamic Programming”. Princeton University Press, 1962.
W.L. Winston. "Investigación de Operaciones. Aplicaciones y Algoritmos”. Editorial Iberoamérica, 1994.
V. Maniezzo, L. M. Gambardella, and F. De Luigi, “Ant Colony Optimization,” Optimization Techniques in Engineering. SPRINGER-VERLAG, vol. 141, pp. 101–117, 2004.
A. Colorni, M. Dorigo, V. Maniezzo, and others, “Distributed optimization by ant colonies,” in Proceedings of the first European conference on artificial life, vol. 142, pp. 134–142, 1991.
M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: An autocatalytic optimizing process,” TR91-016, Politecnico di Milano, 1991
M.M. Flood. “The traveling salesman problem”. Operations Research, vol. 4, no. 1, Feb. 1956.
L. Kang and W. Cao, “An Improved Genetic & Ant Colony Optimization Algorithm for Travelling Salesman Problem,” in 2010 International Symposium on Information Science and Engineering (ISISE), pp. 498–502, 2010.
T. Stützle and M. Dorigo, “ACO algorithms for the traveling salesman problem,” Evolutionary Algorithms in Engineering and Computer Science, pp. 163–183, 1999.
C. Blum, “Ant colony optimization: Introduction and recent trends”. Physics of Life Reviews, vol. 2, no. 4, pp. 353–373, 2005.
M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no 1, 1997, pp. 53-66.
Li, K., Kang, K., Zhang, W., & Li, B, ”Comparative analysis of genetic algorithm and ant colony algorithm on solving traveling salesman problem”, In: Proceedings of the IEEE International Workshop on Semantic Computing and Systems, pp.72-75, 2008.
G. Dantzig, R. Fulkerson, S. Johnson, “Solution of a Large-Scale Traveling-Salesman Problem” Journal of the Operations Research Society of America, vol. 2, no. 4 (Nov., 1954),
M. Nourelfath, N. Nahas, and B. Montreuil, “Coupling ant colony optimization and the extended great deluge algorithm for the discrete facility layout problem,” Engineering Optimization, vol. 39, no 8, pp. 393-410, 2007.
M. Dorigo and C. Blum, “Ant colony optimization theory: A survey,” Theoretical Computer Science, vol. 344, no. 2–3, pp. 243–278, 2005.
Y. Hani, L. Amodeo, F. Yalaoui, H. Chen, “Ant colony optimization for solving an industrial layout problem,” European Journal of Operational Research, vol. 183, no 2, pp. 633-642, 2007.
K. Li, L. Kang, W. Zhang, and B. Li, “Comparative Analysis of Genetic Algorithm and Ant Colony Algorithm on Solving Traveling Salesman Problem,” in IEEE International Workshop on Semantic Computing and Systems, 2008. WSCS ’08, pp. 72–75, 2008
R. Contreras. “Modelo de optimización en la generación de plantas industriales, considerando las actividades de mantenimiento y las condiciones ambientales mediante el uso de la metodología de los algoritmos genéticos”. Tesis para optar el título de doctor. Universidad Politécnica de Valencia, pp. 81-281, 2010.
J. González, I. Rojas, H. Pomares, M. Salmerón and J.J. Merelo “Web newspaper layout optimization using simulated annealing.” IEEE Transactions on System, Man, and Cybernetics, Part B, vol 32, no 5, pp. 686-691, 2002.
M. Dorzán, E. Gagliardi, M. Leguizamón, M. Taranilla. “Algoritmos ACO aplicados a problemas geométricos de optimización”. Proyecto UPM AL09-PAC12 y Proyecto Tecnologías Avanzadas de Bases de Datos Universidad Nacional de San Luis, Argentina, 1-2, 2009.
R. Martí. “Procedimientos metaheurísticos en optimización combinatoria”. Universidad de Valencia. Departament d’Estadística iInvestigació Operativa. Facultat de Matemátiques, pp. 2-9, 2003.
M. A. Muñoz, J.A. López y E.F. Caicedo. “Inteligencia de enjambres: sociedades para la solución de problemas (una revisión)”. Revista Ingeniería e Investigación vol. 28 no. 2, pp. 119-130, agosto de 2008.
ACO “Public Software” July 2015, [Online] Available in:
http://iridia.ulb.ac.be/~mdorigo/ACO/aco-code/public-software.html
.png)
.jpg)
