FACILITY LOCATION MODELS DEVELOPMENT TO MAXIMIZE TOTAL SERVICE AREA

Abstract

This paper present and discuss the new developed model to maximize total service area of a fixed number of facilities. Two greedy algorithms, Greedy Adding (ADD) and Greedy Adding with Substitution (GAS), were applied to solve the optimization problem of the Maximal Service Area Problem (MSAP). The MSAP is a discrete model where a specified number of facilities that achieve the best objective function value of the model are selected out of a finite set of candidate sites. In this study the determination of Fire stations location in Jakarta Selatan, Indonesia, were chosen for simulation. The shape of total service area covered by emergency facilities such as fire stations and ambulances is influenced by the road accessibility. The determination process requires lots of manual intervention in trying to improve the total service area. The two algorithms managed to reach better coverage than the coverage of existing fire stations with the same number of fire stations within the same travel time. The ADD managed to reach the coverage of 82.81% and GAS did 83.20%., while the existing fire stations only reach 73.69%.w. The approach undertaken in conventional facility location models had only defined a facility's service area simply by a circular coverage. And therefore, it can be concluded that, as such the conventional approach is appropriate for facilities which are not influenced by topographical and road network barriers. [PUBLICATION ABSTRACT]

Headnote

Abstract

This paper present and discuss the new developed model to maximize total service area of a fixed number of facilities. Two greedy algorithms, Greedy Adding (ADD) and Greedy Adding with Substitution (GAS), were applied to solve the optimization problem of the Maximal Service Area Problem (MSAP). The MSAP is a discrete model where a specified number of facilities that achieve the best objective function value of the model are selected out of a finite set of candidate sites. In this study the determination of Fire stations location in Jakarta Selatan, Indonesia, were chosen for simulation. The shape of total service area covered by emergency facilities such as fire stations and ambulances is influenced by the road accessibility. The determination process requires lots of manual intervention in trying to improve the total service area. The two algorithms managed to reach better coverage than the coverage of existing fire stations with the same number of fire stations within the same travel time. The ADD managed to reach the coverage of 82.81% and GAS did 83.20%., while the existing fire stations only reach 73.69%.w. The approach undertaken in conventional facility location models had only defined a facility's service area simply by a circular coverage. And therefore, it can be concluded that, as such the conventional approach is appropriate for facilities which are not influenced by topographical and road network barriers.

Keywords:Facility Location, Emergency Facilities, Service Area, Network analysis S.)

(ProQuest: ... denotes formulae omitted.)

1. Introduction

Facility location modeling introduced in this paper is addressed to emergency facilities. Emergency facilities have a unique characteristic in the way they measure benefits. Typically, the objective of facility location problem is either to minimize costs or maximize benefits. In the case of emergency services, the objective is often stated as the minimization of losses to the public (Aly and White, 1978). In emergency facilities, the response time or distance traveled is a crucial parameter to measure the quality of emergency services (Toregas et al., 1971). Longer response will result in more losses, indicating the poor service. Conversely, quicker response will save more properties and lives from losses and damages. Therefore, emergency facility location problems are typically modeled under time or distance constraint. This nature of emergency services affects the types of models should be adopted for locating emergency facilities. For instance, it may make more sense to a city fire department to locate fire stations so that a response is possible to every property in less than five minutes, than to worry about minimizing the average response time (Longley et al., 2005). Given this consideration, coverage location problems such as the MCLP and LSCP are more appropriate than the PMP which seeks to minimize the total/average distance.

Facility location models concern the provision of a service to satisfy a spatially dispersed demand. A demand for the service exists at a large number of widely dispersed sites. It is impossible to provide the service anywhere. For instance, every household needs a source of groceries, but impossible to provide a grocery store at each household. Therefore, for reasons of cost, the service must be provided from a few, centralized locations. Examples of location models are the P-Median Problem (PMP), P-Center Problem (PCP), Location Set Covering Problem (LSCP), and Maximal Covering Location Problem (MCLP). The PMP has the objective to minimize the total or average distance between facilities and demands assigned to them, whereas the PCP has the objective to minimize the farthest distance (Klose and Drexl, 2005; Hamacher and Nickel, 1998). In the LSCP, the optimum number of facilities is one aspect of the solution to the problem, and the constraint requires for all demands must be covered by at least one facility (Toregas and ReVelle, 1972). In the MCLP, the number of facilities is known a priori and the objective becomes to maximize services for demands (Church and ReVelle, 1974).

