ATM Deployment using Rank Based Genetic Algorithm

ATM Deployment using Rank Based Genetic Algorithm

Kulkarni Manjusha M.

Department of Computer Science and Engineering, Visveswaraya Technological University M.Tech-4th Sem, SJBIT, Bangalore, India

Abstract ATM is the most significant service provided by banking sector to the customers. Optimally deploying ATMs is very complex. The effective deployment of ATM depends upon ion present in the selected area and how much ATM service is utilized by customers. Genetic algorithms are used to solve such optimization problems using techniques such as inheritance, mutation, selection, and crossover. A banks decision to deploy ATMs should be logical as well as profitable which provide greater convenience and covering larger market area with maximum customers. The goal is to minimize the total number of machines but covering all the customer demands in the selected area. This study proposes a Rank Based Genetic Algorithm using convolution for solving the Banking ATMs Location Problem (RGAC).

RGAC is one of the ATM deployment strategy based on rank concept which gives high feasible solution in reasonable time. RGAC gives cost efficient allocation of ATMs and computing percentage coverage(PC Covering whole area ) which is high as it covers customers demands by maximizing the service utility of each machine .

KeyWords: Genetic Algorithms (GAs), Rank, Automated Teller Machines (ATM), Percentage coverage (PC), Client Utility matrix (CU), Service Utility Matrix (SU , Rank Based Genetic Algorithm using convolution (RGAC).

I.INTRODUCTION

ATM is an electronic banking outlet, which allows customers to complete basic transactions without the aid of a branch representative or teller. ATMs are scattered throughout cities, allowing customers easier access to their accounts. ATMs have become a competitive weapon to commercial banks whose objective is to capture the maximum potential customers. The fact is that commercial banks compete not only on the dimension of price but also on the dimension of location. ATM optimal Deployment Strategies offer the opportunity to provide greater convenience and to attract more customers by covering the money market with sufficient ATM facilities. These strategies also provide greater cost efficiency by finding optimal number of ATMs to be installed and greater profitability by increasing the ATM user base in order to earn much more transactions and

services fees as well as through the inflow of deposits from the depositors.

The location depends on the transactions demanded by the customer of proprietary ATM and non-proprietary ATM. A banks decision to deploy ATMs should be a rational Economic decision using the best ATM deployment strategy that takes into account the high computation complexities. This paper proposes a new Rank Based Genetic Algorithm for solving the banking ATM location problem using Convolution (RGAC) which outperforms the Heuristic Algorithm based on Convolution (HAC) algorithm that is inefficient while market size increases. (RGAC) increases the search efficiency by improving the evolutionary process while meeting a feasible solution. Moreover, RGAC has proved to be a robust approach for solving the ATMs deployment problem and is able to provide high quality solutions in a reasonable time.

The rest of the paper is structured as follows: Section II indicates some important related work RGAC.A detailed description of the problem encoding and specific operators are explained in Section III. Section IV explains about RGAC and VI section includes concluding remarks.

1. RELATED WORK

   The study [1] investigated placement of minimum number of ATM machines covering all customer demands in given geographical area. They have developed a heuristic algorithm to efficiently solve the optimal location problem of ATM placement by formulating a mathematical model.

   In this study, the problem of finding the minimum number of ATMs and their locations given arbitrary demand patterns is considered. They have considered one particular area and divided the parts of that accordingly such as area with no demand, high demand, and normal demand and so on with color code. Using the variables the placement problem is modeled.

   The study [2] presents the problem of WiFiDP (WiFi Network Design problem) grouping problem. A hybrid grouping genetic algorithm (HGGA) is proposed as a

   convenient method to solve such problems with providing a smaller and low cost connection service. The popularity of WiFi-enabled devices represents an enormous market potential for wireless networking services and mobile applications, based on this technology. The deployment of citywide WiFi access networks is a location problem as well as its a large assignment. In this case, the grouping genetic algorithm is combined with a repairing procedure, to ensure feasible solutions, and with a local search to improve its performance for the case of the WiFiDP. The grouping genetic algorithm (GGA) is a class of evolutionary algorithm specially modified to tackle grouping problems, i.e. scenarios in which a number of items must be assigned to a set of predefined groups. Thus, in the GGA, the encoding, crossover, and mutation operator of traditional GAs are modified, obtaining a compact algorithm with very good performance in problems of grouping.

   The study [3] investigate the ATM placement problem which is significant service provided by bank to customers. Many banks utilize ATMs to make cash withdrawal available to their customers at all times. They have formulated the ATM allocation problem as an optimization problem with mathematical model by considering various factors for deployment such as the price of buying or leasing an ATM, cost of deployment, cost of operation, and ATM characteristics to be deployed. .

   The study [4] determines cash management for ATM network. They have proposed one approach based on artificial neural network to forecast a daily cash demand for every ATM in the network and on the optimization procedure to estimate the optimal cash load for every ATM.. ANN are used for tasks such as pattern recognition, classification and time series fore-casting. The key to all forecasting applications is to capture and process the historical data so that they provide insight into the future. The primary objective of cash forecasting is to ensure that cash is used efficiently throughout the branch network. Cash fore-casting is integral to the effective operation of an ATM/branch network optimization procedure.

   The study [5] revolves around the grid computing environment where sharing computational resources, software and data take place at a large scale. However, the management of resources and computational tasks is a critical and complex undertaking as these resources and tasks are geographically distributed and a heterogeneous, dynamic in nature. They proposed a new Rank Based Genetic Scheduler for Grid Computing Systems (RGSGCS) for scheduling independent tasks in the grid environment by minimizing Makespan and Flowtime. The performance of the system can be evaluated by distributing number of resources across the networked computers.

2. PROBLEM FORMULATION

The ATM placement problem is modeled and defined mathematically. The variables used in modeling of the intended problem are shown in the table I. The optimization problem is organized in such a way as to realize market clearance.

In other words, the difference between CU and SU should be minimized. This difference can be expressed mathematically in equation 1:

E = SU CU (1)

Where E is the difference matrix of sie(I×J) after assigning total number of machines, SU is service utility matrix.

1. Client Utility Matrix CU:

   Any exercise to optimize the deployment of ATMs must start with a thorough understanding of the customer base and identification of the priority of the customers .The generation of CU is made by following these procedures:

   • The first step is to categorize people based on where they live, where they work and where they may need money in order to make payment for shopping and other transactions. The science of grouping of the people in a geographical area according to socioeconomic criteria is known as Geo- demography. The Commercial Geodemography has been used to target ATM services to the Banks clients based on their lifestyle and location. In this study the geo-demographic approach is used by conducting a survey on potential Customer as well as geographical, demographic, economic, and traffic data. Other considerations include safety, cost, convenience, and visibility.

   Quite often, malls, supermarkets, gas stations, and other high-traffic shopping areas are prime locations for ATM sites. In this paper, the priorities for different potential ATM locations will be implemented based on a priori analysis of all the applicable factors. Using SPSS program , the related data are entered. The variables used are Customers Age, income, Education and Marital Status which constitute the demographic and economic factors. The traffic data are represented by a variable such as the location importance which encompasses factors like number of residents, number of public institutes, number of private institutes and the state of street whether it is main street, by-street or crossroad.

   The procedure now is to compute the mean value of these variables for each customer then we segment the customers according to their areas and compute the cumulative mean value for customers belonging to each respective segment. Each cumulative mean value represents one element in G(x×y) matrix. The elements of G(x×y) range from 0 to 10.when The element g(x×y) is high means that there are more number of potential customers in that area, in contrast, when g(x×y) is small means less number of potential

   customer are there. Generate sub-matrices (cur), the matrix of cur is presented in equation 2 and Figure 1:

   cur = G(x×y) × U(m×n) × 10 (2)

   Figure 1. Cur Matrix.

   Where: r = 1, 2 (m× n) (I× J) . U(m×n) is the degradation of Client Utility, by assuming m =3, n=3, U(m×n) is given in figure 2:

   Figure 2: Degradation of client utility matrix

   CU matrix can be obtained by replacing each element in G(x×y) by its corresponding matrix cur as in Figure 3.

   Figure 3. Client Utility Matrix CU.

   The reason behind calculating cur is that, cur will be strongest at the center of the areas, and it will degrade as one moves away from it.

2. Service Utility Matrix SU:

Once the deployment of ATMs is a one off project, hence it is done once. It is essential to distribute the limited number of atms in such a way as to maximize the utility of services. In order to find SU, this study assumes that ATMs are homogeneous, in line with this there exists only one matrix

A. Matrix A (represents the degradation of ATMs utility as one moves away from its location) is predetermined and held constant for all machines. The rectilinear distance model is adopted as shown in figure 4.

Figure 4. Service Matrix A (The rectilinear distance model)

The matrix Ln indicates the location of the nth machine. If this location is denoted by the coordinates (un,vn) then all elements of Ln are equal to zero except for coordinates (un,vn) where they are equal to one as in the equation 3 and figure 5.

The matrix SU can be obtained from the convolving of two matrices A and L as in equation 4 and figure 6. Notice that the objective of the convolution here is to surround the unique non-zero element in Ln with the service pattern matrix

A. Therefore, the convolution operation in this case can be performed very efficiently by simply centering the elements of the A matrix at (un, vn).

SU = A * L (4)

Where: the symbol * indicates the convolution product.

C. Percentage Coverage (PC):

In order to satisfy the client, his Utility should be satisfied by covering his demand, and the Service Utility should be maximized through effective deployment of ATMs, this will save the cost of providing additional ATM. PC is computed as the percentage of ( is equal to one in all points in E that have SU greater than CU) divided by the number of elements in E. PC is given as in equation (5):

Where is given in equation ( 6):

In addition to PC, another important measure (the total Client Utility satisfied ) is calculated. The formula of is given in equation (7):

The algorithm returns both and PC values with the solution as will be shown in the simulations section. PC and values

are essential in measuring the goodness of deployment of ATMs.

The value of g ranges between [0, 1] and it approaches one only when all elements in E are zeros or positive values, denoting the saturation level of Client Utility. In order to deploy less number of ATMs without affecting negatively on PC and if the value of PC is equal to hundred (100), then next step the number of ATMs is reduced by one, the trial continues reducing N as long as PC is within the acceptable limit (i.e. more than the lower limit 99). Otherwise when the value of PC is less than the acceptable limit, then trial increases number of ATMs till PC reaches the acceptable limit. The previous conditions are presented in equation 9:

Where: k = 1, 2

V. RANK BASED GENETIC ALGORITHM FOR SOLVING THE BANKING ATMS LOCATION

PROBLEM (RGAC)

GA is used to solve optimization problems by imitating the genetic process of biological organisms. A potential solution to a specific problem may be represented as a chromosome containing a series of genes. A set of chromosomes makes up the population. By using Selection, Crossover and Mutation Operators, GA is able to evolve the population to generate an optimal solution.

1. Chromosome Representation

   The efficiency of GA depends largely on the representation of a chromosome which is composed of a series of genes.

   Here each gene represents an ATM location which is equal to one or zero based on binding of the ATM to its location as in equation 3. As a result, L represents the chromosome. Population Initialization is generated randomly.

2. Fitness Equation

   A fitness equation must be devised to determine the quality of a given chromosome and always returns a single numerical value. In determining the fitness equation, it is necessary to maximize the Percentage Coverage PC of CU. RGAC takes the PC value as a fitness equation for a given chromosome, which presented in equation 5.

3. Evolutionary Process

   Evolutionary process is accomplished by applying Rank based Roulette Wheel Selection (RRWS). Crossover and mutation operate from one generation to the next. Selection Operator determines how many and which individuals will be kept in the next generation. Crossover Operator controls how to exchange genes between individuals, while the Mutation Operator allows for random gene alteration of an individual. Besides the standard genetic operators discussed above, the Elitism Phase is used to preserve the best candidates. These

   stages are discussed in details as below. Firstly, in order to carry out the RRWS, the Relative Probability (shown in equation 14) and cumulative proportion of each chromosome are calculated.

   Pi = Rank (fitness); (14)

   After that, one-Point Crossover and Mutation Operators, the algorithms (1, 2) are applied to the chromosomes from the selection phase. Mutation Operator runs through the genes in each of the chromosomes and mutates each gene according to a Mutation Rate Pm. Finally, Elitism combines the parent popultion with the modified population (the candidates generated by Crossover and Mutation Operators), and takes the best chromosomes to the next generation. The purpose of this phase is to preserve the best chromosomes from being lost. After this phase, the algorithm continues to the next iteration. RGAC is presented in the algorithm 3.

4. Performance Analysis

   RGAC needs to execute some hundreds of iterations to come up with an optimal solution. However, the shortcoming of HAC is convergence to a local optimum. According to the simulation results, it is proved that RGAC is effective in speeding up convergence while meeting a feasible result. Also RGAC outperforms HAC, in the PC and g values to obtain the final schedule.

   Algorithm 1 One point Crossover

   1: for i=1 to popSize/2 do

   2: Select two chromosomes p1, p2 randomly 3: Select Crossover point Point randomly

   4: Save coordinates of ATM locations of two chromosomes p1, p2 in row1, col1, row2, col2.

   5: if random [0, 1] probCrossover then

   6: for k=Point+1: ChromosomeLength do

   7: Swap the coordinates of ATM locations of T two chromosomes p1, p2

   8: end for

   9: Keep the newly produced chromosomes as candidates 10: end if

   11: end for

   Algorithm 2 Mutation

   1: for i=1 to popSize do

   2: Select chromosome p randomly

   3: Save coordinates of ATM locations of chromosome p in row, col

   4: if random[0,1] probMutation then

   5: Select one ATM location of chromosome p randomly and make it equals to zero

   6: Generate one ATM location of chromosome p

   randomly and make it equals to one

   7: add the newly produced chromosomes as candidates

   8: end if

   9: end for

   RGAC Algorithm

   1: Generate Initial Population P of size N1 randomly.

   2: Evaluate each chromosome using equations (1,5 and 7) 3: for g 1 to MaximumGenerations do

   4: Generate offspring Population from P 5: Rank based Roulette Wheel Selection

   6: Crossover and Mutation algorithms (1,2)

   7: Evaluate each chromosome resulting from Crossover and Mutation stages using equations (1,5 and 7)

   8: (Elitist) Select the members of the combined population based on minimum fitness, to make the population P of the next generation.

   9: Evaluate each chromosome using equations (1,5 and 7)

   10: if stopping criterion has reached then

   11: return PC, g values and best ATM Location Matrix L found;

   12: break;

   13: end if

   14: end for

   RGAC is effective in speeding up convergence while meeting a feasible result. The fitness equation gives very good results and high quality solutions, even though the complexity of the Problem increases.

   VI RESULT AND ANALYSIS

   After generating random population and deploying possible number of ATMs, the numbers of machine placed are more but applying is RGAC the ATMs placed (shown with 1 and 0 indicated ATM is not placed) at the points where the percentage of population is more as well as the ATM machine is fully utilized.

   1. Result of ATM machine random population

   2. Result of ATM machine deployment with applying RGAC

VI CONCLUSIONS AND FUTURE WORK

This paper presents the RGAC technique, for deploying ATMs in the Banking world, which increases search efficiency by improving the evolutionary process while meeting a feasible result. Moreover, RGAC has proved to be a robust approach for solving the ATMs deployment problem and is able to provide high quality solutions in a reasonable time as compared to HAC. The simulation results show that, RGAC solves the optimization problem of ATMs deployment by maximizing PC and minimizing N, thus RGAC matches the two objectives of banks, namely, attaining the highest client utility as well as improving the cost efficiency of the banks. In the future, it is appropriate to extend the goodness of results by including other measures like variance or standard deviation in order to obtain less dispersion in matrix E.

REFERENCES

1. M.A. Aldajani and H. K. Alfares, Location of banking automatic teller machines based convolution, Comput. Ind. Eng., vol. 57, no. 4, pp.11941201, 2009.

2. Figueras, and M. Solarski, A hybrid grouping genetic algorithm for citywide ubiquitous wifi access deployment, in CEC09: Proceedings of the Eleventh conference on Congress on Evolutionary Computation. Piscataway, NJ, USA: IEEE Press, 2009, pp. 21722179.

3. A. Qadrei and S. Habib, Allocation of heterogeneous banks automated teller machines, in INTENSIVE 09: Proceedings of the 2009 First International Conference on Intensive Applications and Services. Washington, DC, USA: IEEE Computer Society, 2009, pp. 1621.

4. L. B. J. F. P. D. Rimvydas Simutis, Darius Dilijonas, Optimization of cash management for ATM network, in Information Technology and Control, 2007.

5. A.J. S. R. Wael Abdulal, Omar Al Jadaan, Rank based genetic scheduler for grid computing systems, in The International Conference on Computational Intelligence and Communication Networks (CICN 2010).IEEE, 2010.

6. Alaa Alhaffa and Wael Abdulal, A Market-Based Study of Optimal ATMS Deployment Strategy, International Journal of Machine Learning and Computing, Vol.1, No. 1, April 2011.

7. Omar Al Jadaan, Lakishmi Rajamani,3C. R. Rao , Improved selection operator for ga, Journal of Theoretical and Applied Information Technology, 2005 – 2008 JATIT.

8. Rakesh Kumar, Senior Member, IACSIT and Jyotishree, Member, IACSIT, Blending Roulette Wheel Selection & Rank Selection in Genetic Algorithms, International Journal of Machine Learning and Computing, Vol. 2, No. 4, August 2012.

9. D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. New York, NY: Addison-Wesley, 1989.

10. M. Wagner, The optimal cash deployment strategy modeling a network of automated teller machines, thesis in Master of Science in Accounting, Hanken- Swedish School of Economics and Business Administration, 2007.