Solve Location Allocation Problems Using Genetic Algorithm Computer Science Essay

Locating a facility into the best place is a decision making problem. The best place depends on criteria like the optimal distance, the capacity of the facility, population density, optimal cost etc. Facility allocation can be based on one criterion like optimal distance or adding various combinations of criteria like optimal distance and capacity of the facility together or capacity of the facility or optimal cost together and so on. So, the goal of the location allocation problem’s solution is to find the best location or locations to fit one or more facilities which will make the highest utility value from one criterion or multiple criteria.

Solution of this problem is important for the decision makers. They need decision support tool which will locate the facility based on the criteria. These criteria can also be divided into GIS type (spatial) and nonGIS type (aspatial). GIS type can be like shortest path from location, shortest time in the routing path etc. For example in market facility NonGIS type can be food market, supermarket, pizza shop etc. NonGIS type criterion can also be significant in decision making for example if a pizza shop already exist in certain location then decision maker may not be interested to put another of same type.

Bad location of the facility has negative effect to provide services to the beneficiary. Distance from the area of supply and the area of demand should be optimal. If location of the facility is far from populated area (area of demand) beneficiary may not be able or interested to take the service from that facility. This type of facility can be school, hospital, market, hospital, fire service etc. The capacity of the facility also has effect to provide the service. When facilities are created to meet the demand of people, capacity of the facility cannot be ignored. Therefore, the location of the facility should be well distributed such that capacity of the facilities can meet all the demand. So with optimal distance, capacity of the facility needs to be considered in the time of taking decision. Sometimes facility needs more space to extend the capacity (e.g. extending for 500 persons to 1000 persons) or to build connecting facility (e.g. High school with primary school). So considering extended demand, the location for facility should have more space. In that case, allocating location of contiguous space becomes necessary.

Location allocation was studied in various researches to locate facilities like markets, waste dumping places, parks, land for agricultural purposes, ambulances etc. into the best places in order to achieve maximum benefit. The facilities were located into new optimal locations in almost all of the studies. In some of the studies [1-3] , facilities were located with respect to the demand for the facility. In other studies, multiple facilities were located as points in the map [4-8] whereas single facility was located as an area in different researches [9, 10]. Multiple facilities with area allocation did not get enough attention.

Li and Gar-On Yeh [4] mentioned that according to Church, readjusting the facilities considering the existing ones such that the facilities can compete with competitive facilities considering competitive facilities’ location is a competitive location allocation problem. But this problem allows closing of existing facilities [11], hence, this will not be suitable for all facilities like school, hospital etc. Existing network facilities may not need to be relocated in optimal locations. Finding optimal locations of new facilities considering existing facilities is much realistic approach. But in almost all of the studies, the consideration of existing network was deprived in the location allocation problem formulation.

Commercial ARCGIS software has also implemented location allocation problem in the extension of network analyst [12]. It is tightly coupled and has strong visualization that shows the output result. But this commercial software only deals with single objective location allocation problems. For example, finding the locations that can reduce the overall transportation costs of delivering goods to outlet is one single objective type problem. Another single objective type is to find the maximum coverage from the location of police station, fire station, emergency rescue center etc. Their black box implementation doesn’t allow any customization and development of these problems. It cannot deal other type of complex location allocation problems. Traditional deterministic methods also cannot deal complex location allocation problems. So, heuristic approach is necessary.

One of the heuristic approaches of solving location allocation problem is genetic algorithm (GA) which was first addressed by Hossage and Goodchild [13]. They identified implicit parallelism as the reason of good performance of genetic algorithm. Implicit parallelism identifies and preserves common components between individuals of GA that make better performance. There were also some comparisons among GA and other similar heuristic methodologies like simulated annealing, tabu search or neighborhood search [4, 14]. In this researches, the authors inferred that GA can improve solution to near global optimal quickly. The performance of GA doesn’t depend on simple assumption unlike neighborhood search and GA is faster than simulated annealing.

