decided to relocate two stations, construct only two new stations and transfer three existing companies to them.*

Example 8.1 Plane and Hendrick (1977) performed such an analysis in Denver. We will explain their approach using a hypothetical example similar to theirs. There are four possible fire station sites in a city and five response neighborhoods that require coverage by a pumper company. We will need a relation between expected fire engine travel time, T{d), and travel distance, d, to determine if coverage is adequate. In an empirical study, Kolesar, Walker, and Hausner (1975) validated the model T{d) = lidlayi ifd 2d, and TXd) = vja + d/v, if d > 2d,. The parameter a can be interpreted as acceleration, is cruising velocity, and d, is distance required to achieve cruising velocity. Considerations of time of day and regional traffic conditions (within a city) appeared to create only minor differences in average response velocities.

Table 8.1 shows the maximum allowable response time (Tg) for each response neighborhood (RNg) and the expected fire engine travel times. The objective is to locate a minimum number of fire stations while satisfying response time requirements. The problem can be cast in the form of a zero-one linear programming problem given by:

minimize = z, + Zj -b Zj + Z4 subject to

Oz, + \Z2 + IZ3 + OZ4

IZ, + OZ2 + OZ3 + IZ4

Oz, + OZ2 + OZ3 + IZ4

IZ, + IZ2 + IZ3 + IZ4 O2, + OZ2 + IZ, + IZ4

z,, Z2, Z3, Z4 = 0 or 1.

This is an example of an unweighted set-covering problem (SC), with general form given by:

minimize g = 1 z,, (8.1)

subject to

1 aktZk => 1

= 0 or 1

for all £ for all k.

(8.2) (8.3)

♦Advertisement for IBM in mba, Vol. 12, No. 5, May 1978

Table 8.1 Hypothetical Response Time Data.

Response Neighborhood

Maximum Response Time Requirements for First-Due Pumper (seconds)

Expected Response Time (seconds) from Fu-e Station Candidate Sites

In a related application, Kolesar and Walker (1974) let demand points correspond to response neighborhoods presently uncovered because their fire companies are in service. Site corresponds to the h empty fire station. The problem is to minimize the number of empty fire stations to be filled by relocating available fire companies so that all response neighborhoods are covered. In this context = 1 if filling the h> empty fire station covers RNe and = 0 otherwise.

In another instance, site is a potential ambulance station. Let be the travel time between site and RNg, and let te be the travel time from RNt to the nearest hospital. If the maximum permissible round-trip time is Tl for an ambulance serving RNg from the nearest station, then = 1 if + tf , and = 0 otherwise.

Still another instance arises indirectly. Walker (1974) described a model for use by the New York City Fire Department to add a fleet of tower ladders to its ladder companies. The Rand Institute of New York City was asked to suggest which of 138 existing conventional aerial ladder locations should be replaced by tower ladders. The fire departments goal was to deploy as many tower ladders as possible while maintaining at least one conventional ladder (which is preferred in certain situations) as one of the two closest ladders to every alarm box in the city. For each alarm box, the two closest ladder houses are called a response pair. If there are ladder houses that can accept a tower ladder and L alarm boxes, the implied optimization is:

maximize Q = Z

subject to

Z 1 for all £

= or 1 for all k.

Here = I if a tower ladder should be located in house and 0 otherwise, and a/,c = 1 if house is one of the two ladder houses in response pair £ and 0 otherwise. Now set = I - 2 and observe that a-Xl - z)

< 1 can be written as 2 - a<fZ = 1. The problem can now be put into

the form of problem (SC), where = 0 if ladder house should receive a tower ladder, and = 1 otherwise.

Although many solution procedures have been proposed for problem (SC) we will discuss three that are particularly expedient.

Solution Procedures

(a) Reduction Rules.

The following rules are often effective in reducing problem (SC).

R1. Redundant demand points may be ignored. If for some demand point e there exists another demand point r such that a„ a, for all (the demand point is covered whenever the demand point is covered), the constraint for demand point £ may be eliminated.

(For example, using Rl and letting /• = 3, the constraints for demand points 2, 4, and 5 may be eliminated in Example 8.1.) R2. Redundant sites may be deleted. If for some site there exists another site r such that , as for all £ (all demand points covered by site are also covered by site r), the variable may be eliminated.

(Using R2, the variables z, and Z2 may be eliminated in Example 8.1.)

R3. Essential sites may be chosen immediately. If for some demand point S, a,e = 1 whereas af = 0 for (site r is the only satisfactory service point for demand point £), z, may be set equal to 1. Further, demand point £ and all other demand points J such that a,.j have thereby been covered and their associated constraints may be eliminated.

(In Example 8.1 variable z may be set equal to I; the second, third, fourth, and fifth constraints may be eliminated using R3.)

Large problems may be reduced considerably (and often solved when the a/s are based on real data) by successive application of Rl through R3. When reductions do not produce an optimal solution, the reduced problem may be solved using the following procedure.

(b) Cutting Plane Procedure.

Define the linear programming relaxation of problem (SC) as:

minimize = 2 I E 1, for all £

z * *

and z, 0, for all k\. Step 1 Append the cutting plane constraint:

(8.4)

(8.5)

Step 2

Step 3

