Figure 7E.3

mand.

Township of Rio Rancho-Geographical Configuration of De-

each of which will combine ambulance, fire, and police services. Figure 7E.3 indicates the demand, or number of emergencies per square block for the past year. The "L" region in the north is an obstacle, while the rectangle in the south is a park with a shallow pond. It takes an emergency vehicle an average of 15 seconds to go one block in the N-S direction and 20 seconds in the E-W direction. Your task is to locate the two facilities so as to minimize the total response time.

a. Assume that the demand is concentrated at the center of the block and that the facilities will be located on corners.

b. Assume that the demand is uniformly distributed on the streets bordering each block and that the facilities may be located anywhere on the streets.

Suggested Outline for Solution Report

1. A clarification or restatement of the problem, as appropriate.

2. A clear exposition of all assumptions and hypotheses.

3. An analysis of the problem justifying or motivating the modeling approach to be used.

4. 5.

The design of the model. A discussion of how the model can be tested. A discussion of the strengths and weaknesses of the model, including error analysis and such things as stability (eg, conditioning, sensitivity).

A one-page summary of results attached to the front.

REFERENCE NOTES

SECTION 7.1 This section is based on Love (1976).

SECTION 7.2 Ostresh (1973, 1975) used the strictly separating line property to suggest an algorithm based on choosing pairs of existing facility locations through which to pass a line, which is then rotated slightly. The implementation presented here is from Drezner (1984) who also considered the analogous problem under the minimax criterion. OKelly (1986) discussed an application to locating interacting hub facilities.

SECTION 7.3 Construction of the set /„ and the associated m-median approach are from Love and Morris (1975a). The definition of the rectangular hull and the proof of Property 7.1 are from Juel (1975). The set was discussed by Juel and Love (1983b). Wendell, Hurter, and Lowe (1977), Chalmet, Francis, and Kolen (1981), and Thisse, Ward, and Wendell (1984) discussed a related set of "efficient points." A point X* solves problem (2.10) for some choice of the positive weights Wl if and only if X* is an efficient point.

Wendell and Hurter (1973) proved that an optimal location exists in the convex hull for two-dimensional single-facility location problems for any norm. Their conjecture that this result would extend to the multi-facility problem (4.1) was proved by Hansen, Perreur, and Thisse (1980). Juel and Love (1983b) showed that if Jhe new facilities are chained and 1 < p < oo, all optimal solutions for problem (4.1) must be in the convex hull.

SECTION 7.4 The development here is from Love and Juel (1982). A survey of global concave minimization techniques is contained in Pardalos and Rosen (1986). Cooper (1963, 1964, 1972) did foundation work on formulating location-allocation models and solving them using heuristic procedures. Gelders, Pintelon, and Van Wassenhove (1987) discussed an application to a large Belgian brewery.

Techniques for exact solutions to problem (7.1) have been suggested by Kuenne and Soland (1972) for p = 2 and by Sherali and Shetty (1977) and Marucheck and Aly (1981) for p = I. Chen and Handler (1987) considered the minimax problem.

SECTION 7.5 This section is based on Gcoffi-ion (1976c), who used the model here to discuss the insight value of an auxiliary model. The work of Bos (1965) and Leamer (1968) supported the model development.

APPENDIX-CHAPTER 7

Mathematical Notes

7.1 Prove Property 7.1

The rectangular hull includes an optimal solution to problem (2.10).

proof: We will use the index set notation of Property 7.2. Let and be the complements of the index sets G,, and Lj. with respect to J; and for any index set A, let

S{A) = Z

Initially, suppose problem (2.10) has a unique optimal solution (xt,xf). Then the necessary and sufficient conditions (2.15) for a given point (a-,,X2) to solve problem (2.10) become:

S{Gd < S(G,) and S{L,) > S(Ld for A: = 1,2.

Now to show {x\,xf}tH,f, we must show that each of the pairs of sets in Property 7.2 have an element in common. On the contrary, supposeone of the pairs, say A and B, is disjoint. Then A contains B, and contains A, and we have

S{B) < S(A) and S{A) < S(B).

We also have the optimality conditions:

S{A) < S{A) and S{B) < 5( ).

Combining we get

S(A) < S{B) < S{B) S{A) < S{A),

which is a contradiction. Thus each of the pairs of sets in Property 7.2 must have an element in common. By conditions (7.3), this means ( *, ?)* «.

If the optimal solution to problem (2.10) is not unique, then the optimality conditions (2.15) can be stated:

S(G,) « SiG,) and S{L,) S(L,) for k= 1,2.

We see that the contradiction above breaks down only if both sub-problems have multiple optima, and A and are complements. This

means that any location in a rectangle is optimal, and A and consist of indices for existing facilities NW and SE (or NE and SW) to this rectangle. Thus two opposite corners of the rectangle belong to .

chapter Q

Site-Selecting Location-Allocation Models

Models of previous chapters are termed site-generating models, or "continuous" location models, because location takes place in a continuous space. The facility locations generated would indicate plausible "neighborhoods" within which to implement solutions, qualified by practical realities. Models in this chapter assume the decisionmaker can specify a list of plausible sites for facility location. The list may be constructed from solutions of site-generating models and supplemented by sites that are appealing from a multi-objective perspective. For warehouse location, the list might include gateway cities relative to important demand points, and cities where the company or its competitors presently have facilities.

Models of this chapter will treat location of facilities and allocation of demand points simultaneously (existing facilities are demand points in this chapter). Typical questions addressed include: How many facilities should there be? Where should they be located? What size should each facility be? Which facility should serve which demand points? We begin with a model to minimize the number of facilities required to satisfy service level constraints.

8.1 SET-COVERING MODELS FOR SITE SELECTION

Horses pulling a fire wagon, it was once decided, can run no farther than ten city blocks. For that reason, fire stations in many American cities were located 20 blocks apart.

Today Wichita, Kansas, is saving nearly $3 million in construction and

operating costs----The city had planned to construct five new stations

during the 1970s. But, after a computer analysis, the Fire Department