In this context, this study is motivated towards the solution of location allocation problem by using GA in order to locate the area of the facilities with optimal distance from population density, considering capacity and existing network of the facilities. So, optimal solution for this problem considering these criteria will help the decision makers to make the choice.

2. Research identi¬cation:

2.1 Research objectives:

My main research objective is to solve location allocation problems using GA through a case study of school as facility in the city of Enschede. To achieve the research objective the whole objective is divided into four sub research objectives. By completing these sub research objectives step by step I want to finally achieve the entire research objective. Comparing and analyzing GA with other methodology like location allocation by agent based or simulated annealing or tabu search method will be the final phase of my research objective.

The sub research objectives are as follows:

To determine optimal facility locations considering existing network in GA.

To implement contiguity for multiple facilities in GA.

To put into action capacitated location into GA.

To compare GA with other methodologies.

2.2 Research questions

Each sub research objective brings one or more research questions. From first sub research objective the following question can be derived:

How to prepare and process GIS data for GA to find optimal location for new facility allocations that can cope with existing network in GA?

From the second research objective the following research question can come out:

How can GA handle implementing area (contiguity) for multiple facilities?

From the third sub research objective the next question can be forwarded:

What will be the objective function of GA to apply capacitated facility in order to get optimal location considering existing network?

For achieving the last sub research objective in order to analyze and evaluate the formulated problem by GA, firstly GA needs to be optimized. Then after optimization of GA, it can be compared with other methodologies. At this stage the research questions that can be originated are given as follows:

When can GA be optimized implementing all the criteria?

What are the strengths or weaknesses of GA in this problem context with compare to other methodologies?

2.3 Innovation aimed at:

The innovation relies on the holistic view and extensive test of GA for a variety of location allocation problems of growing complexity. Hence network, contiguity and capacity of the facility will gradually be implemented by GA to solve location allocation problem. Finally, GA will be compared with other methods to identify its strengths and weaknesses

2.4 Method adopted:

The method which will be applied here is genetic algorithm (GA). GA is a heuristic search and optimization algorithm which always uses the best solutions from each generation. Like biological evaluation GA forwards the best solutions toward the optimal solution. GA replicates the process of genetic mutation, selection and cross over in biological evolution.

Figure 1 depicts how the methodology will be adopted with GA. Data should be processed and made ready as input format to feed into GA. Then initial population for the solutions will be generated taking consideration of existing network of facilities in each individual. Each population will be assessed through fitness assessment by fitness function. Optimal distance from the facility, capacity of the facility and contiguity of the facility will be assessed in this step. Initially these will be assessed separately. Then these can be assessed altogether for the formulated problem by increasing the complexity gradually. So, fitness assessment step performs the fitness test of the individuals. It determines which of the existing individuals will be eliminated or replaced by the offspring of the higher fitness from the reproductive step.

Figure 1: Methodology to be adopted with Genetic Algorithm

The new generation will continue the same steps like their parents until the best fit can be found in the population. This process will be stopped when best solution will be found. Best solution means the combination of the individuals with highest fitness value in the population. Optimization of GA may be done by the modification of the fitness function with respect to formulated problem.

Why this method?

Multiple objectives, multiple sites and multiple constraints in spatial context can make the location allocation problem more complex. Traditional methods cannot deal highly complex problem due to high computation. In the study [4], the authors mentioned that according to Openshaw, applying deterministic method is not feasible because of its extreme computational time to solve this problem. So, heuristic approach is needed to solve this problem. There are other’s heuristic geocomputational methods like simulated annealing, tabu search and neighborhood search which can also be applied in complex spatial decision problem.

Very few studies have been conducted to evaluate geocomputational methods for location-allocation problem. In one research [14] there is comparison among simulated annealing, tabu search and GA for different types of location allocation problem. The authors inferred that GA was better than others to extract more information from fewer solutions. It seems to improve solution quite rapidly. However, for the unrestricted evaluation of the candidate solutions (individuals in GA) the performance of other methods may be better. But since in my research I’ll use restricted evaluation, performance of GA will not be hampered.

