Application of Ant Colony Optimization for Multi-objective Production Problems
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.
[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.
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:58325", author = "Teerapun Saeheaw and Nivit Charoenchai and Wichai Chattinnawat", title = "Application of Ant Colony Optimization for Multi-objective Production Problems", 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.", volume = "3", number = "12", pages = "1536-6", }