to the constraints of problem (8.4) with LB = I. (LB is a lower bound on the optimal value of problem (SC).) Solve the resuhing linear programming problem. Let q,,, denote the optimal objective value. If the optimal solution is integer, stop. Otherwise, if qH is an integer, set LB = and go to Step 3. q,, is not an integer, set LB to [q,,,] + 1, where [qt,] denotes the greatest integer in q,,, and proceed to Step 2.

Solve the resulting linear programming problem. If this solution is integer, stop. Otherwise, proceed to Step 3.

Use a branch-and-bound analysis to determine whether an integer solution exists with value LB. If not, set LB = LB + \ and return to Step 2.

Typically, problem (SC) is solved on the first pass through Step 2. If, however, as in the dynamic relocation of fire companies, problem (SC) is large and must be solved quickly, a heuristic procedure may be necessary. The following procedure is efficient and has proved effective.

(c) Kolesar- Walker Heuristic. Step 0 Set A = 1 and UB = -f-oo.

Step 1 Choose site (set z = 1) such that site covers {a = 1) the A" largest number of demand points.

Step 2 Assuming site has been chosen, eUminate all demand points £ for which = 1. If any demand points remain, set z, = 1, which covers the greatest number (break ties arbitrarily) of remaining demand points, and repeat Step 2. Otherwise, go to Step

Step 5 Let equal the number of sites chosen. If < UB, store the solution and set UB = q. If h = H, terminate; otherwise, set h = h + \ and return to Step 1.

The value of H is arbitrary. Computational experience using H equal to about one-third of the number of candidate sites indicates optimal solutions are produced with high frequency; otherwise, near optimal solutions are generated.

Perils and Perspectives

At this point it is appropriate to warn of the perils of integer programming. Integer programming problems are often very hard to solve exactly. Hence, there is often a need for good heuristics to "solve" location models of reahstic dimension posed as integer programs.

An opposing caveat must be registered, however. Using a heuristic cannot ensure that the solution generated is optimal. Efforts at sensitivity analysis and comparative analysis are therefore confounded. Typically individual computer runs of a model are designed to gain insights based on different scenarios. Consider the view expressed by Geoffrion (1976b):

Not only does an optimizing capability enhance the value of most individual runs [for validation and gaining insights], but it also provides the opportunity to make valid comparisons between results of different runs. This is an extremely important consideration because the conclusions reached by a planning project typically rely far more heavily on comparisons between computer runs than on runs considered individually. With [heuristic programs]. .. one never knows whether different results are due to different inputs or to the vagaries of the computer program.

Solving problem (SC) to develop configurations of emergency service units represents only a first approximation in many applications. The model focuses on intradistrict responses and ignores design issues relating to interdistrict response. The model also lacks service capacity considerations and fails to incorporate the probabilistic nature of the service system. See Walker, Chaiken, and Ignall (1980) and Larson and Odoni (1981) for models addressing these issues.

Set-Covering Addenda

(a) Set-Covering Under the Minimax Criterion.

Let m be the optimal value of problem (SC). Frequently there are several feasible solutions that use only m facilities. Some of these "optimal" configurations may appear very unattractive to a decisionmaker. Secondary criteria must guide selection from among the alternate optima. The following formulation chooses m sites for facilities to minimize the maximum time (or distance) for all the demand points to their nearest

located facility. Let /,„ denote a set of m indices of chosen sites. The maximum response time is:

(/,„) = max,{minfo,,j?ti).

Let / = [\,2,...,K\. The problem is to:

minimize /„,) such that is a subset of /. (8.6)

Problem (8.6) is sometimes referred to as the w-center problem. To retain the requirement from problem (SC) that response neighborhood £ is assigned to at least one located facility within the threshold time (distance) Tl, set ti,i = M, an arbitrarily large number for all and S such that ti,s > Tg. This implicitly enforces the constraints min./Jj < Tg, for all £. An optimal solution to problem (8.6) is denoted by /„,. The following algorithm determines /„,.

Miniekas Algorithm

Step 0 Choose an initial /,„ from /. (Perhaps start with an optimal solution to problem (SC) that located m facilities.)

Step 1 Calculate /,„) and define a, = 1 if 4f < T(I„), and = 0 otherwise. Then solve problem (SC) with these definitions. Let denote the optimal objective value obtained.

Step 2 If q* > m, or if problem (SC) is infeasible, terminate with = /„,. Otherwise, an improved solution is at hand. Update /„, as the set of indices k, such that z* = 1 in the solution of problem

(SC). If q* < m, then a judiciously chosen set of m~q* additional indices may be used to complete the update. Return to Step 1.

The jationale for Step 1 is that if q* m, then the new set /„ yields a reduced value of T{I,„), over the previous set. To see this, consider a typical constraint of problem (SC). Because Arff 1 is satisfied, some

zf = 1 for which ai,i= 1. This means the response time to demand point 2 fi-om chosen site is less than the previous maximum response time. Because all such constraints must be satisfied, all demand points are closer to their nearest facihty than the previous maximum response time. The number of zero values for the a-Zs increases by at least one at each iteration. This guarantees finite convergence of the algorithm.

The following example illustrates the construction of a trade-ofF curve of m versus T(J,„) to show service coverage versus the number of facilities required.

Example 8.2 Figure 8.1 and Table 8.2 are from Scott (1971). The demand points, indicated as nodes on the graph, are candidate sites for