In another research [4] GA performance is superior to neighborhood search and simulated annealing. They urged that neighborhood search can only perform better under simple assumption and it cannot guarantee that the search result will be optimal. They also showed that GA performs much faster than simulated annealing. For these reasons, I’ll apply GA method in my research to solve location allocation problem.

2. Literature Review:

An extensive literature review to provide idea about previous researches of location allocation and different type of solutions is carried out. The objective is to understand the terms and trends in location allocation problem and solutions. Location allocation is a problem which is under research almost for a century (started from Weber’s location allocation problem 1909). Now-a-days the LA problem has grown with lots types and classification. The combinations of different classification have made the problem more complex and hence the techniques of solution. This chapter will investigate all such researches and will discuss the pros and cons and try to find the gap where much light of research were not shed.

2.1 Facility, demand, space in location allocation.

There is abundant usage of some terminologies in Location allocation literature.

Before going into details in literature review some terminologies should be explained. Facilities, location and customers or demands are referred as basic components of location allocation problems by Azarmand et. al. [15]. In various location allocation problems COMponents may differ and play a role to typify that location allocation problem. The following description has an influence by the authors.

2.1.1 Facility

Facilities can be divided depending on number of the facilities, capacity of the facilities, or number of services.

Single (source) or multi (source) facilities

Single facility or multi-facilities depends on the number of the facility used in the problem. In single source/facility, only one new facility will be used or established whether in multi source/facilities more than one facility are located.

Capacitated or uncapacitated facility

Facility can also be classified as capacitated and uncapacitated considering how much demand facility can meet. If facility can supply an infinite demand then it is uncapacitated and when facility’s capacity of supply is limited then it is capacitated.

Single or multi services

Facility can also be classified depending on number of services it is providing. A facility can provide only one type of service or multiservice.

2.1.2 Demand

Deterministic or Stochastic:

The demand of the customer can be either deterministic or stochastic. In case of deterministic the demand are known while it is used into the model. In case of stochastic, demand of customer becomes probabilistic into the model.

2.1.3 Space

There are three types of representation of space in location allocation problem. These are discrete, continuous and network.

Discrete

In discrete space model, it is assumed that we have prior knowledge of the candidate sites. It is also referred as site selection model.

Continuous

Continuous space model actually generates appropriate site as output. It is also known as site-generation model.

Network based

The network-based model is defined as network either with continuous or discrete space model. Links of network are considered as a continuous set of candidate locations. In network with discrete model, new facilities are placed only in the nodes.

2.1. Classification by Brandeau, Murray Church and integration of models:

A more extensive classification is done to distinguish location allocation researches up to 1989 year by Brandeau and Chiu [19]. They tried to provide an overview of major problems in location allocation and briefly describe different types and how they relate to one another. They reviewed more than 50 location allocation model including standard problems such as the median, center, and warehouse location problems, as well as less traditional problems up to year 1989. They derived all the classification through objective, decision variables, system parameters. Classification through objective was based on optimization of some values through objective function and non-optimization types. Classification through decision variables was based on facility, location service area, number of servers or facilities etc. System parameter type classification was based on topological structure, travel metric, travel time/cost, demand etc.

Location allocation problem is also classified by Murray[20]. According Murray classification becomes more complex what it seems now-a-days. Unlike Brandeau and Chiu he has added some other classification based on all the factors from input to output of location model, its objective and focus.

Church (1999) identifies four general classes of location models which are median, covering, capacitated, and competitive[5]. Median models consider that the average distance from any user to their closest facility is minimized by locating fixed number of facility. By the number of facility median models can divided into more classes which are 1 median and p- median. Covering models involves covering the maximum population by locating n facilities. Capacitated models consider the capacity of each facility with respect to demand. Competition models help the decision maker to consider other’s competitive facility location and readjust own facilities. According to Church the recent trend is integrating multiple facility models, for example p-median and maximal covering.

