Solve Location Allocation Problems Using Genetic Algorithm Computer Knowledge Essay

Locating a center in to the best place is a decision making problem. Where depends on standards like the perfect distance, the capacity of the facility, population density, ideal cost etc. Center allocation can be based on one criterion like best distance or adding various combinations of conditions like optimal distance and capacity of the service together or capacity of the facility or optimal cost jointly etc. So, the purpose of the positioning allocation problem's solution is to find the best location or locations to fit a number of facilities which will make the highest power value in one criterion or multiple requirements.

Solution of this problem is important for the decision creators. They want decision support tool that may locate the center based on the criteria. These criteria can also be divided into GIS type (spatial) and nonGIS type (aspatial). GIS type can end up like shortest avenue from location, shortest amount of time in the routing way etc. For example in market facility NonGIS type can be grocery store, supermarket, pizza shop etc. NonGIS type criterion may also be significant in decision making for example in case a pizza shop already are present in certain location then decision maker might not be interested to put another of same type.

Bad location of the service has negative result to provide services to the beneficiary. Distance from the region of supply and the region of demand should be optimum. If location of the facility is far from populated area (portion of demand) beneficiary might not be able or interested to take the service from that center. This type of facility can be school, hospital, market, medical center, hearth service etc. The capacity of the service also has result to supply the service. When facilities are created to meet the demand of people, capacity of the facility cannot be overlooked. Therefore, the location of the center should be well distributed in a way that capacity of the facilities can meet all the demand. So with optimum distance, capacity of the facility needs to be looked at in the time of taking decision. Sometimes center needs more space to extend the capability (e. g. extending for 500 individuals to 1000 folks) or even to build connecting facility (e. g. Senior high school with primary institution). So considering expanded demand, the positioning for facility should have more space. If so, allocating location of contiguous space becomes necessary.

