ارزیابی و مقایسه الگوریتم های بهینه سازی فرا ابتکاری در مکانیابی تسهیلات مطالعه موردی: بانک ها

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

نویسندگان

1 دانشجوی دکتری سیستم اطلاعات مکانی پردیس دانشکده فنی دانشگاه تهران

2 استادیار گروه مهندسی نقشه برداری پردیس دانشکده فنی- دانشگاه تهران

3 استادیار گروه عمران - دانشکده فنی - دانشگاه تبریز

چکیده

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

کلیدواژه‌ها


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

Evaluating and comparing meta-innovative optimization algorithms in locating facilities Case Study: Banks

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

  • Abolfazl Ranjbar 1
  • Farshad Hakimpour 2
  • Siamak Talat Ahary 3
1 Ph.D. Candidate, Department of GIS engineering, Faculty of surveying engineering, Tehran University
2 Assistant professor, Department of GIS Engineering, Faculty of Surveying Engineering, Tehran University
3 Assistant professor, Department of civil engineering, Faculty of engineering, Tabriz University
چکیده [English]

Extended Abstract
Introduction
The problem of locating bank branches is classified asNP-Hard problem which can possibly be solved only in exponential time by the increase in the number of banks and the large number of customers, especially when the location model includes various datasets, several objectives and constraints. As a consequence, we need to use heuristic methods to solve these types of problems. Also, since majority of data and analyses applied in the locating problems are spatial; GIScience’s abilities should be employed besides optimization methods.
Nowadays, to perform particular financial tasks, bank customers often need to be present at their bank. For the sake of its customers, a bank should increase its branches in the city to attract more customers in the race with competing banks. However, establishing new branches is too expensive and banks prefer to carry out an optimal location finding procedure. Such procedures should consider many criteria and objectives including spatial data of customers, new and existing bank branches as well as the level of attraction of banks. Customers often select a bank that is closer to them, has better services or financial records and also consider other human or physical factors. Hence, planning to increase the number of customers for a new branch of a bank considering spatial criteria and various other objectives appears necessary.
 
Materials & Methods
This paper determines the location of bank branches. Finding an optimum site for 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, Grey Wolf Optimizer (GWO), Genetic Algorithms (GA), Particle Swarm Optimization (PSO), Cultural Algorithms (CA) and Invasive Weed Optimization (IWO) are applied for finding the best location for bank branches. From marketing point of view, the aim is to attract more customers while the number of attracted people to a new branch should be acceptable. The new methods have capability to find the optimum location for new branches. 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. To fulfill this propose, a part of the city of Tabriz was selected for implementation.The assumptions for the defined problem can be expressed as the following statements:
a)We consider four different banks (Melli, Mellat, Sepah and Mehr) in our study area.
b)Population density (of people over 15 years of age) is available at the building block level.
c)Banks have infinite capacity for accepting customers.
d)Each customer refers to only one bank.
e)New bank branches should have maximum distance from the branches of the same bank, so that, it attracts minimum number of customers from branches of the same bank.
 
Conclusion
  To evaluate the quality and accuracy of the algorithms, several iterations are performed. The results of statistical and final tests indicate that the accuracy and convergence speed of Invasive Weed Optimization are more than other Algorithms in finding optimal location of bank branches.
 

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

  • Meta-heuristic algorithms
  • Optimization
  • Location
  • Banks
  • Geospatial Information System
1- A.R. Mehrabian and C. Lucas, “A novel numerical optimization algorithm inspired from weed colonization” Ecological Informatics, vol 1,.pp 355–366, 2006.

2- Aboolian, R., O. Berman & D. Krass, "Competitive facility location and design problem", European Journal of Operational Research, No.182, Pp. 40–62, 2007.

3- Andries P. Engelbrecht Computational Intelligence An Introduction, Second Edition  2007, John Wiley & Sons.pp261-275

4- Aras, N., S. Yumusak & I.K. Altmel, "solving the capacitated multi-facility Weber problem by simulated annealing, threshold accepting and genetic algorithms", Springer, Operations Research/Computer Science Interfaces Series, No. 39, Pp. 91-112, 2007.

5- Aghamohammadi H., Saadi Mesgari M., Molaei D. & Aghamohammadi H., (2013) Development a Heuristic Method to Locate and Allocate the Medical Centers to Minimize the Earthquake Relief Operation Time, Iranian J Publ Health, Vol. 42, No.1, pp.63-71.

6- Azadeh, A, S.F. Ghaderi & A. Maghsoudi, "Location optimization of solar plants by an integrated hierarchical DEA PCA approach", Energy Policy; NO. 36, Pp. 3993-4004, 2008.