Integrating different location allocation model makes the model more realistic and as well as more computationally burdensome or complex. So in order to reduce the tradeoff between these two a balance should be made to depict reality and handling complexity in the location allocation problem.

Since we are dealing only p median in the next seciotn p-median, LRP

2.1 P-median Location allocation Researches and Reality

Location-allocation (LA) is a problem of locating a set of new facilities in order to maximize or minimize distance from facilities to customers is and an optimal number of facilities have to be placed in an area of interest such that it satisfies the customer demand [15]. Alfred Weber is considered as father of location allocation problem according to Ghosh and Rushton [16]. Weber did locate a single warehouse by minimizing the total travel distance between the warehouse and a set of spatially distributed customers according to Brandeau et. al. [17]. Weber problem was extended from single warehouse (facility) to multiple supply points (facility) by another research of Cooper[18] in 1963 which was a p-median location allocation problem. If p is equal to 4(p=4) then p-median means 4-median problem which searches the locations of 4 supply centers for optimal aggregate distance from a set of demand points. In Cooper’s problem, multiple supply centers or facilities are sited in continuous space and discrete demand is allocated to a facility.

Using real life data is a challenge for location allocation problem. In some of the past researches, facilities, demands were used through nodes or continuous space. In network based location allocation problem, graph network is used in many literatures. Hakimi[19] considered facilities sited as nodes in the graph network. So his optimal solution of p facilities will consist of only nodes in the graph network. In his model, demand is discrete and optimal solutions of facilities are also discrete. Similarly in the facility location solved by Hossage[13], a network of discrete nodes were used for facilities and demands. Discrete nodes for facility or demand are also used by Gong et. al. [1, 3], Correa et. al. [20], Uno et. el. [21], Medaglia et. al.[6], Yang et. al. [22].