Conventional facility location models only define a facility's service area simply as a circular-shaped region based on a specified radius. Such definition might be appropriate for facilities which are not influenced by topographical barriers, like sirens or telecommunication transmitters. But for emergency facilities like fire stations and ambulances, accessibility is an important requirement. Therefore, road accessibility should be taken into account in emergency facility location problem to improve emergency services. GIS can serve this requirement through network analysis. Network analysis in GIS takes into account network attributes such as road width, speed limit, barriers, turn restriction and one way restriction. This advantage provided by GIS should be incorporated in the service area calculation to obtain a more realistic model.

2. OBJECTIVES

The objective of the study is to develop a facility location model in continuous demand region, with road accessibility considerations. This is performed by integrating travel time zone generated through road network analysis in GIS into the MCLP. The objective of the location model to be developed in this study is to maximize the total service area of a fixed number of facilities. Hence, we refer it as the Maximal Service Area Problem (MSAP). In this case, the service area is defined as the travel time zone showing the area that can be reached by a facility in particular travel time. Both the MCLP and MSAP are described into further detail in the following sections.

Based on the fact that most conventional models only define a facility's service area simply as a circular-shaped region, this study is interested to enhance service area calculation in emergency facility location problem by using GIS.

2.1 The Maximal Covering Location Problem (MCLP)

The MCLP was first introduced by Church and ReVelle (1974). It seeks the maximum population that can be served by a limited number of facilities within a stated service distance or time. A mathematical formulation of this problem is stated as follows: ... (1)

... (2)

... (3)

... (4)

Where:

i,I the index and set of demand nodes

j,J the index and set of potential facility sites

N^sub i^ {j∈ J | d^sub ij^ < S} = the set of all node j which is within S of node i

d^sub ij^ the shortest distance/time between node i and node j

S the desired service distance/time for every demand node i

w^sub i^ the population to be served at node i

...

...

2.2 The Maximal Service Area Problem (MSAP)

The MSAP is created as a modification of the MCLP which makes use of the capability of GIS to generate service areas of facilities as travel time zones. The travel time zone, or in some texts referred as travel time band, is a polygon layer, overlaid on the network, indicating band of travel time (Figure 1).

In the travel time zones, service area polygons are generated based on the network through a network analysis in a vector GIS environment. Network analysis in GIS takes into account network attributes such as road width, speed limit, barriers, turn restriction and one way restriction. Most GIS packages which support network analysis can generate travel time zones. Some of which are TransCAD, ArcGIS Network Analyst, GRASS with its v.net.alloc and v.nec.iso functions, SANET with its Voronoi function and TNTMips Network Analysis with its allocation functionality.

The MSAP does not take into consideration capacity constraints of facilities, such as number of personnel, emergency devices, and emergency vehicles, in calculating the service area. It is designed as a discrete model where a specified number of facility sites that achieves the best objective function value of the problem are selected out of a finite set of potential sites. The continuous space of the study area is deemed as the demand region. To simplify mathematical modeling of the MSAP, this continuous space is divided into discrete points. The optimization problem is then defined as to maximize number of demand points intersecting with service area polygons of a set of facilities. In other words, we select a set of sites for the facilities in such a way that the combined service area polygons of these sites encompass the largest possible area in the demand region. The number of demand points intersecting with the service area polygons acts as the surrogate information to measure the area of coverage (see Figure 2). The actual area of coverage can be calculated in the GIS once the set of facility sites has been selected. The mathematical model of the MSAP is formulated as follows:

... (5)

...(6) ... (7)

... (8)

Where:

...

Other notations have been defined previously.

(a) Service area polygons of multiple facilities are overlaid one on top another; (b) the number of demand points intersecting with the service area polygons is used as surrogate information to measure the area of coverage.

In the original MCLP, the weight wi represents the population aggregated in the demand object. Since no data aggregation takes place in the MSAP, this coefficient may be replaced by the risk level of the demand point. For example, high-risk points have a higher weight than do low-risk points. But in the MSAP, there is no distinction of risk levels among demand points. Thus, the value of wi is set to 1 or simply ignored. Value of a^sub ij^ is an input obtained from the GIS. A GIS functionality is used to examine whether the demand points fall within the service area polygons of facilities.

3. MATERIALS AND DATA

3.1. Study Area

To evaluate the effectiveness of the MSAP, fire stations in Jakarta Selatan (South Jakarta) are chosen as the study area for simulation. The study area is a part of DKI1 Jakarta, Indonesia (Figure 3). It occupies an area of approximately 145.73 km^sup 2^. Jakarta Selatan represents an urban area with high density population, high road traffic rate, diverse landuse and heterogeneous human activities. Such area has a high demand for public facilities, including emergency facilities. Thus, a proper planning need to be established to ensure an adequate service is delivered.

