back start next
[start] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [ 32 ] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]
32 Table 8.3 Constraint Coefficients for Example 8.1. as given in Table 8.3. A zeroone linear programming algorithm found q* = 3. Several alternate optima were reported. Of these, z* = (1,0,0,0,0,0,1,0,1,0,0,0) gave the least maximum response distance. At Step 2 then, /3 is updated to {1,7,9), for which (/ ) = 38. Returning to    1  TU n1/Y«Wh»>> tKon tQfminaffc (Source: ScoU, 1971, Combinatorial Programmmg. Spatial Analysis and Planning Methaen, London.) locating (w = 3) ambulance bases. No r« T, constraints are used An arbitrary initial choice. I, = {3,5,11} with T{I,) = 43, is indicated in the figure. Proceeding to Step 1 in the algorithm, the a,,s produced are Table 8.2 Symmetric Shortest Distance Matrix (in kilometers). improvemem oi j uvci imimi 13. ri. v..wiiib,i.iv i... . .~ of maximum distance T versus m is given in Figure 8.2. Determining /3 = Jl,7,91 with nU) = 38,12 = 15,7), with /) = 43, and 7, = (8) with T{1) = 73 provides the left endpoints of the steps in the graph. Evidently optimal solutions to problem (SC) defined by 38 < < 43, for all £, require three facilities. The set /3 is a minimax choice from among those optimal solutions. Figure 8.2 Example of a Tradeoff Curve of Maximum Distance (D Versus Number of Facilities (m) to Be Located. 38 43
(b) Maximal Covering with Mandatory Closeness Constraints. The minimax approach to choosing from alternate optima for problem (SC) ignores the average closeness of response neighborhoods to their nearest service center. The following approach seeks locations for m facilities to maximize coverage (population covered) within a desired time (distance) T. Let Tf /,,,) be a required upper bound on the response time (or distance) to RNf from the nearest service center location. Let w, be the population at (or weight for) RN. Then solve the following problem: minimize 1 wXi (8.7) subject to Z Z, + X, > 1 for all for all S (8.8) (8.9) (8.10) Population inside 10..............201 Population outside 10 but inside 15 , 439 Population outside 15.............. 0 r     1*12   l       1 17  ®    33 •        (1 *   1   
,4 • 2 , = or 1 for all k,e, (8.11) where: (1, if a facility is to be located at site 0, otherwise J1, if demand point £ is not assigned to a facility, within T [O, otherwise Kl, = {k\ t,g < rj and K2f = {k f„ < ]. The objective is to minimize the population not covered within T and, hence, to maximize the population covered within T. Constraints of type (8.10) force Xg = 1 if no facility is located within T of demand point £. If any Zi = 1 for keKlg, then due to the sense of the optimization, will be zero in the optimal solution. Constraint (8.9) restricts the number of service facilities to m, whereas constraints (8.8) enforce the mandatory closeness requirements. Limited computational experience indicates that solving the linear programming relaxation frequently produces integer solutions as required. Example 8.3 Church and ReVelle (1974) provide the following example. Suppose there are 55 response neighborhoods for ambulance service and all must be covered within 15 minutes. Thus, all Tg = 15. Figure 8.3(a) indicates an optimal solution to problem (SC); m = 5 ambulance bases are needed. Solidline partitions denote 15minute coverage. Suppose a choice among alternate optima to problem (SC) is to be made on the ® Figui 8.3(a) A Location SetCovering Solution for 7" = 15. (Source: Ciiurch and ReVelle, 1974, in Papers of the Regional Science Association 32:101118.) basis of best coverage within 7" = 10 minutes. Dashedline partitions indicate 10minute coverage. Figure 8.3(b) shows an optimal solution to problem48.7)(8.11) using all = 15, = 10, and w = 5. The rectangular insert tallies the (improved) lOminute coverage. Finally, Figure 8.3(c) shows an optimal solution ignoring the mandatory closeness constraints (8.8). The rectangular insert indicates a great improvement in 10minute coverage. This benefit must be balanced against the cost of some of the population now lying outside 15minute coverage. (c) The Weighted SetCovering Problem. Fire station location analysis may include the goal of choosing from among the multiple optima for problem (SC) that alternative which utilizes the
Population inside 10 ...... Population outside 10 but inside 15 Population outside 15......... .354 286 0 Figure 8.3(b) An Optimal Solution to the Maximal Covering Location Problem with Mandatory Closeness Constraints. (Source: Churcti and ReVelle, 1974, in Papers of the Regional Science Association 32:101118.) maximum number of existing fire stations. This avoids capital expenditures where possible and avoids the political "cost" of moving a fire station. A twopass approach would be to first find the minimum number of fire stations necessary to satisfy the response time constraints. Then, holding this number constant, maximize the number of existing stations in the solution. Exercise 8.3a asks the reader to justify that the following hierarchical objective function combined with the response time covering constraints (8.2) achieves the intent in one step. The hierarchical objective is: minimize Z + E (1 + (8.12) Population inside 10 ...............609 Population outside 10 but inside 15 . 19 Population outside 15.............. 12 Figure 8.3(c) An Optimal Solution to the Maximal Covering Location Problem Without Mandatory Closeness Constraints. , , (5 and ReVelle, 1974, in Papers of the Regional Science Association 32:101118.) where 0 < w < (1/L), L is the number of response neighborhoods, and the existing fire station locations are indexed from 1 to p. This is an example of a weigftted setcovering problem that replaces objective (8.1) with: minimize A, where c,, > 0. For problems beyond the computational reach of standard zeroone linear programming algorithms, specialized algorithms are necessary. Most integer programming texts contain a section on specialized approaches to solving setcovering problems.
[start] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [ 32 ] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]