Instead of node as network, in some studies continuous space was used to locate optimal facility. Continuous space was comprised of cells in a study by Li et.al. {Li, 2009 #30} where the freedom of choosing facility from any cell also support continuity. Facility can be located anywhere in the continuous space and will not depend on points according to Neema et. al.{Neema, 2010 #38}. Though Neema et. al. used GIS data but they also did not consider their solution

In above all study demand and facility is used, distance between these two were considered as straight line. Road network was not considered.

In GIS Road network

synthetic data(data produced in randomly in rectangular or square )

However in location allocation problem, road network is still not used.

Misconception of Location routing problem and location

Allocation problem

2.4 Location allocation, Location routing and GIS Network

Location routing problem fix the route based on location of facilities and Location allocation problem locate facilities based on distance or sometimes shortest path between facility and demand. Location routing problem differs with traditional location allocation problem in the distance between facility and demand. For location routing the distance is considered as visit of customer or supplier to the facility through tour. For traditional location allocation distance is considered as straight line or radial trip from the facility to the customer or supplier. Therefore, the classical location allocation problem ignores route by network when locating facilities [27].

Route can be adopted in the location allocation problem. It can be one of the criteria in location allocation problem. One of GIS approaches which considers road network as one of the input of location allocation problem is done by Li [4]. But road network is used to calculate proximity not to calculate shortest path. Similarly Sasaki et al.[8] also did not use road network in their input. Classical p-median always considers nearest distance as straight line or Euclidian distance between demand and facility. Very few research papers in location allocation that used GIS, considered road network in their model by any means. But no model from GIS so far used shortest path from road network into location allocation model. Hence the concept of tour from location routing model can be absorbed as shortest path in the location allocation model.

But in the classical location allocation problem when facility is providing service like school, hospital, market it is always assumed that students, patient or customer will go to the nearest facility. In reality, facility may not be always the nearest one. Some of the facility may be chosen according to its type (i.e. specialized hospital; school depending on medium or religion, market based on commodity etc.). So demands for facility should be stochastic rather than deterministic and some of the demands may not be used for nearest facility location.

Genetic Algorithm in Location Allocation:

This was a single objective problem. Hossage and Goodchild [13] used a genetic algorithm to solve the p-median problem. Their goal was to locate p facilities in a spatial network of n nodes such that the total distance between each node and its closest facility is minimized.

An improvement of single objective p-median problem is to apply multiple objectives with it. In the multiple objectives capacities, optimal distance, optimal cost etc. can be combined. Multiple objectives were also solved by using GA in a research for locating multiple facilities with three objectives like maximizing the population coverage, minimizing the total transportation costs and minimizing the proximity of the road [4]. Now even if the new locations have been allocated as the optimal and hence the best ones, these locations may not be feasible if the optimal location falls over obstacles [3] like water-body, existing buildings etc.

Market locations with the lowest transportation cost to the nearest market where the crops can be sold at maximum price was solved in one study [5] which also addressed multiple objectives by GA. In another study [6], waste dumping locations were allocated with a low cost operating network and maximum distance from population living area. Minimizing the distances from parks to highly populated areas, highly air polluted areas, noisy areas and areas without parks were considered to find parks’ locations [7]. Another research [8] was about locating 27 ambulances in 35 locations such that shortest distances from main road network weighted by emergency case number from small area to the nearest potential ambulance location were maintained. All the three researches [6-8] also deal with multiple objectives through GA method.

However, a hybrid evolutionary method was used in location allocation problem which dealt with the capacity of the facility [1]. But the facility was assumed as one cell. In addition, the problem space was not spatial but simulated from random number. In spatial context, an improved genetic algorithm with Hilbert curve was used for capacitated facilities [2]. But in both cases [1] [2] contiguity of cells in the facility was not considered. Some types of facility location problem were compared using GA in a study [23] where the performance of capacitated facility problem’s solution was not good. Its computational time was much higher. But the approach of genetic algorithm with Hilbert curve [2] was faster in capacitated facility location problem.

Some authors [8] introduced optimal solution for minimal distance considering the amount of demand. But they didn’t consider the capacity of the service center when at the same time they were considering the demand at each location. GA has sensitivity in weight of the parameters. Some authors [4] also used weight of the parameters but didn’t mention any methodology of how to take weight and which weight would possibly be the best for GA as optimization. Moreover, they did not deal with contiguity of the optimal facility as area. They assumed that facility will be located as one point in map. In some other contexts [9, 10, 24] [25], though contiguity of the optimal facility was considered as area the capacity of the facility was not considered with the problem.

2.3 land allocation:

As one of the multiple objectives, the concept of using contiguity of cell (area) was applied with GA by Brookes [9, 10] but the concept is applied in land allocation not in facility allocation. He used region growing approach of image processing to grow region of contiguous cells from seed cell. But he only considered single land of contiguous cells as optimal solution. An improvement of Brookes’ research was done for generating alternatives of optimal solutions from GA which considers not only contiguity of cells but also multiple land allocation [25]. An agent based model [24] was also used for optimal land allocation using contiguous cells for each optimal allocation of land like the study [25]. Stewart[26] also used GA in order to integrate with land use planning decision support system. He achieved the solution for maximizing the natural value of the area, for maximizing the recreational value of the area and for minimizing the cost of changing land use. The concept of allocating land can be absorbed in the facility allocation. Because almost all results of facility allocation research considers point rather than area.

2.5 Location allocation and ARCGIS:

The ARCGIS[12] location allocation analysis layer offers only six different problem types to answer specific kinds of questions which are minimize impedance, maximize coverage, minimize facilities, maximize attendance, maximize market share and target market share. Classical location allocation problem like p-median problem is same as minimal impedance where in both case the objective is to minimize the sum of distances from demand points to facility. All the problems considered uncapacitaed facility which may not be practical in some types like school, hospital etc. Straight line distance is used in the output where presence of network was not considered and was totally absent. All the facilities were point in the map. There is no consideration for facilities as area. All the demand points were aggregated to the centroids of location. Using separate demand point for each demand is not possible in ARCGIS while separate demand point is used in some past researches as mentioned by Church[28]

2.6 Solutions of location allocation problem:

Exact

Hueristic

Metahueristic