7- Badri, M.A., "Combining the analytic hierarchy process and goal programming for global facility location-allocation problem", International Journal of Production Economics, No. 62, Pp. 237-248, 1999.

8- Beresnev, V., "Branch-and-bound algorithm for a competitive facility location problem", Computers and Operations Research, No. 40 ,Pp. 2062–2070, 2013.

9- Bozkaya, B., S. Yanik  & S. Balcisoy, "A GIS-Based Optimization Framework for Competitive Multi-Facility Location-Routing Problem", Springer Science+Business Media, Netw Spat Econ, No. 10 , Pp. 297–320, 2010. (DOI 10.1007/s11067-009-9127-6)

10- Brimberg , J., P. Hansen & N. Mladenovi,  (2000) "Improvements and Comparison of Heuristics for Solving the Uncapacitated Multisource Weber Problem", Journal of Operations Research, Vol. 48, pp. 444-460.

11- Chou, C.C., "A fuzzy MCDM method for solving marine transshipment container port selection problems", Applied Mathematics and Computation; No. 186, Pp. 435-444, 2007.

12- Daskin, M.S., "Network and Discrete Location: Models, Algorithms, and Applications", Wiley, New York, 1995.

13- Drezner  T.,  Drezner  Z. , (2011) The gravity multiple server location problem, Computers & Operations Research, No. 38, pp694–701.

14- Drezner, Z., & H. Hamacher, "Facility Location: Applications and Theory", Springer, Berlin, 2002.

15- Holland, J.H. (1975). "Adaptations in Natural and Artificial Systems", Ann Arbor, MI: University of Michigan Press.

16- Hotelling, H., "Stability in competition", Economic Journal, No.39, Pp. 41–57, 1929.

17- Karaganis A. and Mimis A., (2010),  “A Geographical Information System Framework for Evaluating the Optimum Location of Point-Like Facilities,” Asian Journal Of Information Technology, Vol. 10, No. 4, pp. 129-135.

18- Kennedy, J., Eberhart, R. C., (1995) "Particle swarm optimization", In Proceedings of IEEE international conference on neural networks, 1942–1948, New Jersey: IEEE Press.

19- Megiddo, N & K.J. Supowit, “On the complexity of some common geometric location problems”, SIAM Journal on Computing, No.13, Pp. 182–96, 1984.

20- Muro C, Escobedo R, Spector L, Coppinger R. Wolf-pack (Canis lupus) hunting strategies emerge from simple rules in computational simulations. Behav Process 2011;88:192–7.

21- Murray, A. T. & R. L. Church, (1996) "Applying Simulated Annealing to Location-Planning Models", Journal of Heuristics, Vol. 2, pp. 31-53.

22- Onut, S, T. Efendigi & K.S. Soner, "A Combined Fuzzy MCDM Approach for Selecting Shoping Center Site: A Example form Istanbul, Turkey", Expert Systems with Applications, No. 37, Pp. 1973-1980, 2009.

23- R. Reynolds, An Introduction to Cultural Algorithms, In Proceedings Of the 3rd Annual on Evolutionary Programming, World Scientific, River Edge, NJ, pp. 131-139, 1994.

24- Seyedali Mirjalili, Seyed Mohammad Mirjalili, Andrew Lewis, Grey Wolf Optimizer, Advances in Engineering Software 69 (2014) 46–61

25- Suárez-Vega, R., D.R. Santos-Peñate, P. Dorta-González & M. Rodríguez-Díaz, "A multi-criteria GIS-based procedure to solve a network competitive location problem", Applied Geography, No. 31, Pp. 282-291, 2011.

26- Tabari, M., A. Kaboli, M.B. Aryanezhad, K. Shahanaghi & A. Siadat, "A new method for location selection: A Hybrid Analysis", Applied Mathematics and Computation, No. 206, Pp. 598-606, 2008.

27- Wolpert, DH. and Macready WG. No free lunch theorems for optimization. Evolut Comput, IEEE Trans 1997; 1:67–82.

28- Worboys, M., “GIS:A Computing Perspective”, Bristol, PA: Taylor and Francis, 1995.

29- Yu, B., Z. Yang  & C. Cheng, "Optimizing the Distribution of Shopping Centers with Parallel Genetic Algorithm", Engineering Applications of Artificial Intelligence, No. 20, Pp. 215-223, 2006.

30- Zhang, L. & G. Rushton, "Optimizing the size and locations of facilities in competitive multi-site service systems", Computers and Operations Research, No. 35, Pp. 327-338, 2008.