Location allocation was analyzed in various researches to find facilities like market segments, waste products dumping places, parks, land for agricultural purposes, ambulances etc. in to the best places in order to achieve obtain the most. The facilities were located into new optimum locations in the vast majority of the studies. In a few of the studies [1-3], facilities were located with regards to the demand for the service. In other studies, multiple facilities were located as details in the map [4-8] whereas solo center was located as a location in different studies [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 contend with competitive facilities considering competitive facilities' location is a competitive location allocation problem. But this issue allows final of existing facilities [11], hence, this will never be suited to all facilities like institution, clinic etc. Existing network facilities may not have to be relocated in optimal locations. Finding optimal locations of new facilities considering existing facilities is a lot realistic approach. But in almost all of the studies, the account of existing network was deprived in the positioning allocation problem formulation.

Commercial ARCGIS software has also executed location allocation problem in the expansion of network analyst [12]. It really is tightly coupled and has strong visualization that shows the output effect. But this commercial software only handles one objective location allocation problems. For example, finding the locations that can decrease the overall travelling costs of providing goods to store is a unitary objective type problem. Another sole objective type is to find the maximum coverage from the location of police place, fire station, disaster rescue middle etc. Their dark box implementation doesn't allow any customization and development of the problems. It cannot offer other type of complicated location allocation problems. Traditional deterministic methods also cannot package complicated location allocation problems. So, heuristic way is essential.

One of the heuristic methods of solving location allocation problem is hereditary algorithm (GA) that was first addressed by Hossage and Goodchild [13]. They discovered implicit parallelism as the reason of good performance of hereditary algorithm. Implicit parallelism identifies and preserves common components between people of GA that make better performance. There were also some comparisons among GA and other similar heuristic methodologies like simulated annealing, tabu search or community search [4, 14]. In this researches, the authors inferred that GA can improve method for near global optimal quickly. The performance of GA doesn't rely upon simple assumption unlike neighborhood search and GA is faster than simulated annealing.

In this framework, this study is determined towards the solution of location allocation problem by using GA to be able to locate the area of the facilities with maximum distance from human population density, considering capacity and existing network of the facilities. So, maximum solution because of this problem considering these requirements will help the decision makers to help make the choice.

2. Research identication:

2. 1 Research targets:

My main research target is to resolve location allocation problems using GA through a case study of institution as service in the city of Enschede. To achieve the research objective the whole objective is split into four sub research goals. By concluding these sub research objectives detail by detail I want to finally achieve the whole research objective. Evaluating and analyzing GA with other technique like location allocation by agent structured or simulated annealing or tabu search method will be the final period of my research objective.

The sub research objectives are the following:

To determine best service locations considering existing network in GA.

To put into practice 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 a number of research questions. From first sub research goal the following question can be derived:

How to get ready and process GIS data for GA to find best location for new service allocations that can handle existing network in GA?

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

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

From the 3rd sub research purpose the next question can be forwarded:

What will be the objective function of GA to use capacitated facility to be able to get optimal location considering existing network?

For obtaining the previous sub research goal in order to analyze and evaluate the developed problem by GA, firstly GA needs to be optimized. Then after search engine optimization of GA, it could be compared with other methodologies. At this stage the study questions that can be originated are given the following:

When can GA be optimized employing all the standards?

What will be the strengths or weaknesses of GA in this problem framework with compare to other methodologies?

2. 3 Development aimed at:

The innovation depends on the all natural view and extensive test of GA for a number of location allocation problems of growing complexity. Hence network, contiguity and capacity of the service will little by little be implemented by GA to resolve location allocation problem. Finally, GA will be compared with other methods to identify its talents and weaknesses

2. 4 Method adopted:

The method which is applied here is genetic algorithm (GA). GA is a heuristic search and marketing algorithm which always uses the best solutions from each technology. Like biological analysis GA forwards the best alternatives toward the perfect solution. GA replicates the procedure of hereditary mutation, selection and cross over in biological evolution.

Figure 1 depicts how the strategy will be implemented with GA. Data should be processed and made ready as type format to feed into GA. Then initial human population for the solutions will be made taking account of existing network of facilities in every individual. Each inhabitants will be evaluated through fitness diagnosis by fitness function. Optimal distance from the service, capacity of the facility and contiguity of the facility will be evaluated in this task. Initially these will be evaluated individually. Then these can be assessed completely for the formulated problem by increasing the complexity eventually. So, fitness analysis step works the fitness test of the individuals. It establishes which of the existing individuals will be removed or substituted by the offspring of the higher fitness from the reproductive step.

Figure 1: Strategy to be followed with Hereditary Algorithm

The new technology will continue the same steps like their parents until the best fit are available in the population. This process will be discontinued when best answer will be found. Best solution means the blend of the individuals with highest fitness value in the populace. Search engine optimization of GA may be done by the adjustment of the fitness function with respect to formulated problem.

Why this technique?

Multiple objectives, multiple sites and multiple constraints in spatial framework can make the positioning allocation problem more technical. Traditional methods cannot offer highly complicated problem anticipated to high computation. In the analysis [4], the authors brought up that regarding to Openshaw, making use of deterministic method is not feasible because of its extreme computational time to solve this issue. So, heuristic methodology is needed to solve this issue. You can find other's heuristic geocomputational methods like simulated annealing, tabu search and neighborhood search which can be applied in complex spatial decision problem.

Very few studies have been conducted to evaluate geocomputational methods for location-allocation problem. In a single research [14] there may be contrast among simulated annealing, tabu search and GA for different types of location allocation problem. The authors inferred that GA was better than others to draw out more info from fewer alternatives. It seems to improve solution quite swiftly. However, for the unrestricted analysis of the candidate alternatives (individuals in GA) the performance of other methods may be better. But since in my own research I'll use constrained analysis, performance of GA will never be hampered.

In another research [4] GA performance is superior to neighborhood search and simulated annealing. They urged that area search can only just perform better under simple assumption and it cannot promise that the search consequence will be optimal. They also showed that GA does much faster than simulated annealing. Therefore, I'll apply GA method in my own research to solve location allocation problem.

2. Books Review:

An extensive literature review to provide idea about past researches of location allocation and various type of alternatives is completed. The target is to comprehend the conditions and developments in location allocation problem and alternatives. Location allocation is issues which is under research almost for a century (started from Weber's location allocation problem 1909). Now-a-days the LA problem is continuing to grow with tons types and classification. The combinations of different classification have made the problem more complex and therefore the techniques of solution. This chapter will investigate all such studies and will discuss the pros and downsides and look for the space where much light of research weren't shed.

2. 1 Service, demand, space in location allocation.

There is abundant utilization of some terminologies in Location allocation books.

Before entering details in literature review some terminologies should be described. Facilities, location and customers or demands are known as basic components of location allocation problems by Azarmand et. al. [15]. In a variety of location allocation problems COMponents varies and are likely involved to typify that location allocation problem. The following description comes with an influence by the authors.

2. 1. 1 Facility

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

Single (source) or multi (source) facilities

Single center or multi-facilities depends on the amount of the facility found in the condition. In solo source/facility, only 1 new center will be utilized or founded whether in multi source/facilities more than one facility are located.

Capacitated or uncapacitated facility

Facility can be labeled as capacitated and uncapacitated considering how much demand service can meet. If service 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 be categorised depending on variety of services it is providing. A facility can offer only one kind of service or multiservice.

2. 1. 2 Demand

Deterministic or Stochastic:

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

2. 1. 3 Space

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


In discrete space model, the assumption is that people have prior knowledge of the prospect sites. It is also referenced as site selection model.


Continuous space model actually generates appropriate site as end result. 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 believed as a continuing set of prospect 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 performed to distinguish location allocation researches up to 1989 12 months by Brandeau and Chiu [19]. They tried to provide an overview of major problems in location allocation and briefly express different types and exactly how they relate to one another. They examined 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 season 1989. They produced all the classification through aim, decision factors, system guidelines. Classification through objective was based on search engine optimization of some ideals through aim function and non-optimization types. Classification through decision factors was predicated on center, location service area, variety of machines or facilities etc. System parameter type classification was predicated on topological framework, travel metric, travel time/cost, demand etc.

Location allocation problem is also categorised by Murray[20]. Regarding Murray classification becomes more technical what it seems now-a-days. Unlike Brandeau and Chiu he has added various other classification predicated on all the factors from type to result of location model, its purpose and focus.

Church (1999) recognizes four standard classes of location models which can be median, covering, capacitated, and competitive[5]. Median models consider that the common distance from any individual with their closest service is minimized by locating fixed number of facility. By the amount of facility median models can divided into more classes which are 1 median and p- median. Covering models consists of within the maximum population by locating n facilities. Capacitated models consider the capability of each center regarding demand. Competition models help your choice maker to consider other's competitive facility location and readjust own facilities. Relating to Cathedral the recent craze is integrating multiple service models, for example p-median and maximal covering.

Integrating different location allocation model makes the model more sensible and as well as more computationally burdensome or complicated. So in order to lessen the tradeoff between both of these a balance should be produced to depict actuality and handling complexity in the location allocation problem.

Since we live working only p median within the next seciotn p-median, LRP

2. 1 P-median Location allocation Researches and Reality

Location-allocation (LA) is a issue of locating a set of new facilities to be able to increase or reduce distance from facilities to customers is and an ideal number of facilities need to be placed within an market so that it satisfies the customer demand [15]. Alfred Weber is recognized as dad of location allocation problem corresponding to Ghosh and Rushton [16]. Weber did locate a solitary 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 lengthened from one warehouse (center) to multiple supply points (facility) by another research of Cooper[18] in 1963 which was a p-median location allocation problem. If p is add up to 4(p=4) then p-median means 4-median problem which queries the locations of 4 resource centers for optimum aggregate distance from a couple of demand details. In Cooper's problem, multiple source centers or facilities are sited in constant space and discrete demand is allocated to a center.

Using real life data is a obstacle for location allocation problem. In a few of days gone by researches, facilities, requirements were used through nodes or constant space. In network founded location allocation problem, graph network can be used in many literatures. Hakimi[19] considered facilities sited as nodes in the graph network. So his optimum solution of p facilities will consist of only nodes in the graph network. In his model, demand is discrete and best alternatives of facilities are also discrete. Likewise in the center location solved by Hossage[13], a network of discrete nodes were used for facilities and requirements. Discrete nodes for center 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 constant space was used to locate optimal facility. Constant space was made up of cells in a report by Li et. al. Li, 2009 #30 where the liberty of choosing center from any cell also support continuity. Service can be located any place in the constant space and will not rely upon points relating to Neema et. al. Neema, 2010 #38. Though Neema et. al. used GIS data nevertheless they also did not consider their solution

In above all review demand and center can be used, distance between these two were regarded as straight line. Road network was not considered.

In GIS Road network

synthetic data(data stated in arbitrarily 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 course predicated on location of facilities and Location allocation problem track down facilities predicated on distance or sometimes shortest avenue between service and demand. Location routing problem is different with traditional location allocation problem in the distance between service and demand. For location routing the length is recognized as visit of customer or distributor to the facility through tour. For traditional location allocation distance is recognized as straight lines or radial trip from the center to the customer or supplier. Therefore, the classical location allocation problem ignores way by network when finding facilities [27].

Route can be followed in the location allocation problem. It could be one of the standards in location allocation problem. One of GIS strategies which considers street network as one of the source of location allocation problem is done by Li [4]. But road network is utilized to calculate closeness not to determine shortest path. Similarly Sasaki et al. [8] also did not use highway network in their suggestions. Traditional p-median always considers nearest distance as in a straight line collection or Euclidian distance between demand and service. Very few research paperwork in location allocation that used GIS, considered street network in their model at all. But no model from GIS so far used shortest route from street network into location allocation model. Hence the idea of head to from location routing model can be assimilated as shortest avenue in the positioning allocation model.

But in the traditional location allocation problem when facility offers service like school, hospital, market it is always assumed that students, patient or customer will go to the nearest facility. In reality, facility might not exactly be always the nearest one. Some of the facility may be chosen according to its type (i. e. special hospital; institution depending on medium or faith, market predicated on item etc. ). So requirements for facility should be stochastic rather than deterministic and some of the needs may not be used for nearest center location.

Genetic Algorithm in Location Allocation:

This was an individual 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 in a way that the total distance between each node and its closest center is reduced.

An improvement of single objective p-median problem is to use multiple targets with it. In the multiple aims capacities, best distance, ideal cost etc. can be put together. Multiple targets were also fixed by using GA in a research for finding multiple facilities with three aims like maximizing the population coverage, minimizing the full total transport costs and minimizing the closeness of the street [4]. Now even if the new locations have been allocated as the optimal and hence the best ones, these locations may well not be possible if the perfect location falls over hurdles [3] like water-body, existing complexes etc.

Market locations with the cheapest transportation cost to the nearest market where in fact the plants can be sold at maximum price was solved in one research [5] which also resolved multiple targets by GA. In another research [6], waste materials dumping locations were allocated with a low cost operating network and maximum distance from population living area. Lessening the distances from parks to highly filled areas, highly air polluted areas, loud areas and areas without parks were considered to find parks' locations [7]. Another research [8] was about finding 27 ambulances in 35 locations in a way that shortest ranges from main street network weighted by crisis case amount from small area to the nearest potential ambulance location were looked after. All the three researches [6-8] also package with multiple targets through GA method.

However, a hybrid evolutionary method was used in location allocation problem which dealt with the capability of the center [1]. But the facility was assumed as you cell. In addition, the condition space had not been spatial but simulated from random amount. In spatial framework, an improved hereditary algorithm with Hilbert curve was used for capacitated facilities [2]. However in both instances [1] [2] contiguity of cells in the center was not considered. Some types of facility location problem were likened using GA in a report [23] where the performance of capacitated service problem's solution had not been good. Its computational time was much higher. But the procedure of genetic algorithm with Hilbert curve [2] was faster in capacitated facility location problem.

Some authors [8] unveiled maximum solution for minimal distance taking into consideration the amount of demand. But they didn't consider the capability of the service centre when at the same time they were taking into consideration the demand at each location. GA has awareness in weight of the guidelines. Some authors [4] also used weight of the variables but didn't speak about any methodology of how to use weight and which weight may be the best for GA as marketing. Moreover, they did not deal with contiguity of the optimal facility as area. They assumed that service will be located as one point in map. In some other contexts [9, 10, 24] [25], though contiguity of the perfect facility was regarded as area the capacity of the center was not considered with the situation.

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] however the notion is applied in land allocation not in center allocation. He used region growing approach of image processing to expand region of contiguous cells from seed cell. But he only considered solitary land of contiguous skin cells as optimum solution. A noticable difference of Brookes' research was done for producing alternatives of best alternatives from GA which considers not only contiguity of cells but also multiple land allocation [25]. An agent founded model [24] was also used for optimum land allocation using contiguous skin cells for each ideal allocation of land like the study [25]. Stewart[26] also used GA in order to incorporate with land use planning decision support system. He achieved the perfect solution is for increasing the natural value of the area, for making the most of the recreational value of the area and for minimizing the price of changing land use. The idea of allocating land can be assimilated in the service allocation. Because virtually all results of facility allocation research considers point rather than area.

2. 5 Location allocation and ARCGIS:

The ARCGIS[12] location allocation evaluation layer offers only six different problem types to answer specific sorts of questions that are minimize impedance, optimize coverage, minimize facilities, optimize attendance, improve market share and target market share. Classical location allocation problem like p-median problem is identical to nominal impedance where in both case the objective is to reduce the amount of distances from demand items to facility. All of the problems considered uncapacitaed center which may not be practical in some types like school, hospital etc. Direct line distance is used in the output where occurrence of network had not been considered and was totally absent. All of the facilities were point in the map. There is absolutely no consideration for facilities as area. All the demand details were aggregated to the centroids of location. Using split demand point for each and every demand is not possible in ARCGIS while distinct demand point is utilized in some earlier researches as stated by Cathedral[28]

2. 6 Alternatives of location allocation problem:




Also We Can Offer!

Other services that we offer

If you don’t see the necessary subject, paper type, or topic in our list of available services and examples, don’t worry! We have a number of other academic disciplines to suit the needs of anyone who visits this website looking for help.

How to ...

We made your life easier with putting together a big number of articles and guidelines on how to plan and write different types of assignments (Essay, Research Paper, Dissertation etc)