Application of Ant Colony Optimization for Multi-objective Production Problems

Authors: Teerapun Saeheaw, Nivit Charoenchai, Wichai Chattinnawat

Abstract:

This paper proposes a meta-heuristic called Ant Colony Optimization to solve multi-objective production problems. The multi-objective function is to minimize lead time and work in process. The problem is related to the decision variables, i.e.; distance and process time. According to decision criteria, the mathematical model is formulated. In order to solve the model an ant colony optimization approach has been developed. The proposed algorithm is parameterized by the number of ant colonies and the number of pheromone trails. One example is given to illustrate the effectiveness of the proposed model. The proposed formulations; Max-Min Ant system are then used to solve the problem and the results evaluate the performance and efficiency of the proposed algorithm using simulation.

Keywords: Ant colony optimization, multi-objective problems.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1072417

References:

[1] Blum, C. & Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparisons. ACM Computing Surveys, 35(3), 268-308.
[2] Dorigo M., Birattari M. & St├╝tzle T. (2006) Ant Colony optimization: Artificial Ants as Computational Intelligence Technique. IEEE Computational Intelligence Magazine, Nov. 2006.
[3] Blum, C. & Dorigo, M. (2005). Search bias in ant colony optimization: On the role of competition-balanced systems. IEEE Trans. on Evolutionary Computation, 9(2), 159-174.
[4] Dorigo, M. & St├╝tzle, T. (2002). The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances. In: F. Glover and G. Kochenberger (Eds.), Handbook of Metaheuristics. Kluwer Academic Publishers.
[5] Dorigo, M., Maniezzo, V. & Colorni, A. (1996). The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 26(1), 29-41.
[6] Dorigo, M. & Gambardella, L. (1996). Ant Colonies for the Traveling Salesman Problem. Technical Report IRIDIA/1996-3, Universit'e Libre de Bruxelles.
[7] Dorigo, M. & Gambardella, L. (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Trans. on Evolutionary Computation, 1(1), 53-66.
[8] St├╝tzle T., & Hoos H. (2000). Max-Min Ant System. Journal of Future Generation Computer Systems, 16, 889 - 914.
[9] Bullnheimer, B., Hartl, R. F., & Strauss, C. (1999). A new ranked-based version of the ant system: a computational study. Central European Journal for Operations Research and Economics, 7(1), 25-38.
[10] Cordón O, Herrera F, Fernández de Viana I, Moreno L. A new ACO model integrating evolutionary computation concepts: The best-worst ant system. In: Proc Second IntWorkshop on Ant Algorithms, Brussels, Belgium, 2000. pp 22-29.
[11] Cordón O, Fernández de Viana I, Herrera F. Analysis of the best-worst ant system and its variants on the TSP. Mathware Soft Comput 2002;9:177-192.
[12] Cordón O, Fernández de Viana I, Herrera F. Analysis of the best-worst ant system and its variants on the QAP. In Dorigo M, Di Caro G, Sampels M, editors. Ant algorithms. LNCS 2463. Heidelberg: Springer- Verlag; 2002. pp 228-234.
[13] DI CARO, G., DORIGO, M., "Extending AntNet for Best-effort Quality-of-Services Routing", Ant Workshop on Ant Colony Optimization, htpp://iridia.ulb.ac.be/ants98/ants98.html, 15-16, 1998.
[14] DALKILIÇ, G., TÜRKMEN, F., "Karınca Kolonisi Optimizasyonu", YPBS2002 - Yüksek Performanslı Bilişim Sempozyumu, Kocaeli, Ekim 2002
[15] VRAHATIS, M.N., BOUTSINAS, B., ALEVIZOS, P., PAVLIDES, G., "The new k-windows algorithm for improving the k-means clustering algorithm", Journal of Complexity 18, pp. 375-391,2002.
[16] C. E. Mariano, E. Morales, A Multiple Objective Ant-Q Algorithm for the Design of Water Distribution Irrigation Networks, Technical Report n HC-9904, Instituto Mexicano de Tecnologa del Agua, Mexico, June, 1999.
[17] M. Gravel, W. L. Price, C. Gagn'e, Scheduling Continuous Casting of Aluminium using a Multiple Objective Ant Colony Optimization Metaheuristic, European Journal of Operational Research, vol. 143, n1, 2002, p. 218-229.
[18] P. R. McMullen, An Ant Colony Optimization Approach to Addressing a JIT Sequencing Problem with Multiple Objectives, Artificial Intelligence in Engineering, vol. 15, n3, 2001, p. 309-317.
[19] B. Bar'an, M. Schaerer, A Multiobjective Ant Colony System for Vehicle Routing Problem with TimeWindows, Proc.Twenty first IASTED International Conference on Applied Informatics, Insbruck, Austria, 2003, p. 97-102.
[20] S. Iredi, D. Merkle, M. Middendorf, Bi-Criterion Optimization with Multi Colony Ant Algorithms, First International Conference on Evolutionary Multi-criterion Optimization (EMO-01), vol. 1993, Lecture Notes in Computer Science, 2001, p. 359-372.
[21] K. Doerner, W. J. Gutjahr, R. F. Hartl, C. Strauss, C. Stummer, Pareto Ant Colony Optimization: A Meta-heuristic Approach to Multiobjective Portfolio Selection, Annals of Operations Research, 2004.
[22] L. Gambardella, E.D. Taillard, G. Agazzi, MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows, in F. G. D. Corne, M. Dorigo(ed.), New Ideas in Optimization, McGraw Hill, London, UK, 1999, p. 63-76.
[23] B. Bullnheimer R.F. Hartl C. Strauss, An Improved Ant system Algorithm for the Vehicule Routing Problem, Annals of Operations Research, vol. 89, 1999, p. 319-328.
[24] K. Doerner, R. F. Hartl, M. Teimann, Are COMPETants More Competent for Problem Solving? The Case of Full Truckload Transportation, Central European Journal of Operations Research, vol. 11, n2, 2003, p. 115-141.
[25] Alaya, I. Solnon, C. Ghedira, K., Ant Colony Optimization for Multi- Objective Optimization Problems, 19th IEEE International Conference on Tools with Artificial Intelligence, Vol. 1, 450-457, 2007.
[26] Stutzle, T., and Hoos, H. H. (2000). MAX-MIN ant system. Future Generation Comput. Systems, 16, 889-914.