3.2. Road Network Dataset

The road network dataset for performing network analysis was specially prepared. ArcGIS 9.2 package was utilized to build the road network dataset. There are five classes of roads in South Jakarta (Table 1) which are classified by similarities in physical characteristics and traffic condition.

This classification is used to stipulate the road hierarchies. The speed for each class is the average speed between day and night estimated roughly through a driving test for a whole week. The higher hierarchy road has the higher speed. The Tollroad is excluded when building the road network dataset, as fire vehicles do not typically use the toll road as their routes due to limited entrances, unless the fire incident occurs along it. Attributes of road data contain a Meters field representing the road segment length, and a Minutes field representing the travel time to traverse the road segment. From Meters and Speed fields, values of the Minutes field can be calculated. The Minutes field is then used as the network impedance in the network analysis.

3.3 Set of Candidate Sites

There are 63 candidate sites available in the study area, consist of 46 proposed sites and 17 sites of existing fire stations. The proposed sites were obtained through the site suitability evaluation performed as a Multi-Criteria Decision Making (MCDM) problem in a raster GIS environment. A series of suitability criteria, such as proximity to high-hierarchy road, distance to existing fire stations, ability to cover fire risk zones, proximity to water sources, were evaluated to determine suitable sites for locating new fire stations.

4. METHODOLOGY

In order to establish the MSAP as a facility location model, following steps have to be performed:

1. Establishment of the concept and characteristics of the model. This should clarify the objective of the model, for what facilities the model is addressed, backdrops that stimulate the development of the model, what conventional model to be modified, whether the model is designed as a planar, network or discrete model, what GIS functions to be integrated and how the integration will be implemented to improve location analysis and solution quality to the problem.

2. Formulation of the mathematical model. In order to solve the optimization problem of the model mathematically, the model must be formulated in the form of mathematical equation. Formulation of the model will be depending on geometric representation used for facility and demand entities.

3. Design of solution algorithms. The optimization problem of the model must be solved by optimization algorithms. This step should determine appropriate algorithms to solve the problem. Many algorithms are problem specific. That is, they need to be designed specifically according to the complexity of the problem, data size, desired solution quality, limit of processing time and other considerations.

4. Comparison of solutions obtained by the algorithms with different datasets. This should examine the performances of the algorithm in providing good solutions to the problem. Are the solutions optimal enough with the applied algorithms? Can better solutions be obtained with more advance algorithms? In this study, the solutions yielded are also compared with the existing condition to see how far the proposed method could improve the existing facility services.

The first two steps are already described in the previous sections. Hence, this section is more focused on the discussion of algorithms used to solve the MSAP. Both the MCLP and MSAP concern with the problem of selecting p facility sites out of n candidate sites that achieve the best objective function value of the problem. In mathematics, such problem is considered as a combinatorial problem. This problem cannot be solved by direct mean for a large dataset, as the number of possible combinations is enormous and will take very long time to be investigated. Typically, heuristics such as Genetic Algorithms (Li and Yeh, 2005; Jaramillo et al., 2002), Simulated Annealing (Murray and Church, 2004; Aerts and Heuvelink, 2002) and Tabu Search (Jaeggi et al., 2008; Sun, 2006) are used to solve hard combinatorial problems in the context of facility location problems. Heuristics only produce a near optimal solution, as the solution is not proved to be the best. Procedures in finding the solution are typically trade off the solution quality for processing speed (de Smith et al., 2007).

For this study, two greedy heuristics - the Greedy Adding (Add) and Greedy Adding with Substitution (GAS) were adopted to solve the MSAP. Greedy heuristics involve a process whereby at each stage a locally optimum choice is made which may or may not lead to a globally optimum solution to some problems. As such, greedy algorithms are local search procedures (de Smith et al., 2007). Both Add and GAS were chosen as they have been tested workable to solve the MCLP (Church and ReVelle, 1974), easy to understand, relatively fast and easy to integrate with existing data structures in the GIS. However, other heuristics like Tabu Search, Simulated Annealing and Genetic Algorithm may also be applied to obtain a better solution if necessary, but should be compensated by a significant longer computation time.

4.1. Greedy Adding (Add)

