Hierarchical location analysis for integrated area planning in rural India

World Bank Reprint Series; Number 126 Shyamadas Banerji and H. Benjamin Fisher Hierarchical Location Analysis for Ite ra ted Area Planni ira Rural In3dia Reprinted with permission from the Thirtenth Eturoeacnai Congress of the Re-iomil Scio,wc Association, vol. 33 (1974), pp. 177-94  THIRTEETrH EUROPEAN ( CON, rRESS OF THE IEG rIONAL S3CIENCE ASSOCIATION HIERARCHICAL LOCATION ANALYSIS FOR INTEGRATED AREA PLANNING IN RURAL INDIA by Shyamadas Banerji and H. Benjamin Fisher* 1. INTRODUCTION This paper has two objectives. First we wish to describe an approach to hierarchical location analysis being developed for, and applied to, integrat- ed area planning in micro-regions defined as Community Development Blocks which are scattered throughout rural India.' Second, more implicitly, we wish to initiate a discussion of the research effort within which this approach is among several that have been undertaken. The Pilot Research Project in Growth Centers is funded by the Government of India with assistance from the Ford Foundation and has the purpose of beginniiing a process for development of personnel, information systenwis and methods for integrated area planning in rural India.2 What follows will describe only one set of methods used by the Project and very littlk will be said about personnel and information systemns. We feel that even this should be sufficient to begin an important discussion. The paper begins with an examination of spatial standards for hierarchical location planning in micro-regions and then proceeds to an exposition of set-covering and P-median algorithmns used to choose candidates for service centers, giveini altertnative values of the standards. Section 3 describes methodds used to appraise these candidates and recommend others on the basis of criteria that cannot be considered within the a] gorith nis. Finally, an application of the algorithms and appraisal methods is reviewed in an example based upon ;ne of the Project's study areas. A concluding section outlines the manner in which this procedure the authors are associated with the India Field Office of the Ford Found;atinn, New I)elhi, India. Opinions expressed in this paper are not necessarily those of the Ford Foundation or the (overnment of India. "'Integrated area planning" in India can be defined as intersectoral planning focussed upon spatial or localionnal investment decisions. These locational decisions are seen as a key to thesolution of the greater prohiem encountered inthle at tempt to achieve functional integra tioni betweensectors. (oriinitinit- I)evelrnpmlenI Blocks a it in cro-regioltal ad m in ist rative ullits havili an average of 125 settlements and anl t,orage population of 125.t0t()l eacht, iisually including one small market center. 2The Project includes twenty field-c-il teams assigned to sttudy are-as located in seventeen states and the Union Territor-y of Pondicherrv, as well as a small managerial group in the Department of Community Development and a Central Research Cell in New Delhi. The latter has a multi-disciplinarv staff composed of forty professionals supported by approximately tventy non-professionals.  178 PAPERS OF THE lll.(;IONAI ,S('11'N('C' A.SSo('tATION, VOL. 33, 1974 is linked to one iteration of a plan-making process which is evolving as a principal recommendation of the Project. 2. STANDARDS FOR HIERARCHICAL LOCATION PLANNING The methods reported in this papeir have been used in the PI-)ject to prepare what is called a General Settlemnent Plan (GSP) for each of the twenty Community Development Blocks studied. The objective of the GSP is to provide an initial and general framework for the e fficient and equitable spatial organization of the given micro-region EfficiencY is defined in terms of minimizing potential distances to be travwelled from settlements (demand points) to service centers (supply points); equity is defined in terms of maximum allowable travel distances; and spatial organization is defined in terms of hierarchies, including alternative scales for service centels and for the settlements which comprise their respective service areas. The GSP is initial in the seinse that it is a sketch plan to be completed rapidly as the first step of a plan-making process, and it is general in that it is not specific with regard to indixvidual sectors oIr categories of investment propos- als. It provides a framework wvithin which investment pl)oposals can be: a) made within individual sectors; b) integrated between sectors; and c) conceived on the basis of intersectoral relat iorns that are not apparent within individual sectors. Accepting the proposition of efficien-cy that the objective of the GSP should be to minimize potential distances travelled to service centers, the first task is to define equity standards for maximum allowable travel distance that may be interpreted as constraints for solutions at alternative levels of the spatial hierarchy. The use of a facility in a ser'vice center is, in general, a function of its accessibility from demand points and other factors such as av,ailability of transportation modes and routes, economic charac- teristics of user groups, traditions, personal preferences, etc. Other factors held constant, use will diminfsh with distances between supply and demand points. A utilization decay function may be defined which is a spatial-interac- tion characteristic of each service facility. This chalracteristic is related to the accessibility of the service to the user population and may be defined quantitatively by D, the populationi-weiglhted average distance of trav,el for the service corresponding to the distributioni of service facilities for the study area: m n Pi EPd.j D = -I . n E Pi where:  BANERJI AND FISH ER: PLANNING IN RUTRAL I.>DA 179 i= user population of settlement i; dij = shortest path distance to facility at iettlemrent j from settlement i; n = total number of settleme7uts; m = total number of facilities. The variance of the distribution is m E (D DO) Var (D) -- 'j-- - m where D, represents the population-veighted average distance of travel for the service area of each settlenment j. The variance of the distribution is a measure of the equity of access for all users in the study area. Obviously, these statistics are based upon the existing pattern of locations within and without the study area to which people travel in order to use facilities. Both D and Var (D) are access norms which are useful in developing access standards for planning purposes. Furthermore, they are vital to the demarca- tion of groups of service fuinctions with similar access characteristics. Organizing space for every service function individually would be dysfunc- tional in terms of efforts to select the minimum number of settlements needed for investments in facilities subject to the meeting of minimum standards for equity of access. Formulation of location patterns for eacl service on an individual basis would lead to a proliferation of locations in which investments would be spread out, thus diluting the benefits of urbanization and agglomeration. Grotuping of service functions by means of spatial interaction norms permits formulation of access standards for each group as a whole which can then be used to deteonmine optimal locations for its members. The norms D and Var {D) are necessary inputs to the development of realistic standards for the specific planning region in terms of what is achievable in light of the present and projected availability of resources. Variance (D) is used in appraising a particular locational pattern in terms of equity of access and is therefore helpful in choosing between alternative locational patterns. Thus, all the services being planned may be grouped in homnogeneoous categories which have similar access norms on the ba,sis of which the required standards may be foirmulated. The procedure used by the Project is gener-ally to prepare an array of ':iLz,ogeneous categories for a given stuidy area, to compare this array with exlplicit but often infeasible or undesirale standards for maximum triavel distacncec which are pirescribed in public policy,3 and then to agree upon explicit standards for alternative levels of the spatial hierar-chy in discussions with field cell 3For example, the Approach Paper to the Fifth Five-Year Plan pres( rillxs that no settlement. in India shall be more than five kilometers from a middle school or more than eight kilometers from a high school.  180 PAPERS OF THE REGXIONAI, SCIENCE ASSOCIATION! VOL. 33, 1974 personnel and others familiar with existing conditions and potentials of the study area. 3. MIN ;, MI NUMBERS OF CENTERS AND OPTIMAL SPATIAL LOCATIONS For every value of a maximum travel-distance standard corresponding to a particular group of se rvices, the minimum number of centers needed to service every settlenment, and their locations on the existing transportation network may now be deterniined. Co.rrespondinig to this minimum number of service centers, a locatio-i pattern may be defined which minimizes the aggregate weighted distance of travel for all potential users in the study area. This pattern optimizes the potential interaction of facilities and users. It may be noted that the location pattern which minimizes the aggregate weighted travel distance may violate the maximum travel distance standard. However, the Project's experience has been that very few settlements (usually no more than one or two) are involved in such violations and that this problem warrants additional clhanges of locational decisions only rarely. Influence of Existing Locations Any realistic technique for location planning should take into consider- ation the existing centers in selecting new locations for investment in service facilities corresponding to a particular level of access. The presence of existing centers acts as a constraint on the optimization algorithms to be discussed in following sub-sections and may, therefore, degrade optimal solutions. Departure from the unconstrained and spatially optimal solution may be measured in terms of wveighted average D or aggregate travel distance Z or the number of locations P needed to serv2cQ -very settlement according to a maximum travel distance standard A (all defined below). The uncon- strained algorithm corresponds to a situation in which nlo location is fixed a priori in the solution. It may be mentioned that the locations considered are not only those which are located within each study area. While it is true that each study area has fixed boundaries, the existence of facility locations just outside the boundaries which interact with settlements inside cannot be ignored if the final location plan which emerges is to be realistic. A study area is not a closed system. The "edge problem" wvhieh results, arises in the developnment of a plan for any bouLnded regionl. The Projecl approaches this problem by considering all centers which ser ve se ttleme(nts within the study area with particular groups of facilities wherever they are,ptrovided thatthle sp(cified ,ccess standarids a-ite satisfied. Centers existing both within and without the study area may be entered into the algor ithms as constraints.  I3ANERJI AND FISHER: PLANNING IN RURAL INDIA 181 Spatial Hierarchies4 Standards for maximum travel distance associated with various groups of services define a hierarchy oi settlements in space for each study area. The hierarchy arises because: a) the hierarchy is implicit in most services, e.g., in education the continuum of primary school - junior school - high school - college - university; and b) relationships exist betwveen settlements in terms of infrastructure availability. The highest level of settlements in the hierarchy is defined by the maximum travel-distance standard associated with a particular group of services which occur the most infre- quently. The next level of the hieraarchy would be associated with the second group of services and the maximum travel-distance standard associated with this group. The next level of settlements in the hierarchy would be associated withthe nextgroup of services, andso on.Itmay benoted thatthe settlements in a hierarchy which is defined by this procedure have the property of nesting. Nesting implies that higher level settlements are congruent with settlements in the preceding lower level and possess an "incremental basket of services" with respect to the lower level settlement. This also indicates that the number of settlements increases as one moves down the hierarchy, while the level of services and facilities increases incr-emelntally up the hierarchy. A center at a particular level possesses all the services and facilities of all the levels below it in the hierarchy. It would thus also be an element of all the lower hierarchical levels. In this context it is clear that all settlements at a particular hierarchical level constrain the solution of the next lower hierarchical level in the manner described in the preceding sub-section. The hierarchical relationship between settlemernts colrresponding to different maximum travel distances is the familiar tree structure and each link of the tree denotes the dominance-subselvience relationships between settlements. The graph thus described is directed and acyclic, so transitivity is maintained. It may be noted here that a hierarchical set of solutions to location planning introduces inefficiencies similar to those found in other constrained solutions. If there are three centers at level i and if the next lower or (j + 1)st lev-el requires 3 + x centers, level j + 1 of the hierarchy is constr ained by the pr eceding centers in level j. Negatioli of this principle would contradict the pattern of historical evolution of human institutions in settlements. 4A hierarclical relation indicated by , is a relatiorslhip defined on a set which possesses the following properties: a) non-refIexivity; b) inti -synirntry: i j and j i-> i i j; c' transitivity: i and j kz i.> k A hierarchy constitutes a strict order relationship of transitivt. dominance. A model in which tra-nsitivit) relatioinships of dominance is always verifiable is called a hierarchization model; see Rouget [20]. Scott [221 has defined nodal hierarchies on network systems for a location-allocation algorithm.  182 PAPIEiRS OF THE RE(IONA1, SCIN(E' ARSO(IATI()N, VOL. 33, 1974 The Set-Covering Algorithm The problem of determining the minimum number of locations needed to serve every settlement in the s'dy area such that no settlement is more than the prescribed distance away from a facility has been formulated as a set-covering problem and has been solved by a variety of heuristic and mathematical progr amminig techniqlues. The solution involves a two-step procedure: a) determining the shortest-path distance between all pairs of settlements by means of various algorithms such as those proposed by Dijkstra [6], Rushton and Ostresh [21], and Yen [27]; and b) constructing a binary matrix of constraints for every value of maximum travel distance from the shortest-path distance matrix, and then solving the set-covering problem for obtaining the minimum number and locations of settlements corre- sponding to the maximum travel distances. Set-covering problems have wide application and have received consider- able attention. The mathematical programming formulatiorn is P: Minimize {CX/AX= e, xi = 0 or 1, j = N} where: N= {1, 2,.... A - an mn x n matrix of zeroes and ones; C = an arbitrary n-vector; e (1, ..., 1) represents an m-vector. This is a special class of integer programming models known as a zero-one programming model. This class of problems has been solved utilizing the special properties of the set-covering problem.5 However, the size of the location problems encountered in the project tend to be quite large. The constraint matrix A can vary from 300 x 300 to 3,000 x 3,000. Furthermore, during the preparation of the general settlemiient plan for a study area the problem may often need to be run for as many as twenty values of the prescribed travel-distance standard, each defining a separate cover problem. In certain cases, where the sensitivity of the number of locations required to serve every settlement within a particular range of travel distance standards needs to be explcred, a hundred values of travel distances corresponding to a hundred separate set-covering probletns may have to be run. Thus, both the size of the problems and the large number of problems within a particular planning task have necessitated the development of heuristic set-covering techniques which are fast and accurate; see Banerji [3] and Ignizio [121. The output of the set-covering algorithm for a range of values of the maximum travel distance may be plotted, as shown in Figure 1. The heuristic set-cover ing alg(orithms may be constrained either 'See Balas and Padberg [ii [2], Banerji [3], Bellmore and Ratcliff [4], Garfinkel [8] [9], Ignizio [ 12], Lemke, Salkin, and Spielburg [ 161, Roth [ 19], and Toregas, Swaini, ReVelle, and Bergman [261.  BANERJI AND FISHIER: PLANNING IN RURAIL INDIA 183 28 -10 IL 12 E z 8 40 80 120o 160 200 Ma4xirnum T ravel;1 -[I Km-', ) FIGURE 1. Minimum Number of Facility Locations to Cover All Settlements in the Phirangipuram Block of Andhra Pradesh by the presence of facilities which already exist as a part of the final solution or by a hierarchical location-allocation procedure in which location patterns at each level are constrained by the selection at the preceding higher level. Referring to Figure 1 for a particular value of P, representing the minimum number of locations, the minimum value of the maximum travel-distance standard A repiresents the most stringent, and, hence the optimal, condition. The locations identified by this- combination of P and A represents the optimal set of locations. The P-Median Algorithm The P-median of a weighted graph is a set of points consisting enitirely of nodes which minimizes the sum of the weighted distances from these P points to points closer to them than any other set of P points in the graph. P-clusters of nodes are formed associated with each P-median with the Dirichlet property that all points in a cluster are closer to the median point in the cluster than to any of the other P - 1 median points. Mathemat- ically, the P-median is defined by Jarvinen, Rajala, and Sinervo [13] as follows:  184 PAPERS OF THE REGIONAL SCIENCE ASSOCIATION, VOL. 33, 1974 Let VP represent a set of p points v 1, vi2, ..., v P on a weighted graph G-= (V, E), let d(Vp, Vj) = Minimum {d(vi1, vj), d(Vi2, v;), ..., d(vjp, Vj)} where d(v,,, vU) is the shortest distance between vertex Vik, Vj, and let VikEVPCV (k=1,2,.p); VJEV (j=1,2,...,n). The set of points VO' is a p-median of G if for every VK on G n n , hi d(Vo, Vj) - hj d(VP, Vj) j=1 j=1 where h is the weight associated with vertex j. The mathematical programming version of the problem has been devel- oped by ReVelle, Marks, and Liebman [18]. The problem is to minimize n n Z=E Aijyi dij -L1 j1 subject to: n E Aij = 1 (i =. 1, 2, ....., n) j=1 where: yi = weight associated with vertex i; d U = shortest path distance between i and J; AU - A11 i 0 for all iand j, i # j; n ,Ajj = p; AXU =0, 1forall iandj; Ak ii I if vertex vi is assigned to median vu, 0 otherwise; Ak1 = 1 if vu is a median, 0 otherwise. Garfinkel, Nebbe, and Rao [10] have shown that the integer constraint on A,, can be partially relaxed by a weaker constraint set Aii - , I (j = 1, 2, n ,r), Ak U 0 for all iand j (i=j), thus formulating the P-median problem as a mixed integer programming problem.  BANERJI AND FISHER: PLANNING IN RURAL INDIA 185 It is easily seen that the P-median algorithm can be used for a large category of location analyses in which the objective is to locate P facilities in such a way as to minimize total effort or cost. In analyses of locations for schools, hospitals, and agro-produce markets the weights could, for ex- ample, be measured respectively in.terms of school-age populations, hospi- tal-using populations, and quantities of produce. Total cost or effort may be given as n ZN'V N C A *i 11j- 1 where Civ = y, d i. Analytical solutionis to the P-median problem have been developed by Garfinkel, Nebbe, and Rao [10J using a linear progTamming decomposition technique, by Diehr [5] using a heuristic search based on the dual of the linear programming version of the P-median problem, by ReVelle, Marks, and Liebman [18] using a linear programming approach (standard primal simplex) and a branch and bound approach in cases of non-integer termination, and by Jarvinen, Rajala, and Sinervo [13] using a branch and bound approach and a heuristic techni(que. H1eurI istic techniques have also been used by Maranzana [17] and Tietz and Bart [24]. Most problems which have been analyzed by researchers are relatively small compared to the problems encnulltered in the general settlenment plan. Since the formulation of a GSP requires running the P-median algorithm several times, heuristic approaches have been favored, being relatively fast compared to analytical techniques. Diehr [5] has shown that the Tietz and Bart [24] heuristic solution and the lower bound obtained from his heuristic search (based on the dual of the linear programming version of the P-median problem) differ by only two per cent. The Tietz and Bart heuristic has been used most extensively by the Project. Integration of the Set-Covering and P-Median Problems Application of the set-covering algorithm indicates the minimum number of locations P such that no settlement is further than che prescribed travel distance from a facility. The location pattern for the distribution of facilities in space may be such that the total cost of providing the s-rvice may be quite high. The result of the P-median algorithm indicates a location paUtelrn for P-facilities stlch that the total user cost for obtaini ng serivices is miniimiized. These two algoritlims may be combined priovided that -violations of the maximum travel-disltance standard1(ls are acceptable for some settlements. Then, corresponding to a pr-escrlibed travel di-stance standard, the minimiiumn number of locations P nteeded to coverl every settlenmnt may be obtained by the set-covering algorithnm. The optimal (listribution of P settlemilenlts in space with reference to the objective of mninimizing total user cost may then be obtained via the P-median algorithnm.  186 PAPERXS OF TIIE REIGIONAI1 SCIENCE ASSOCIATION, VOL. 3:3, 1974 4. MODIFICATION OF OPTIMAL SPATIAL LOCATIONS TO ACCOUNT FOR EXISTING SOCIO-ECONOMIC INFRASTRUCTURE AND OTHER REALITIES The hierarchical location patterns determined by the set-covering and P-median algorithms are optimal in terms of criteria based upon potential spatial access and total-systemi user costs. However, other criteria are also important for locational investment planning. Conditions of capital rationing and tr aditional preferences which reflect av'ailability of existing infra- structure (including natural resources, entrepreneurial skill, and other inputs for growth and development) necessitate the consideration of these other cr-iteria at this point. Thus, the third step of the General Settlement Plan is to modify the optimal spatial locations to account for the existing social and economic infrastructure. A number of techniques for assessing and ranking settlements in terms of their potential for growth and development as centers have been developed and applied for this purpose. These include: variations of Guttman scales which rank settlements in a region according to the numbers of selected social and economic institutions in each; see Sen, Wanmali, Bose, Misra, and Ramesh [23]; settlement ranks based upon a variation of the Reed-Muench method for calculating set tlement-population thresholds for clifferent institutions; see Haggett and Gunawardena [11]; settlement ranks based upon service-area population thresholds for different institutions; see Fisher and Rushton [7]; settlements ranked by inward flows of people and goods; see Kumar [15]; settlements ranked using factor analyses of these flows; see Tewari [25]. Other techniques are used at this point to consider alternative locations for centers in the sub-regions of candidate centers already chosen by the set-cove ring and P-median lglaor-ithms. The result at each le Vel of hierarchy is generally to shift some locations for planned centers and to let others stand. As yet, the Project has found no case in which the shifting procedure yields solutions which violate the original conditions of spatial optimality by more than a small margin. A typical example will be sumrmar ized in the next section of this paper. Delineation of ServL,ice Areas For Each Ceniter Identification of center-s at each level of the spatial hierarchy now permits the delineation of approximate service areas. Thli is done on the basis of simple p)roximity plrinciples. All settlements are assigned to their nearest. centers so that each cluster forms a Direchlet region. A code has beell developed in Fortran IV for an IBM 360, j44 computer wvhich makes the allocations by scanning a matrix of intersettlement shortest-path distances on the existing transportation networlk. An equivalent graphic technique for delineating service areas has been developed by Keeney [14].  BANERJI AND FISTIER: PLANNING IN l'KRAL INDIA 187 5. APPLICATION OF THE GENERAL SETTLEMENT PLANNING METHOD TO PHIRANGIPURAM BLOCK IN GUNTUR DISTRICT OF ANDHRA PRADESH Phirangipuram Block is located eight miles east of Guntur Town in Andhra Pradesh. Guntur Town is the largest settlement in that region and is the most important point of interaction for all settlements of the study area. The two urban centers in the Block,6 SaitLenapalli (24) and Phirangipuram (20), occupy focal positions with respect to socio-economic and allied institutional development as suggested in Figure 2. Social services E xarmples of F t lIre. t o; d I .1, of Mj itmnn't I tv tI),IjcfL Pfanr')i For Fj' JIEnvl Ct-te ors