Map distances are converted to nautical miles using:

diqr) = u?«(,r) . cos {(q, + r,)/2),

(10.7)

and this may be converted to rhumb line statute miles by multiplying by 1.1515. The factor cos ((, + /-,)/2) corrects for distortions of the Mercator projection as either polar region is approached. This implies as a seventh empirical distance function an inflated rhumb line distance given by:

dAq,r; /:) = /:(1.1515) diqj), > 0.

A rhumb line between two points (with different longitudes) on the earths surface intersects intervening longitudinal meridians at a constant angle. Other than at the equator, the great circle route will not do so. Thus d7(q,r, 1) only approximates great circle distance. As an example, consider the distance from Seattle, Washington, g = (47° 36 N, 122° 20 W), to Miami, Florida, r = (25° 45 N, 80° 11 W). The respective Mercator map coordinates are (3255.8,7340) and (1599.8,4811). Then d(q,r) = 3022.9 and u?(,r) = 2424.5 nautical miles. We find d-,(q,r; 1.18) = 3294.3 miles, using = 1.18 which is the intercity route factor for U.S. distances from Table 10.6 and 10.7. A road map indicates that the road travel distance is 3273 miles. The estimate is off by less than 1%.

But how well does diq,r, 1) = 2791.8 miles approximate the great circle distance between the two cities? Using equation (3.2), the great circle arc between points q and r is defined by a such that:

cos a = cos q, cos r, cos { - ) + sin , sin r,. (10.8)

Expression (10.8) defines the great circle metric, ie, the shortest arc length between points and ris a. We find a = 39.55°, which is 11% of a great circle. The great circle distance between Seattle and Miami is 0.11(24,902 miles) = 2739.2 miles, using the circumference of the earth at the equator. d{q,r, 1) is off by less than 2%.

Large region metrics are convenient to use even in studies of not-so-large regions because the latitude and longitude of points of interest are often readily accessible. This obviates the need to define an original coordinate system. Furthermore, certain large region location problems can be solved approximately via d{q,r) which relies on the convenient Euclidean formula. The location problem is thereby translated to the Mercator map. For instance, the Globetrotter sales meeting problem is approximated by:

minimize W{X) = Wjdj{X,aj\ k).

(10.9)

Replacing d by d, problem (10.9) is approximated by:

minimize W{X) = X w{ix-aj,y+{x2-dj2y\\ (10.9a) X

which can be solved by the Weiszfeld iterative procedure (2.6). Indeed, approximating d by d" gains access to the wealth of techniques for handling a variety of Euclidean distance location problems. However, reliance on d ignores the correction term in equation (10.7). This leads to significant distortions of distances near a polar region, or when considering a region larger than a hemisphere.

10.6 MODELING VEHICLE TOUR-DISTANCES

Suppose distribution to customers is by a fleet of vehicles. The much-studied model for locating a facility to minimize the average cost of distribution is:

minimize W{X) = { ., ]). X

(10.10)

To be valid this objective must somehow account for the actual delivery operations from the facility, operations that involve optimal vehicle tours with deliveries to several customers at a time. But !lp{X,a estimates the "direct" distance to customer j. Treating a sum of weighted direct-distances must somehow account for the sum of vehicle tour-distance costs. Let N be the estimated average of the maximum number of customers that can be supplied on one vehicle route; ATis determined by such factors as vehicle capacity and maximum duration for a route. If the number of customers, n, greatly exceeds , then problem (10.10) may well be a reasonable approximation of the underlying location-routing problem. Otherwise, problem (10.10) is inappropriate; vehicle routing and facihty location become inextricably connected. Model formulation becomes considerably more complex than heretofore. This problem area has only recently begun to attract efforts to construct solution procedures.

EXERCISES 10.1

Use the selection process described in Exercise 1.1 to choose 10 pairs of cities randomly. Construct a coordinate system and then use intuition to estimate appropriate values of and p for d. Using the randomly generated trips, calculate AD. Then calculate AD using k= 1.15 in u?2, and comment on the results.

Describe applications wherein SD would be preferable to AD as a goodness-of-fit criterion, and conversely. Justify your answer.

1/V2 [(1,0) - (0,1)] = (I/V2, -1/V2).

10.10 a. Use d with k= 1.18 to estimate the road travel distance (approximately

1281 miles) between Chicago, Illinois, (41° 49N, 87° 37W) and Albuquerque, New Mexico (35° 05N, 106° 40W).

b. Use d (with fc = 1) to estimate the great circle distance from London, England, to Bombay, India (see Table 10.8). Then calculate the great circle distance according to expression (10.8).

c. Find a reference on spherical trigonometry; then trace the derivation of expression (10.8).

10.11 a. Solve the Globetrotter Business Machines location problem (Table 10.8)

using formulation (10.9a).

b. Evaluate the solution found in Exercise 10.11 a according to the objective function in problem (10.9), and then according to that in problem (3.1).

c. Evaluate the solution (49° N, 19° E) according to the objective function in problem (3.1).

d. Solve the problem of Example 3.1 using formulation (10.9a).

e. How would winds aloft or restricted regions affect the validity of using the great circle metric to model airline flight distances?

10.12 Radio transmissions follow a great circle arc. Suppose a radio station is to be located to minimize the greatest distance to intended listeners in the 15 cities of Table 10.8. Use d" as an approximation to rf, and one of the techniques of Chapter 6 for Euclidean distances to solve this minimax location problem. Comment on this process and on the result.

10.13 Suppose you have been hired as a consultant. Give a detailed account of an approach you would use to locate a distribution point from which customer demand will be met using a fleet of vehicles.

REFERENCE NOTES

SECTION 10.1 This and the succeeding section draw on the studies reported in Love and Morris (1972, 1979). Perreur and Thisse (1974) proved location properties for metrics approximating travel distance on star-shaped networks and networks with circumferential transport systems.

SECTION 10.3 The work of Ward and Wendell (1980) is closely followed here. Witzgall (1964) appears to have been the first to recognize the application of polyhedral norms to facility location.

SECTION 10.4 Cooper (1968) extended the minimum sum problem to consider distances raised to the power Aand proved Property 10.2 for Euchdean distances. Morris (1981) studied the problem for the case of jC distances. If the cost functions are only assumed to be continuous and increasing in distance, a global minimizer for the minimum sum problem can be obtained using the big square-small square method described in Hansen, Peeters, and Thisse (1983).

c. Suggest an alternative fitting criterion that reflects an asymmetric loss for distance estimation error.

10.2 Suppose outbound transportation costs t. are to be approximated using the cost-estimation relationship given in Section 8.3.

a. What method would you recommend for calculating dti, the distance from site to demand zone jP? Why?

b. If an empirical function is used, how would barriers such as large lakes, river segments between bridges, or mountain ranges with no crossings enter into the analysis? What about multiple barriers?

10.3 Show that the rectangular and Euclidean distances are equal if the line segment between q = {qq) and r = (rr) is parallel to one of the coordinate axes, whereas the rectangular distance exceeds the Euclidean distance by a factor of /2when the line segment is at a 45° angle to an axis.

10.4 Explain why the choice of coordinate axes affects the ability of the rectangular distance function to accurately predict actual distances on a rectangular grid.

10.5 Show that: e,{q,r)/yl2 < e,{q,r) < f,(?,r) and that ejiq,r) je,(?,r) 2

10.6 Graph the unit "circle" for using the parameters determined from the rural Wisconsin sample according to AD,. Describe and then try to justify the directional bias found.

10.7 a. Using the data from Example 2.2, formulate problem (10.4) using/t, =

0.6 and k = 0.3.

b. Solve the problem formulated in Exercise 10.7a using linear programming.

c. Compare the solution found in Exercise 10.7b with that found in Example 2.2.

10.8 Formulate the multi-facility version of problem (10.6), and tell how many variables and constraints there are.

10.9 a. Show that d is a metric.

b. Using an original orthogonal coordinate system based on the vectors (1,0) and (0,1), we can write q = ?,(1,0) + ,(0,1) and r = ,-,(1,0) -b r,(0,l). Show Vl llj,q,r) equals the rectangular distance defined on the 45° rotated coordinate system based on the orthonormal vectors:

(1/V2)[(1.0) + (0,1)] = (I/V2,l/V2)

SECTION 10.5 Translating the location problem to a Mercator map was suggested by Kuenne and Soland (1972).

SECTION 10.6 Christofides and Eilon (1969) did early work on estimating the sum of tour lengths in a location-routing problem. Dohrn and Watson-Gandy (1973) and Burness and White (1976) provided early discussions of the problem. Laporte, Nobert, and Pelletier (1983) developed exact algorithms for selected location-routing problems and surveyed related efforts.

APPENDIX-CHAPTER 10

Mathematical Notes

10.1 Determination of Parameter Values. For ?, the "confidence" intervals searched exhaustively were A:e[0.80,2.29] and pˆ[0.90, 2.29] using a grid width of 0.01. For uf, the intervals of search were A:e[0.8,1.25] and «[0°,90°], whereas for the search interval was A:«[0.8,2.29]. Searches were conducted in the following way for the three-parameter distance models.

First, the criterion function was evaluated at every grid point in a unit cube in the parameter space, using a grid width of 0.1. In almost all cases the minimum value of the criterion function was obtained at an interior point of the cube. Where this did not happen, the process was repeated after shifting the cube in the appropriate direction until an interior minimum was obtained.

Then a search was conducted on the grid points in a cube with a side length of 0.2 centered on the best point in the coarse grid, using a grid width of 0.01. When the minimum value of the criterion function was obtained at an interior point of the cube, the parameter search was terminated. This happened in all instances when d was employed. In many cases with d the search over the fine grid had to be repeated, each time shifting the cube in an appropriate direction until an interior minimum was found. A sensitivity analysis showed that for a fixed value of k, SDt gives rise to a surface like a flat-bottomed valley with steep sides. This accounts for the relative difficulty in estimating the parameters of d. Parameter values in an extended region may give a near-optimal fit, as long as the proper balance is maintained between p and s.

The search procedure employed does not ensure that a global optimum (to two decimal places) was found. However, since several of the parameter values were verified by doing a total enumeration using a grid width of 0.1, the reported parameter values are in most cases optimal or at least near-optimal with respect to the value of the criterion function.

10.2 Prove d4 satisfies the triangle inequality

proof: We must prove [ , )][ ,0¥+[ )], for 0 < < 1. The triangle inequality £p{q,r) < 2pig,t) + SJit,r) holds since Hp is a metric. Thus , ) < ) + U>r)Y, for K>Q. From Hardy, Littlewood and Polya (1952, p. 32), [a + bY < a* -f for 0 < < 1 and , > 0. Letting a = llp(q,t) and b = SXt,r) yields the required result.

10.3 Prove c/4 is differentiable at , when p/s > 1

proof: Write dJ,X,a-, \,p,s) as = - a,,!" -f \ - aj-Y", > \. A direction in is determined by the vector . = ( ) where = 1. Let the first directional derivative off at any point aj in the plane be given by:

= lim

= hm

X-0 X

= lim sign (X)X-[m, + 12" = 0, since a: > 1.