In order to achieve the largest total service area from p facilities within certain travel time band, Add starts with an empty solution set and then adds to this set one at a time the best facility site taken from the set of candidate sites. A site must be selected first as the initial point. For a small number of candidate sites, all sites may be tried as the initial point to obtain a better solution. That is, the algorithm is run iteratively according to the number of available candidate sites. For a large number of candidate sites, the site that covers the largest number of demand points may be selected as the initial point, and the algorithm is only run once. At each iteration, the site for the next facility is selected from the site that covers the largest number of demand points uncovered by the sites selected in previous iterations. The process is continued until p facility sites have been selected.

4.2. Greedy Adding with Substitution (GAS)

GAS was developed to obtain a more satisfying solution than the solution obtained by Add. Facility sites output by Add were reevaluated one at a time by comparing it with other free sites. The reevaluation process is basically a mixture of Drop and Add algorithms. Facility sites in the current solution are ordered based on decreases of total coverage that will be yielded if they are dropped from the set. The site that causes the smallest decrease is evaluated first, as it is considered less significant in providing the maximal total coverage. If a free site can provide an improvement, it will be added to the set of facility sites in the current solution, substitutes the site being evaluated. The total coverage is then recalculated and best sites in the new solution are reordered based on their new decreases. If no free site can provide an improvement, the site being evaluated will remain in the current solution and no substitution takes place. The reevaluation process is run for a specified number of times or until no longer improvement can be gained.

5. RESULTS AND CONCLUSION

Service area polygons of each candidate site are generated using New Service Area function in ArcGIS Network Analyst extension. There are two types of network nodes in this function - Facilities and Barriers. Candidate sites shown in Figure 4 are loaded as facilities in the service area computation. The service area is defined as travel time zones away from facilities. Some necessary parameters must be set first before generating service area polygons, such as what variable used as the network impedance (it can be distance, time or cost), in which band the travel time zones will be generated, how the polygon should be constructed, and what restrictions should be applied. The interface for these parameter settings is shown in Figure 5.

The optimization procedure was done outside the GIS. All of necessary data were exported from the GIS into an external database. These include the data of candidate sites, the data of demand points, and the data of coverage of candidate sites over demand points to extract information of aij required in the mathematical model. The data of demand points were obtained by converting the planar space of demand region into discrete points. For this study, the spacing of demand points was set to 200 m, resulted in a total 3614 demand points. Coverage of each candidate site over demand points was analyzed using Spatial Join function. This function analyzes whether the demand points fall within service area polygons of the facility. The heuristics were run outside the GIS using the data in the external database. All heuristics were coded in Perl programming language and executed on a computer environment with Intel Core 2 Duo 1.73 GHz processor and 2 GB RAM.

5.1. Results

The number of facilities to be sited p, was set equals to the number of existing fire stations (17 fire stations), so that the output can be compared with the existing condition. From 63 candidate sites in the solution space, each candidate site was tried as the initial point. Thus, each heuristic was run 63 times. The total time consumed by Add to complete all executions is 1 minute 57 seconds, while GAS needed 9 minutes 59 seconds. In term of the solution quality, since the GAS searches for best facility sites by evaluating the sites previously found by Add, accordingly the solution output by GAS is always more or at least equally satisfying than the solution output by Add.

The objective function of the MSAP in Equation (6), z, is defined as the number of demand points falling within the service area polygons of a set of facilities. Of all initial points tried, the highest value of z achieved by Add is 2,999 (82.98% of the total 3,614 demand points), while the highest value of z achieved by GAS is 3,010 (83.29%). Since the value of z only acts as the surrogate information to measure the total service area, we need to calculate the actual area of coverage to verify how close the z value reflects the actual total service area.

Calculation of the actual area of coverage was done in the GIS and the result is shown in Table 2. For this purpose, service area polygons of each facility set must be dissolved into single polygon first, and then clipped by the polygon of the study area to remove some area of the polygon lying outside the study area.

As it was expected, for facility sets obtained both by Add and GAS, percentages based on area of coverage A (in square kilometers) are slightly different from percentages based on z. This also occurred in the existing fire stations. Yet the differences are relatively small, below 0.2%. This is thought to be due to the relatively fine resolution of points used for discretization of demand region.

The map of coverage area yielded by existing fire stations and the two heuristics are shown in Figure 6. It can be seen that GAS has a slightly larger coverage area than does Add. The set of selected sites in Add and GAS are nearly the same. There is only one difference - Site 1 in the Add set is replaced by Site 59 in the GAS set. In the Add set, 5 of 17 selected sites are taken from the sites of existing fire stations (Site 1, 3, 9, 17 and 91); while there are only 4 in the GAS set, as Site 1 is replaced by Site 59 which is the proposed site. Compared with the coverage of existing fire stations, Site 23 and 24 appear to be the most responsible in providing increases to the coverage in the southern part of the study area.

