by H5 in a few minutes of computer CPU time. It is not known for these larger problems whether all the solutions produced were optimal.

Rectangular distances were used for testing, although any Hp distance would have been suitable. Rectangular distances were chosen because large numbers of location problems must be solved during the computations, and rectangular problems can be solved rapidly and exactly. It is difficult to compare computing times between solving location problems with, say p = 1 and 1 < p = 2. This is because it is possible to compute exact solutions rapidly by simple arithmetic in the former case, but only approximations to the solution by relatively slow convergent algorithms are possible in the latter case.

7.5 LOCATION-ALLOCATION WITH CONTINUOUS EXISTING FACILITIES

When there are a great many existing facilities, it is convenient to return to the notion of area destinations introduced in Section 3.2, and to develop a so-called auxiliary model. Geoffiion (1976c) lists the intended benefits of an auxiliary model as:

1. Reduce the level of detail and complexity of the location-allocation model until it can be solved by "back-of-the-envelope" calculations.

2. Educate intuition concerning the behavior of the optimal solution of a full model, including sensitivities of the solution as certain parameters are changed systematically.

3. Develop insights to be tested using a full model.

4. Use the insights that are confirmed as a conceptual framework for understanding the numerical results generated by a full model.

Consider a consumer products manufacturer with a single plant and a range of products to be considered as a single product group. Goods are distributed nationally through full-line distribution centers (DCs). The model is constructed from the follovring assumptions (cwt denotes gross shipping hundred-weight):

(Al) Demand is uniformly distributed in an area A with a constant

density of p (cwt/square kilometer). (A2) All DCs are identical and arbitrarily relocatable. (A3) The supply cost for each DC is s (dollars/cwt) regardless of its

location.

(A4) The fixed cost of each DC is / (dollars). (A5) The variable throughput cost of each DC is v(dollars/cwt). (A6) The outbound freight rate for each DC is f(dollars/cwt-kilometer). (A7) There are no throughput limits for the DCs. (A8) Distances are adequately estimated as inflated Euchdean distances.

The model is given by:

minimize TC{,m) = pA{v + s) + fm + T{m), {1.1)

where T{m) is the (weighted-distance) transportation cost for m optimally located DCs. Initially, suppose each market area is circular and the respective DC is located at the center of the circle. The optimum size A* of the area for a given DC is determined by the radius, r, of the circle. The assumptions adopted imply that each market area will be A*.

We will use polar coordinates to compute T{1). The demand density at any point ( , ) is p. The quantity prdrdd costs tr{prdrde) to transport over a distance r. Thus T{\) can be calculated as:

T{\) = £ pt{ff drde = I ptr\ (7.8)

The assumptions imply that T{m) is rnT{\) = 2/3 -irmptr. If A is "divided" into m equal-sized nonoverlapping circles, the common radius will satisfy A = , which means r = { / . We have:

TC{m) = pA{v -\- s) + fm + - pt{Ayirmy

= pA{v + s) + fm + 0.37613 pt ". Using standard calculus methods, we find:

(7.9)

(7.10)

m* = {pt/fy A/2.041 and so each nonoverlapping market area should be: A* = 3.047 {pt/f)-y\

Of course, circles cannot divide A. The only identical market shapes that can divide the plane are the square, the equilateral triangle, and the regular hexagon. Of these, hexagons cover a given area with least transportation cost T{m). However, using hexagonal market areas instead of circular areias, the change in m* would be approximately +0.2%; square areas would change m* by approximately +1.1%; and even equilateral triangular market areas would change m* by about +4.8%. This means the analytical solution for m* based on circular market areas is quite robust with respect to the actual shapes of the market areas that will be used. The actual shapes can be tailored to the shape of the area A. Therefore, under the stated assumptions we have simultaneously answered these complex questions: How many DCs should there be? Where should they be? What service areas should there be to cover the total area A, which is essentially of unspecified shape?

As intended, sensitivity analysis is facilitated using the model. For instance, a 10% increase in p or changes m* by - 6.6%, as (1.10)/ = 1.066. Sensitivity predictions can be surprisingly accurate for small changes in p, t, and/when compared with results from a full model to be discussed in Section 8.3. Using TC(m) in equation (7.9), a figure such as Figure 7.6 can easily be constructed from the data of the problem.

EXERCISES

7.1 A subway is planned through an urban area. There are to be three access stations to serve a section of the line that crosses under eight streets as follows:

Street No. 1 2 3 4 5 6 7 8

Distance

The distances between consecutive streets (in meters) are shown. The estimated number of passengers arriving at each intersection per hour (during peak periods) is given by:

Street No. 1 2 3 4 5 6 7 8

No. of Passengers Arriving per Hour

350 200 500 600 150 400 250 450

Determine the three subway station locations that minimize total passenger travel on the upper street surface.

7.2 It is required to find the location of three distribution centers to serve six existing facilities in an urban area. Data are as follows (assume rectangular distances):

a. Graphically display „ and then find the set /„ using Property 7.2.

b. Using Property 7.3 determine which of the points in the set -/„ are not in £«.

c. Solve the location-allocation problem using dynamic programming.

7.3 Demand zone locations with their monthly requirements are given as follows. Coordinates are in kilometers on a rectangular coordinate system.

Two warehouses are to be located and allocated to minimize total ton-kilometer shipping costs. Assume as a starting point that demand zones 1 and 2 are served by one warehouse and that zones 3, 4, 5, and 6 are served by a second warehouse.

a. Try to improve this solution using heuristic H5. Assume rectangular distances.

b. Assume Euclidean distances. Find all the candidate partitions that are generated using the location of demand zone 3 as the pivot point in the Drezner algorithm.

7.4 Recently, Blue Water Farms, a hog and white bean farming operation in Huron County, Ontario, was faced with a severe water shortage. Extensive field draining in the area had lowered the water table and the existing shallow wells were not able to produce sufficient water to meet livestock, field, and multi-family needs. Figure 7E. 1 shows the location of the seven main house-bam locations where water is consumed. The farm manager decided to drill at least one deep well to supply the needs of the complex. In this section of the county there is an unlimited water supply approxi-

Figure 7E.1 Blue Water Farms-Geographical Configuration.

Huron Road

□ Farm 1

Farm 3 □

Farm 6 □

□ Farm 2

□ Farm 5

□ Farm 4

Scale: 1 centimeter = 8 7 meters

Farm 7 Blind Line Road

mately 75 meters below the ground surface. From discussions with a drilling contractor and an agricultural engineer, the following information was collected.

Approximate well cost (includes drilling, casing, pump, etc.) is $5200.00. The best way to distribute water from a well to another location is by polyvinyl chloride plastic piping buried 1.5 meters below ground level (to prevent winter freezing). A trench must be dug and the pipe laid and buried. Cost estimates were:

Trenching-$ 1.00/meter

Piping-polyvinyl chloride pipe (100 psi bursting strength) 1.25 inch, $2.29/meter; 1.5 inch, $3.00/meter; and 2 inch, $4.45/meter.

Because of differing requirements, the seven locations would require varying pipe sizes, as shown in Table 7E. 1. Any line length greater than 760 meters would result in an excessive pressure drop with these pipe sizes and required flows. The trenches can follow straight-line paths from the new wells to the user locations.

How many wells should be drilled and where should they be located? What is the optimal cost?

7.5 Suppose that market areas are hexagonal as shown in Figure 7E.2. The quantity pfdfde costs trip/drde) to transport over the distance r". Thus, the hexagonal analog of equation (7.8) is:

"4"!

Jo Jo

tpify drde.

Observe that r = 6/cos and that = Ibj-Jb. Find a formula for m* when market areas are taken to be hexagonal. Verify that the change in m* from that in equation (7.10) is approximately +0.2%.

7.6 Find m* for square market areas, then for equilateral triangular areas. Verify that the percentage changes in m* from that in equation (7.10) are approximately +1.1% and +4.8%, respectively.

7.7 Explain why parameters i and v in problem (7.7) have no bearing on m* or on the optimal service area shape. What shapes would you expect to

Table 7E.1

Farms.

Pipe Requirements for Blue Water

Farm

Pipe Size Required (Inches)

1.25

Figure 7E.2 Hexagonal Market Area.

evolve for market areas for the distribution centers of a consumer products manufacturer? Why? What are the major pitfalls of the model? How should the model be used?

7.8 It will be difficult to find precise values for the parameters in equation (7.10). Suppose A, p, and/have been measured accurately, but t has not. Let /„ be the actual value of the outbound freight rate and I be the estimated value. Let the optimal number of DCs using be w„ and the estimated number using t be m*. Determine an equation relating TC(m*)/TC{m) to t/t„. Explain the usefulness of such an equation. Is it worse to overestimate or underestimate /„? Determine an equation relating to t/t.

7.9 Leamer (1968) Suppose demand density is not uniform over the total area A as is assumed in problem (7.7), but A is divided into n circular

" imarket areas A„j = 1,...,«, each with uniform demand density Pj. If market area j has m, DCs, then transportation cost in that area is:

r/w,) = 0.37613 p,t / \ Use the Lagrange-multiplier technique to minimize T(m) = Tj{m) subject to X m, = m. Interpret the result.

7.10* The township of Rio Rancho has hitherto not had its own emergency facilities. It has secured funds to erect two emergency facilities next year.

*This problem was used in the 1986 Mathematical Competition in Modeling administered by the Consortium for Mathematics and Its Applications (COMAP). It is included here with the permission of COMAP and the author, J. C. McGrew, Department of Geography & Regional Planning, Salisbury State College, Maryland.