248 Quantitative Methods and Socioeconomic Applications in CIS 2. Select one of the remaining subsets, and separate it into two or more new subsets of solutions. 3. For each subset, compute an upper bound fv on the maximum value of the objective function over all completions. 4. A subset is eliminated (fathomed) if (i) fv \/i,j,i * j (each demand assignment is restricted to what has been located), Xy = 1V? (each demand must be assigned to a facility), Xjj = p V; (exactly p facilities are located), xtj =1,0 Vz',7 (a demand area is either assigned to a facility or not), where / indexes are demand areas (/ = 1, 2, n), j indexes are candidate facility sites (j = 1, 2, ...,m),p is the number of facilities to be located, at is the amount of demand at area i, dtj is the distance or time between demand i and facility j, x{j is 1 if demand i is assigned to facility j or 0 otherwise. One may add a constraint that each demand site must be served by a facility within a critical distance or time (dtj " d0). This formulation is known as the p-median Examining Wasteful Commuting and Allocating Healthcare Providers 249 problem with a maximum distance constraint (Khumawala, 1973; Hillsman and Rushton, 1975). The second is the location set covering problem (LSCP) that minimizes the number of facilities needed to cover all demand (Toregas and ReVelle, 1972). The model formulation is m Minimize: Z Subject to: ^ Xj si Vj (a demand area must be within the critical distance or time of at least one open facility site) Xj =1,0 V/ (a candidate facility is either open or closed), where Nt is the set of facilities where the distance or time between demand i and facility j is less than the critical distance or time d0, that is, dtj " d0, Xj is 1 if a facility is open at candidate site j or 0 otherwise, /, j, m, and n are the same as in the above p-median model formulation. The third is the maximum covering location problem (MCLP) that maximizes the demand covered within a desired distance or time threshold by locating p facilities (Church and ReVelle, 1974). The model formulation is n Minimize: Z N, Subject to: ^ Xj> + yt si Vz (a demand area must be within the critical distance or time of at least one open facility site or it is not covered), m Xj = p (exactly p facilities are located), Xj =1,0 V; (a candidate facility is either open or closed), y{ =1,0 Vz' (a demand area is either not covered or covered), where i, j, m, n, and p are the same as in the /?-median model formulation, N{ and Xj are the same as in the above LSCP model formulation. Note that y,- is 1 if a demand area i is not covered or 0 otherwise; thus the objective function is structured to minimize the amount of demand not covered, equivalent to maximizing the amount covered. Similarly, one may add an additional constraint to the original MCLP that requires an uncovered demand point within 250 Quantitative Methods and Socioeconomic Applications in GIS a mandatory closeness constraint (the second and a larger distance threshold). The revised model is known as the MCLP with mandatory closeness constraints (Church and ReVelle, 1974). The above problems may be solved in the Network Analyst module in ArcGIS. Specifically, under "New Location-Allocation", "Minimize Impedance" solves the /^-median problem, "Minimize Facilities" solves the LSCP, and "Maximum Capacitated Coverage" solves the MCLP. Table 11.1 summarizes the models and corresponding location-allocation problem types in ArcGIS. For details, use the ArcGIS help on the topic "Location-allocation analysis." As demonstrated in this section, a location-allocation task is often formulated as an optimization problem composed of an objective function (or multiple objectives) and a set of constraints with decision variables to solve. Appendix 11C presents a case with an objective of maximum equal accessibility. The current location-allocation models available in ArcGIS are limited in capacities and do not have the flexibility of adding complex constraints. Many applications call for the formulation of more advanced models that require the use of R, SAS, or more specialized optimization packages such as LINGO. TABLE 11.1 Location-Allocation Models Location-Allocation Model I p-median problem II ^-median with a maximum distance constraint HI Location set covering problem (LSCP) IV Maximum covering location problem (MCLP) V MCLP with mandatory closeness constraints Objective Minimize total distance (time) Minimize total distance (time) Minimize the number of facilities Maximize coverage Maximize coverage Constraints Locate p facilities; all demands are covered Demand must be within a specified distance (time) of its assigned facility3 All demands are covered Locate p facilities; demand is covered if it is within a specified distance (time) of a facility Demand not covered must be within a second (larger) distance (time) of a facilityb Problem Type in ArcGIS Location-Al location Analysis Minimize impedance Minimize impedance (by setting an impedance cutoff) Minimize facilities Maximize capacitated coverage (by setting an impedance cutoff) Maximize capacitated coverage (by setting two impedance cutoffs) a Additional to constraints for model I. b Additional to constraints for model IV. Examining Wasteful Commuting and Allocating Healthcare Providers 251 11.4 CASE STUDY 11B: ALLOCATING HEALTHCARE PROVIDERS IN BATON ROUGE, LOUISIANA This is a hypothetical project developed to illustrate the implementation of location-allocation models in ArcGIS. Say, the Department of Health and Hospitals, State of Louisiana, plans to set up five temporal clinics for administering free flu shots for residents in the East Baton Rouge Parish. Sites for the five clinics will be selected from the 26 hospitals in the parish. For the purpose of illustration, the objective in this project is to minimize the total travel time for all clients, and thus a p-median problem. Other location-allocation models can be implemented similarly in ArcGIS.* The following data sets for the study area are provided: 1. Under the data folder "BatonRouge", geodatabase BR.gdb containing a point feature BR_Hosp for all (26) hospitals, a point feature BRBlkPt for all (7896) census block centroids and a polygon feature BRTrtUtm for all (92) census tracts (both from Case Study 1). 2. Under the data folder "Louisiana", geodatabase LAState .gdb containing a feature dataset LA_MainRd for the major road network in Louisiana (from Case Study 2). The planning problem is to locate five clinics among the 26 hospitals in order to serve the residents in a most efficient way (i.e., minimizing total travel time). The Minimize Impedance (/^-median) model in ArcGIS will be used to find the optimal solution. In practice, facilities are hospitals, demand points are represented by census tract centroids/ and impedance is measured as the network travel time. For demand point properties, the field "Weight" is the relative weighting of a demand point and is defined by the total population in each census tract. Step 1. Preparing the demand point layer: The area size of census tract varies a great deal, and is much larger in a rural area than in the central city. The geographic centroid of a census tract, particularly in a rural or suburban area, may not be a good representation of its location. A better approach is to use the population-weighted centroid (Luo and Wang, 2003). It is accomplished by using the mean center tool (see step 1 in Section 4.3.1). In ArcMap, use ArcToolbox > Spatial Statistics Tools > Measuring Geographic Distributions > Mean Center. In the Mean Center dialog window, select BRBlkPt for Input Feature Class, name the Output Feature Class BRTrt_WgtPt, choose * The following location-allocation models are available in ArcGIS 10.2: Minimize Impedance (p-median), Maximize Coverage, Maximize Capacitated Coverage, Minimize Facilities, Maximize Attendance, Maximize Market Share, and Target Market Share. For more details, see the topic "Location-allocation analysis" in ArcGIS 10.2 Help. f One may use the census blocks instead of tracts to define the demand for better accuracy. This case study chooses census tracts for illustration of the method and saving computation time. 252 Quantitative Methods and Socioeconomic Applications in GIS POP10 under Weight Field and TRTID10 under Case Field,* and click OK. The resulting layer BRTrt_WgtPt has 91 points, which do not include the Baton Rouge Airport tract (Tract 9800) with no population, and thus one fewer than the number of tracts in BRTrtUtm. Join BRTrtUtm to BRTrt_WgtPt based on the common keys (GEOID10 in BRTrtUtm and TRTID10 in BRTrt_WgtPt) to attach the population information to the weighted centroids layer, and export the data to a new feature class BRTrtPt under geodatabase BR.gdb to preserve the joined result. The layer BRTrtPt with population-weighted tract centroids defines the demand points, where the field DP0010001 is the total population for a tract. Step 2. Activating the Location-Allocation tool in Network Analyst: In ArcMap, add the hospital feature BR_Hosp and all feature classes in the road network feature dataset LA_MainRd to the project. From the ArcMap main menu, choose Customize > Extensions > make sure that Network Analyst is checked; back to Customize > Toolbars > select Network Analyst to activate the module. On the Network Analyst toolbar, click the Network Analyst drop-down manual and choose New Location-Allocation. The network analysis layer is created in both Table Of Contents and Network Analyst windows. The location-allocation analysis layer has six classes: Facilities, Demand Points, Lines, Point Barriers, Line Barriers, and Polygon Barriers (similar to step 10 in Section 2.4.2). Step 3. Defining network analysis classes (Facilities, Demand Points, and others): In the Network Analyst window, right-click Facilities > Load Locations to load from BR_Hosp (other default settings are okay). Similarly, right-click Demand Points > Load Locations to load from BRTrtPt; under Location Analysis Properties, set Name to OBJECTID, Weight to DP0010001 (total population); under Location Position, check Use Geometry and set the Search Tolerance to 6500 meters*; click OK to load it. As a result, 26 facilities and 91 demand points are loaded (similar to step 11 in Section 2.4.2). Step 4. Solving the location-allocation model: In the Table Of Contents window, double-click the composite layer Location-Allocation to open its Layer Properties dialog box* > Under the Analysis Settings tab, choose Minutes (Minutes) for Impedance; Under the Advanced Settings tab, choose Minimize Impedance for Problem Type, input 5 for Facilities To Choose (other default settings are okay); click OK. On the Network Analyst toolbar, click the Solve button K. The output properties of network analysis objects are updated to reflect the results. In particular, in the * The Case Field is used to "group features for separate mean center calculations". In other words, for each unique value of the case field (i.e., TRTID10 for census tract id), ArcGIS computes the mean center for all features sharing the same value of this field (i.e., multiple blocks within a tract). For your information, the field TRTID10 was not available from the original BRBlkPt layer, and was added by the author to facilitate the attribute join with the census tract layer. TRTID10 is defined as "Text with length 11", and the formula for its calculation is: trtid10 = [statefp10] & [countyfp10] & [tractce10]. f This is to accommodate loading a tract in the northeast corner of the study area. * Alternatively, in the Network Analysts window, one may click the Location-Allocation Properties button CI next to the Location-Allocation drop-down menu to open it. Examining Wasteful Commuting and Allocating Healthcare Providers 253 FIGURE 11.3 Five selected hospitals in thep-median model. attribute table of Facilities, the field FacilityType identifies which five hospitals are selected; and the fields DemandCount and DemandWeight represent the total number of demand points (census tracts) and total population served by each clinic, respectively. In the attribute table of Demand Points, the Field FacilitylD shows which facility a tract is assigned to. The Line class shows the allocation assignment between a demand point (census tract) and a chosen hospital (clinic). The results are presented in Figure 11.3. Among the 26 hospitals in the study area, five are selected as the clinic sites for minimizing the total travel time for potential clients. Table 11.2 summarizes the information for the service areas of the five clinics. TABLE 11.2 Service Areas for the Clinics Name No. of Tracts Total Population Baton Rouge VA Outpatient Clinic 30 147,409 Greater Baton Rouge Surgical Hospital 25 108,628 Lane Rehabilitation Center 7 40,084 Promise Specialty Hospital of Baton Rouge 10 62,947 Woman's Hospital 19 81,103 254 Quantitative Methods and Socioeconomic Applications in CIS 11.5 SUMMARY Applications of linear programming (LP) are widely seen in operational research, engineering, socioeconomic planning, location analysis, and others. This chapter first discusses the simplex algorithm for solving LP. The wasteful commuting issue is used as a case study to illustrate the LP implementation in R. The solution to minimizing total commute in a city is the optimal (required or minimum) commute. In the optimal city, many journey-to-work trips are intrazonal (i.e., residence and workplace are in the same zone), and yield very little required commute and thus lead to a high percentage of wasteful commuting when compared to actual commuting. Computation of intrazonal travel distance or time is particularly problematic as the lengths of intrazonal trips vary. Unless the journey-to-work data are down to street addresses, it is difficult to measure commute distances or times accurately. The interest in examining wasteful commuting, to some degree, stimulates the studies on commuting and issues related to it. One area with important implications in public policy is the issue of spatial mismatch and social justice (see Kain, 2004 for a review). The location-allocation models are just a set of examples of integer linear programming (ILP) applications in location analysis. The second case study in this chapter illustrates how one of the models (p-median problem) is applied for site selections of healthcare providers, and how the problem is solved by using a location-allocation tool in ArcGIS. The convenience of using ArcGIS to solve location-allocation models is evident as the inputs and outputs are in GIS format. However, its current capacity remains limited as it has yet to incorporate complex constraints. Solving more advanced models requires programming in R, SAS, or other specialized software packages. Economists often make assumptions in order to simplify a model with manageable complexity while capturing the most important essence of real-world issues. Similar to the monocentric urban economic model, Hamilton (1982) made some assumptions for urban structure. One also needs to note two limitations for Hamilton in the early 1980s: the lack of intraurban employment distribution data at a fine geographic resolution and the GIS technology at its developmental stage. First, consider the commuting pattern in a monocentric city where all employment is concentrated at the CBD (or the city center). Assume that population is distributed according to a density function P(x), where x is the distance from the city center. The concentric ring at distance x has an area size 2%xdx, and thus population 2nxP(x)dx, who travels a distance jc to the CBD. Therefore, the total distance D traveled by a total population in the city is the aggregation over the whole urban circle with a radius R: APPENDIX 11A: HAMILTON'S MODEL ON WASTEFUL COMMUTING R R 0 0