ارزیابی و مقایسه الگوریتم های بهینه سازی ژنتیک، شبیه سازی تبرید و فاخته ها در مکان یابی رقابتی تسهیلات (مطالعه موردی: بانکها)

نوع مقاله: پژوهشی

نویسندگان

1 دانشگاه تهران

2 دانشگاه تبریز

چکیده

  این مقاله به مکان­یابی بانکها تحت شرایط رقابتی با سطوح جذابیت متفاوت پرداخته است. مساله مکان­یابی بانکها به فاکتورهای زیادی نیاز داشته و جزء مسایل NP-HARD طبقه­بندی می­شود. استفاده از روشهای فراابتکاری برای حل مسایل NP-HARD علیرغم تقریبی بودن، مناسب­ترین راه حل به نظر می­رسد. در این تحقیق از روشهای بهینه­سازی ژنتیک، شبیه­سازی تبرید و الگوریتم بهینه­سازی فاخته­ها در حل مساله مکان­یابی رقابتی بانکها استفاده شده است.  روشها به طوری آماده شدند که قابلیت پیدا نمودن مکان بانک جدید با وجود بانکهای رقیب را دارند و مکان بانک جدید از بانکهای هم نوع خودش تا حد ممکن دورتر باید باشد (هدف بازاریابی). همچنین در مجموع کل مشتریان این نوع بانک نبایستی از یک حدی کمتر شده و میزان جذب مشتری شعبه جدید التاسیس بانک از یک تعدادی کمتر نشود (محدودیت­ها). بدین منظور قسمتی از شهر تبریز جهت پیاده­سازی انتخاب شد. در نهایت به منظور ارزیابی کیفیت و دقت الگوریتم­ها از تست تکرارپذیری و مقایسه اعداد همگرایی برای نتایج حاصل از اجرای هر الگوریتم روی داده­ها استفاده شد. نتایج حاصل از این آزمون­ها عملکرد دقیقتر و همچنین سرعت همگرایی بیشتر، الگوریتم فاخته­ها نسبت به روشهای بهینه­سازی ژنتیک و شبیه­سازی تبرید در بهینه­سازی مکان­یابی رقابتی بانکها را نشان می­دهد. 

کلیدواژه‌ها


عنوان مقاله [English]

The Assessment and Comparison of a Genetic Algorithm, Simulated Annealing and Cuckoo Optimization Algorithm for Optimization of the Facility Location under Competitive Conditions (Case Study: Banks)

نویسندگان [English]

  • Farshad Hakim pour 1
  • Siamak Talat Ahary 2
  • Abolfazl Ranjbar 2
چکیده [English]

This paper determines the location of bank branches under competitive conditions with different attractive conditions. Finding an optimum location of branches depends on many factors and these problems are known as NP-hard problems. Despite being approximate methods, meta-heuristic algorithms seem suitable tools for solving NP-hard problems. In this paper, Genetic Algorithm (GA), Simulated Annealing (SA) and Cuckoo Optimization Algorithm (COA) are applied for finding the best location of bank branches. From marketing point of view, the aim is to attract more customers while the number of attracted persons to a new branch should be acceptable. The new methods have capability to find the optimum location of new branches under competitive conditions. The location of a new branch should be as far away as possible from branches of the same bank. The other condition is that the total number of customers for the new branch should not be less than a specified number, while the new branch should not attract customers of old branches of the same bank more than a threshold. To fulfill this propose a part of the Tabriz city was selected for implementation. Finally, to evaluate quality and accuracy of the algorithms, several iterations with different seeds are performed. The results of statistical and final tests indicate that the accuracy and convergence speed of Cuckoo Optimization Algorithm are more than the Simulated Annealing and Genetic Algorithms in finding optimal location of bank branches under competitive conditions.

کلیدواژه‌ها [English]

  • Facility Location under Competitive
  • Genetic Algorithm(GA)
  • Simulated Annealing (SA) and Cuckoo Optimization Algorithm(COA)
  • Banks
