Artificial Bee Colony for Quadratic Assignment Problem: A Hospital Case Study
DOI:
https://doi.org/10.21928/juhd.v2n3y2016.pp502-508Keywords:
Quadratic Assignment Problem, Artificial Bee Colony, Hospital Layout, Healthcare ManagementAbstract
The problem of locating hospital departments so as to minimize the total distance travelled by patients can be formulated as a Quadratic Assignment Problem (QAP).In general, (QAP) is one of the Combinatorial Optimization Problems and always high dimensional. Therefore, the use of meta-heuristics that generates good solutions in reasonable computer time becomes an attractive alternative. In this paper, a proposed artificial bee colony (ABC) algorithm is used to optimize QAP. The main idea is to use different crossover techniques for employee and onlooker bee stages and use exchange position operator for scout bee stage. The results of ABC algorithm show the efficiency and capabilities of proposed algorithm in finding the optimum solutions, compared with results of GA and SA in all test problems. The purpose of this paper is to apply the QAP in Azadi hospital in Kirkuk city to minimize the total distance travelled by patients. The application involves determine the flow matrix and the distance matrix to solve the problem. The results related that QAP model was presented suitable framework for clinics allocation and optimum use.
References
[1] Armour, G.C. and Buffa E.. Heuristic Algorithm and Simulation Approach to Relative Location of Facilities. Management Science, Volume 9, 1963.
[2] Bäck, T. (1996). "Evolutionary algorithms in theory and practice". New York: Oxford Univ. Press.
[3] Bazaraa M. S. and Sherali. H. D. On the Use of Exact and Heuristic Cutting Plane Methods for the Quadratic Assignment Problem . The Journal of the Operational Research Society, Volume 33, Issue 11, Novmber 1982.
[4] Behzadi, G. & Sundarakani, B. 2014, 'Practical ABC intelligence
[5] solution for Quadratic Assignment Problems', 4th International conference on Industrial Engineering and Operations Management (IEOM), IEOM, Indonesia, pp. 959-966.
[6] Dell’Amico.M, Carlos Díaz.J, Iori.M, and Montanari.R,. (2009)." The single-finger keyboard layout problem".Computers and Operations Research, V( 36), Issue 11, Pages 3002–3012 .
[7] Dickey, J.W. and Hopkins, J.W., .(1972)"Campus building arrangement using TOPAZ". Transportation Research 6, 59–68.
[8] Dowsland, K.A., .( 1995), "Simulated Annealing. In Modern Heuristic Techniques for Combinatorial Problems" (ed. Reeves, C.R.), McGraw-Hill.
[9] Drezner, Z., .(2002)."Heuristic Algorithms for the Solution of the Quadratic Assignment Problem". Journal of Applied Mathematics and Decision Sciences 6, 163–173.
[10] Elshafei, A.N. (1977)."Hospital Layout as a Quadratic Assignment Problem". Operations Research Quarterly 28, 167-179.
[11] Francis, R.L., White, J.A., .(1974)."Facility Layout and Location: An Analytical Approach". Prentice-Hall, Englewood Cliffs, NJ.
[12] Gilmore . P.C. Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem. SIAM Journal on Applied Mathematics , Volume 10, 1962.
[13] Hahn, P. and Krarup, J., .(2001)."A hospital facility layout problem finally solved" ,Journal of Intelligent Manufacturing, Vol 12, 487-496.
[14] Hubert, L., .(1987)."Assignment methods in combinatorial data analysis". Statistics: Textbooks and Monographs Series, vol. 73. Marcel Dekker.
[15] Karaboga, D., Basturk, B. (2008). "On the performance of artificial bee colony (ABC) algorithm", Applied Soft Computing, Vol. 8, pp. 687-697.
[16] Karaboga, D.,Akay, B.,(2010)."Amodified Artifical Bee colony algorithm for real-Parameter optimization" Information Sciences and Elservier,doi:10.1016/j.ins.2010.07.015.
[17] Karboga, D. and Basturg B., (2007), "A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm", J. Glob. Optim. Vol. 39, pp.459-471.
[18] Kaur, A., Goyal, S., (2011), "A survey on the Applications of bee colony optimization Techniques", International Journal on Computer Science and Engineering (IJCSE), ISSN: 0975-3397 Vol. 3 No. 8.
[19] Koopmans, T.C., Beckmann, M.J., 1957."Assignment problems and the location of economic activities". Econometrica 25, 53–76.
[20] Li Y., Pardalos P. M., and Resende M. G.C.. A Greedy Randomized Adaptive Search Procedure for the Quadratic Assignment Problem. DIMACS Series in Discrete Mathematics and Theoretical Computer Science.
[21] Loiola, E.M., de Abreu, N.M.M., Boaventuro-Netto, P.O., Hahn, P., and Querido, T., .(2007)." A survey for the quadratic assignment problem". European Journal of Operational Research 176, 657-690.
[22] Misevicius, A., .(2005)."A tabu search algorithm for the quadratic assignment problem". Computational Optimization and Applications ,30 (1), 95–111.
[23] Nehi, H. M. and Gelareh S.. A Survey of Meta-Heuristic Solution Methods for the Quadratic Assignment Problem. Applied Mathematical Sciences, Volume 1, Issue 46, 2007.
[24] Pollatschek, M.A., N. Gershoni, and Y.T. Radday (1976). "Optimization of the Typewriter Keyboard by Computer Simulation". Angewandte Informatik 10, 438-439.
[25] QAPLIB - A Quadratic Assignment Problem Library.(2012). Retrieved May 2014, from: http://www.seas.upenn.edu/qaplib
[26] Steinberg, L., 1961."The backboard wiring problem:A placement algorithm". SIAM Review 3, 37–50.
[27] Taha,H.A.,. (2007)."Operations Research An Introduction", Pearson Precintle hall, 8th Edition ,New Jersey , USA .
[28] Talbi E.-G., Roux O., Fonlupt C., and Robillard. D. Parallel Ant Colonies for the quadratic assignment problem. Future Generation Computer Systems , Volume 17 ,France, 2001.
[29] Tate, D.E., Smith, A.E., .(1995)."A genetic approach to the quadratic assignment problem". Computers and Operations Research 22, 73–83.
[30] Wilhelm, M.R., Ward, T.L., (1987)."Solving quadratic assignment problems by simulated annealing". IEEE Transactions 19, 107–119.
[2] Bäck, T. (1996). "Evolutionary algorithms in theory and practice". New York: Oxford Univ. Press.
[3] Bazaraa M. S. and Sherali. H. D. On the Use of Exact and Heuristic Cutting Plane Methods for the Quadratic Assignment Problem . The Journal of the Operational Research Society, Volume 33, Issue 11, Novmber 1982.
[4] Behzadi, G. & Sundarakani, B. 2014, 'Practical ABC intelligence
[5] solution for Quadratic Assignment Problems', 4th International conference on Industrial Engineering and Operations Management (IEOM), IEOM, Indonesia, pp. 959-966.
[6] Dell’Amico.M, Carlos Díaz.J, Iori.M, and Montanari.R,. (2009)." The single-finger keyboard layout problem".Computers and Operations Research, V( 36), Issue 11, Pages 3002–3012 .
[7] Dickey, J.W. and Hopkins, J.W., .(1972)"Campus building arrangement using TOPAZ". Transportation Research 6, 59–68.
[8] Dowsland, K.A., .( 1995), "Simulated Annealing. In Modern Heuristic Techniques for Combinatorial Problems" (ed. Reeves, C.R.), McGraw-Hill.
[9] Drezner, Z., .(2002)."Heuristic Algorithms for the Solution of the Quadratic Assignment Problem". Journal of Applied Mathematics and Decision Sciences 6, 163–173.
[10] Elshafei, A.N. (1977)."Hospital Layout as a Quadratic Assignment Problem". Operations Research Quarterly 28, 167-179.
[11] Francis, R.L., White, J.A., .(1974)."Facility Layout and Location: An Analytical Approach". Prentice-Hall, Englewood Cliffs, NJ.
[12] Gilmore . P.C. Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem. SIAM Journal on Applied Mathematics , Volume 10, 1962.
[13] Hahn, P. and Krarup, J., .(2001)."A hospital facility layout problem finally solved" ,Journal of Intelligent Manufacturing, Vol 12, 487-496.
[14] Hubert, L., .(1987)."Assignment methods in combinatorial data analysis". Statistics: Textbooks and Monographs Series, vol. 73. Marcel Dekker.
[15] Karaboga, D., Basturk, B. (2008). "On the performance of artificial bee colony (ABC) algorithm", Applied Soft Computing, Vol. 8, pp. 687-697.
[16] Karaboga, D.,Akay, B.,(2010)."Amodified Artifical Bee colony algorithm for real-Parameter optimization" Information Sciences and Elservier,doi:10.1016/j.ins.2010.07.015.
[17] Karboga, D. and Basturg B., (2007), "A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm", J. Glob. Optim. Vol. 39, pp.459-471.
[18] Kaur, A., Goyal, S., (2011), "A survey on the Applications of bee colony optimization Techniques", International Journal on Computer Science and Engineering (IJCSE), ISSN: 0975-3397 Vol. 3 No. 8.
[19] Koopmans, T.C., Beckmann, M.J., 1957."Assignment problems and the location of economic activities". Econometrica 25, 53–76.
[20] Li Y., Pardalos P. M., and Resende M. G.C.. A Greedy Randomized Adaptive Search Procedure for the Quadratic Assignment Problem. DIMACS Series in Discrete Mathematics and Theoretical Computer Science.
[21] Loiola, E.M., de Abreu, N.M.M., Boaventuro-Netto, P.O., Hahn, P., and Querido, T., .(2007)." A survey for the quadratic assignment problem". European Journal of Operational Research 176, 657-690.
[22] Misevicius, A., .(2005)."A tabu search algorithm for the quadratic assignment problem". Computational Optimization and Applications ,30 (1), 95–111.
[23] Nehi, H. M. and Gelareh S.. A Survey of Meta-Heuristic Solution Methods for the Quadratic Assignment Problem. Applied Mathematical Sciences, Volume 1, Issue 46, 2007.
[24] Pollatschek, M.A., N. Gershoni, and Y.T. Radday (1976). "Optimization of the Typewriter Keyboard by Computer Simulation". Angewandte Informatik 10, 438-439.
[25] QAPLIB - A Quadratic Assignment Problem Library.(2012). Retrieved May 2014, from: http://www.seas.upenn.edu/qaplib
[26] Steinberg, L., 1961."The backboard wiring problem:A placement algorithm". SIAM Review 3, 37–50.
[27] Taha,H.A.,. (2007)."Operations Research An Introduction", Pearson Precintle hall, 8th Edition ,New Jersey , USA .
[28] Talbi E.-G., Roux O., Fonlupt C., and Robillard. D. Parallel Ant Colonies for the quadratic assignment problem. Future Generation Computer Systems , Volume 17 ,France, 2001.
[29] Tate, D.E., Smith, A.E., .(1995)."A genetic approach to the quadratic assignment problem". Computers and Operations Research 22, 73–83.
[30] Wilhelm, M.R., Ward, T.L., (1987)."Solving quadratic assignment problems by simulated annealing". IEEE Transactions 19, 107–119.
Downloads
Published
2016-08-31
How to Cite
Sultan, J. A., Matrood, D. A., & Khaleel, Z. M. (2016). Artificial Bee Colony for Quadratic Assignment Problem: A Hospital Case Study. Journal of University of Human Development, 2(3), 502–508. https://doi.org/10.21928/juhd.v2n3y2016.pp502-508
Issue
Section
Articles
