Table 8.3 Constraint Coefficients for Example 8.1.

as given in Table 8.3. A zero-one 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»>-> -t-Kon 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. r-i. 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 Trade-off 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

,-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. Solid-line partitions denote 15-minute coverage. Suppose a choice among alternate optima to problem (SC) is to be made on the

®

Figui 8.3(a) A Location Set-Covering Solution for 7" = 15.

(Source: Ciiurch and ReVelle, 1974, in Papers of the Regional Science Association 32:101-118.)

basis of best coverage within 7" = 10 minutes. Dashed-line partitions indicate 10-minute 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) lO-minute 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 10-minute coverage. This benefit must be balanced against the cost of some of the population now lying outside 15-minute coverage.

(c) The Weighted Set-Covering 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:101-118.)

maximum number of existing fire stations. This avoids capital expenditures where possible and avoids the political "cost" of moving a fire station. A two-pass 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:101-118.)

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 set-covering problem that replaces objective (8.1) with: minimize A, where c,, > 0. For problems beyond

the computational reach of standard zero-one linear programming algorithms, specialized algorithms are necessary. Most integer programming texts contain a section on specialized approaches to solving set-covering problems.