5.2. Conclusion

Through the use of GIS, this study has been able to extend the conventional facility location models that employed concentric circle analysis to a more complex and realistic model - the MSAP. By taking advantage of GIS capability to calculate the service area as the travel time zones, the model takes into account the road accessibility in the selection of emergency facility locations. GIS simulates the real road network of the area being analyzed. Hence the solution gained by using GIS is more accurate than otherwise.

The objective of the MSAP is to achieve a maximal total service area from a specified number of facilities. Calculation of total service areas from multiple facilities cannot be done merely by creating simple summary of service area polygons, as the polygons are overlaid one on top another. This study has managed to solve this issue by dividing the planar space of demand region into discrete regular points. The use of regular points as the surrogate information to measure the total service area was introduced as an alternative method of calculation. The method was found to be helpful to ease the implementation of mathematical modeling of the MSAP. In a fine resolution of demand points, the percentage of total service area based on the number of demand points covered is very close to the percentage based on the actual area of coverage. Hence, the aforementioned method of calculation may be conveniently applied to measure the solution quality of the problem.

Two greedy heuristics, Add and GAS, have been successfully applied to solve the formulated mathematical problem of the MSAP. The GAS further evaluates the solution gained by Add to obtain a more satisfying output by implementing substitution procedure whenever the improvement is achieved. As a consequence, the processing time required for site searching by GAS is a bit longer than the processing time required by Add. The total time consumed by Add to complete all executions is 1 minute 57 seconds, while GAS needed 9 minutes 59 seconds. Results showed that both Add and GAS could provide better coverage than the coverage of existing fire stations with the same number of facilities within the same travel time. Add managed to reach 82.81% area of coverage and GAS did 83.20%, whereas the existing fire stations only reach 73.69%.

ACKNOWLEDGEMENTS

We thankful to the Faculty of Engineering and Institute of Advanced Technology of Universiti Putra Malaysia for allowing us to use the available computing facilities. We also like to extend our thankful to the Fire Department of Jakarta Selatan, Indonesia for giving us the opportunity to use their data.

Footnote

1 Daerah Khusus Ibukota (Special Capital Territory)

References

REFERENCES

Aerts, J.C.J.H. and Heuvelink, G.B.M. (2002). Using Simulated Annealing for Resource Allocation. International Journal of Geographical Information Science, 16(6), 571-587.

Aly, A.A. and White, J.A. (1978). Probabilistic Formulations of the Emergency Service Location Problems. The Journal of the Operational Research Society, 29(12), 1167-1179.

Church, R.L. and ReVelle, C. (1974). The Maximal Covering Location Problem. Papers of the Regional Science Association, 32(1), 101-118.

de Smith, M.J. and Goodchild, M.F. and Longley, P.A. (2007). Geospatial Analysis: A Comprehensive Guide to Principles, Techniques and Software Tools. Leicester: Matador.

Hamacher, H.W. and Nickel, S. (1998). Classification of Location Models. Location Science, 6, 229-242.

Jaeggi, D.M., Parks, G.T. and Kipouros, T., and Clarkson, P.J. (2008). The Development of a Multiobjective Tabu Search Algorithm for Continuous Optimisation Problems. European Journal of Operational Research, 185(3), 1192-1212.

Jaramillo, J.H., Bhadury, J. and Batta, R. (2002). On the Use of Genetic Algorithms to Solve Location Problems. Computers & Operations Research, 29(6), 761-779.

Klose, A. and Drexl, A. (2005). Facility Location Models for Distribution System Design. European Journal of Operational Research, 162(1), 4-29.

Li, X. and Yeh, A.G. (2005). Integration of Genetic Algorithms and GIS for Optimal Location Search. International Journal of Geographical Information Science, 19(5), 581-601.

Longley, P.A., Goodchild, M.F., Maguire, D.J. and Rhind, D.W. (2005). Geographic Information Systems and Science. England: John Wiley & Sons.

Murray, A.T. and Church, R.L. (2004). Applying Simulated Annealing to Location-Planning Models. Journal of Heuristics, 2(1), 31-53.

Sun, M. (2006). Solving the Uncapacitated Facility Location Problem using Tabu Search. Computers & Operations Research, 33(9), 2563-2589.

Toregas, C. and ReVelle, C. (1972). Optimal Location under Time or Distance Constraints. Papers of the Regional Science Association, 28(1), 131-143.

Toregas, C., Swain, R., ReVelle, C. and Bergman, L. (1971). The Location of Emergency Service Facilities. Operations Research, 19(6), 1363-1373.