1[آقا محمدی، ح.، سعدی مسگری م.، مولایی، د.، کریمی، و. (1391)، توسعه یک روش ابتکاری برای بهینه سازی مساله مکان­یابی و تخصیص در عملیات امداد رسانی به مصدومان زلزله، نشریه علمی پژوهشی برنامه ریزی و آمایش فضا، دوره شانزدهم، شماره 2، صفحه 19-1.
[2] Megiddo, N., Supowit, K.J. (1984). "On the complexity of some common geometric location problems", SIAM Journal on Computing, Vol. 13, pp. 182–96.
[3] Worboys, M. (1995). "GIS: A Computing Perspective", Bristol, PA: Taylor and Francis.
[4] Zhang, L., Rushton, G. (2008). "Optimizing the size and locations of facilities in competitive multi-site service systems", Computers and Operations Research, Vol. 35, pp. 327-338.
[5] Suárez-Vega, R., Santos-Peñate, D.R., Dorta-González, P., Rodríguez-Díaz, M. (2011). "A multi-criteria GIS-based procedure to solve a network competitive location problem", Applied Geography, Vol. 31, pp. 282-291.
[6] Suárez-Vega, R., Santos-Peñate, D.R., Dorta-González, P. (2012). Location models and GIS tools for retail site location, Applied Geography, Vol. 35, pp. 12-22.
]7[دائی کریم زاده، س.، علیمرادی ریزی، م.، حبیبی پور، ح. (1389)، بررسی عوامل مؤثر بر تجهیز منابع بانکی از دیدگاه مدیران شعب بانک رفاه شهر اصفهان، اولین کنفرانس بین المللی مدیریت و نوآوری، شیراز.
[8] Daskin, M.S. (1995). "Network and Discrete Location: Models, Algorithms, and Applications", Wiley, New York.
[9] Drezner, Z., Hamacher, H. (2002). "Facility Location: Applications and Theory", Springer, Berlin.
[10] Zhao, L. (2002). "The Integration of Geographical Information Systems and Multicriteria Decision Making Models for the Analysis of Branch Bank Closures", University of New South Wales, Sydney, Australia, pp. 59-80.
[11] Current, J.R., Storbeck, J.E. (1994). "A multiobjective approach to design franchise outlet networks", Journal of the Operational Research Society, Vol. 45, pp. 71-81.
[12] Drezner, T. (2011). "Cannibalization in a competitive environment", International Regional Science Review, Vol. 34, pp. 306-322.
[13] Hotelling, H. (1929). "Stability in competition", Economic Journal, Vol. 39, pp. 41–57.
[14] Reilly, W. J. (1931). "The law of retail gravitation", New York: Knickerbocker Press.
[15] Converse, P. D. (1949). "New laws of retail gravitation", Journal of Marketing, Vol. 14, pp. 379-384.
[16] Huff, D.L. (1964). "Defining and estimating a trading area", Journal of Marketing, Vol. 28, pp. 34-38.
[17] Suárez-Vega, R., Santos-Peñate, D.R., Dorta-González, P. (2004). "Competitive multifacility location on networks ", Journal of Regional Science, Vol. 44, pp. 569-588.
[18] Plastria, F. (2001). "Static competitive facility location, an overview of optimization approaches", European Journal of Operational Research, Vol. 129, pp. 461-470.
[19] Azadeh, A, Ghaderi, S.F., Maghsoudi, A. (2008). "Location optimization of solar plants by an integrated hierarchical DEA PCA approach", Energy Policy; Vol. 36, pp. 3993-4004.
[20] Tabari, M., Kaboli, A., Aryanezhad, M.B., Shahanaghi K., Siadat, A. (2008). "A new method for location selection: A Hybrid Analysis", Applied Mathematics and Computation, Vol. 206, pp. 598-606.
[21] Chou, C.C. (2007). "A fuzzy MCDM method for solving marine transshipment container port selection problems", Applied Mathematics and Computation; Vol. 186, pp. 435-444.
[22] Onut, S., Efendigi, T., Soner, K.S. (2009). "A Combined Fuzzy MCDM Approach for Selecting Shoping Center Site: A Example form Istanbul, Turkey", Expert Systems with Applications, Vol. 37, pp. 1973-1980.
[23] Yu, B., Yang, Z., Cheng, C. (2006). "Optimizing the Distribution of Shopping Centers with Parallel Genetic Algorithm", Engineering Applications of Artificial Intelligence, Vol. 20, pp. 215-223.
[24] Drezner, T.,  Drezner,  Z. (2011). "The gravity multiple server location problem, Computers and Operations Research", Vol. 38, pp. 694–701.
[25] Aboolian, R., Berman, O., Krass, D. (2007). "Competitive facility location and design problem", European Journal of Operational Research, Vol. 182, pp. 40–62.
[26] Aras, N., Yumusak, S., Altmel, I.K. (2007). "Solving the capacitated multi-facility Weber problem by simulated annealing, threshold accepting and genetic algorithms", Springer, Operations Research/Computer Science Interfaces Series, Vol. 39, pp. 91-112.
[27] Beresnev, V. (2013). "Branch-and-bound algorithm for a competitive facility location problem", Computers and Operations Research, Vol. 40, pp. 2062–2070.
[28] Karaganis, A., Mimis, A. (2010), "A Geographical Information System Framework for Evaluating the Optimum Location of Point-Like Facilities," Asian Journal Of Information Technology, Vol. 10, pp. 129-135.
[29] Zucca, A., Sharifi, A.M., Andrea, G.F. (2008). "Application of spatial multi-criteria analysis to site selection for a local park: A case study in the Bergamo Province, Italy", Journal of Environmental Management, Vol. 88, pp. 752–769.
[30] Badri, M.A. (1999). "Combining the analytic hierarchy process and goal programming for global facility location-allocation problem", International Journal of Production Economics, Vol. 62, pp. 237-248.
[31] Bozkaya, B., Yanik, S., Balcisoy, S. (2010). "A GIS-Based Optimization Framework for Competitive Multi-Facility Location-Routing Problem", Springer Science+Business Media, Netw Spat Econ, Vol. 10, pp. 297–320. (DOI 10.1007/s11067-009-9127-6)
[32] Saaty, T.L. (1980). "The Analytic Hierarchy Process: Planning, Priority Setting, Resource Allocation", McGraw-[1] Hill, New York, NY, Vol. 437.
]33[قدسی پور، س ح.( 1385)،  فرآیند تحلیل سلسله مراتبی، دانشگاه امیر کبیر، تهران، ایران.
[34] Ying, X., Guang-Ming, Z., Gui-Qiu, C., Lin, T., Ke-Lin, W., Dao-You, H. (2007). "Combining AHP with GIS in Synthetic Evaluation of Eco-environment Quality—A Case Study of Hunan Province, China", Ecological Modelling, Vol. 209, pp. 97–109.
[35] Saaty, T.L., Vargas, L.G. (1991). "Prediction, Projection and Forecasting", Kluwer Academic Publishers, Dordrecht, Vol. 251.
[36] Holland, J.H. (1975). "Adaptations in Natural and Artificial Systems", Ann Arbor, MI: University of Michigan Press.
[37] Goldberg, D.E. (1989). "Genetic Algorithms in Search, Optimization, and Machine Learning ", Addison-Wesley.
[38] Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E. (1953). "Equation of State Calculations by Fast computing Machines", Journal of Chemical Physics, Vol. 21, pp. 1087–1092.
[39] Kirkpatrick, S, Gelat, C.D., Vecchi, M.P. (1983). "Optimization by simulated annealing", Science, Vol. 220, pp. 671–680.
[40] White, S.R. (1984). "Concept of Scale in Simulated Annealing", Proceeding IEEE International Conference on Computer  Design, Portchester, Vol. 122, pp. 261-270.
[41] Yang, X.S., Deb, S. (2009). "Cuckoo search via L´evy flights, Proceeings of World Congress on Nature and Biologically Inspired Computing (NaBIC 2009, India)", IEEE Publications, USA, pp. 210-214.
[42] Rajabioun, R. (2011). "Cuckoo Optimization Algorithm", Applied Soft Computing, Vol. 11, pp. 5508–5518.