a? = (3.25,3.0)

a, = (0.5,1.0)

12 3 4

Figure 1.3 Illustration of Two Rectangular Paths Between Two Points.

average total distance between several pairs of cities in a region can often be made by using a weighted straight-line distance function. For example, within the state of Wisconsin, road distances between cities are on average about 18% larger than the straight-Une distances (see Chapter 10). In the Canadian province of Ontario, they are about 30% larger, and in the U.S. as a whole, road distances between major cities are also about 18% greater than the straight-line distances. In practice, then, if we were solving a location problem in the U.S. as a whole, we could represent the distance between city / at location a, and city j at location aj by:

\.\MAa„a;) = 1.18[(a„ - aj,Y + (a„ - , "-

Rectangular and straight-line (Euclidean) distances are the special cases p = 1 and p = 2, respectively, of the Hp distance between points a, and Uj given by:

epia,a) = - a,, + a„ - ajY 1 < P < oo.

Figure 1.4 illustrates the distance between a, and a2 of Figure 1.3 for values of p between 1 and 2. Using the jP distance function to model actual distances results in more accurate distance measures than restricting use to either of the special cases p = I p = 2 alone. Techniques for empirically fitting the value of p to actual distance data are discussed in Chapter 10.

1.0 1,1 1.2 1,3 1,4 1.5 1.6 1.7 1.8 1.9 2.0 p Figure 1.4 The Distance Between a, and flj as a Function of p.

1.2 RELEVANT COSTS

Estimating the distance between two locations on a plant floor or between two cities is a matter of using a good distance-predicting function. A second step in a location analysis is to estimate the amount of travel per unit time along the route in question in order to achieve the intended purpose. The intent is to convert these estimates into an estimated cost. If goods are to be moved along the aisles of a factory floor, then we would need to know what type of vehicle is to do the hauling. The operating cost per unit distance of the vehicle and the operators wages per unit distance (an average vehicle speed estimate must be known) must be calculated. The question of whether to use average or marginal cost would depend on the situation. For example, if the transportation requirement of an application is small, and a vehicle and/or operator are available and underutilized, only the marginal extra cost of fuel, maintenance, and wear may be required in the calculation. In contrast, if the transportation requirements are substantial, requiring the purchase of new equipment and the hiring of extra operators, an average cost calculation may be more appropriate. The Coastal Construction Company case in Chapter 4 illustrates transportation cost calculations.

1.3 HISTORICAL PERSPECTIVE

Recorded efforts at solving location problems originated with a challenge by Fermat early in the 17th century. In his essay on maxima and minima Fermat wrote, "Let he who does not approve of my method attempt the

Cp(aba2)

solution of the following problem: Given three points in the plane find a fourth point such that the sum of its distances to the three given points is a minimum." Before 1640 Torricelli observed that the circles circumscribing the equilateral triangles constructed on the sides of the triangle, exterior to the triangle, intersect at the optimal point. In 1834 Heinen proved that the Torricelli property was not general; when the three points result in a triangle with one angle equal to or greater than 120°, the vertex of this angle is the minimizing point. In his Doctrine and Application of Fluxions (1750), Simpson generalized the problem to obtaining the point that minimizes the weighted sum of distances from the three given points. Weber (1909) incorporated this problem into location theory in his influential treatise on the theory of industrial location. There were two weighted material source locations and one weighted market location. An appendix by Pick treated mathematical aspects of the problem and discussed use of the Varignon frame (see Exercise 2.2) as a solution method.

The dual problem is also linked to an eariy history. In the Annates de Mathmaliques Pures et Appliquees, Vol. I (1810-11), p. 384, the problem is posed: "Given any triangle, circumscribe the largest possible equilateral triangle about it." In Vol. II (1811-12), pp. 88-93, Rochat, Vecten, Fau-guier and Pilatte observe: "Thus the largest equilateral triangle circumscribing a given triangle has sides perpendicular to the lines joining the vertices of the given triangle to the point such that the sum of the distances to these vertices is a minimum.... One can conclude that the altitude of the largest equilateral triangle that can be circumscribed about a given triangle is equal to the sum of distances from the vertices of the given triangle to the point at which the sum of distances is a minimum." Indeed, the dual problem was stated even earlier. In The Ladies Diary or Womans Almanacic (1755), p. 47, a Mr. Tho. Moss requests: "In the three sides of an equiangular field stand three trees, at the distances of 10, 12 and 16 chains from one another. To find the content of the field, it being the greatest the data will admit of?" It is unlikely, however, that Mr. Moss was aware of the duality involved.

In 1857 Sylvester posed the equivalent of a location problem under the minimax criterion as he offered a one sentence problem description: "It is required to find the least circle which shall contain a given set of points in the plane." The center of the circle is the minimax location of a facility in relation to the set of points. In 1860 he gave a geometrical solution attributed to Pierce.

These eariy adventures could not anticipate the iterative mathematical perspective enabled by the advent of the electronic computer. This explains why almost aU of the literature of facility location is quite recent. The notable exception is the paper by E. Weiszfeld, "Sur le point lequel la somme des distances de n points donnes est minimum," in the Tdhoku Mathematics Journal {1937), which presented an iterative procedure for

locating a new facility to minimize the sum of weighted Euclidean distances to any number of existing facilities. This paper, written in French, submitted from Prague, and pubhshed in a Japanese journal in 1937, was virtually unknown until the late 1960s. For this reason the method was rediscovered by others in the late 1950s and early 1960s. The paper was 25 years ahead of the main thrust of modern facilities location research, which started to gain momentum in the early 1960s. Indeed, the single-facility location problem was described as being unsolved in Progress in Operations Research, Vol. II, edited by Hertz and Eddison (1964).

EXERCISES

1.1 Using a standard highway map of your locale, choose 10 pairs of cities randomly from the mileage chart. Do this by assigning each city an equal sub-interval in the (0,1) interval and reading pairs of numbers from a random number table. Then use each random number pair to choose a pair of cities. Measure the straight-line distance between the cities in each pair and, using the scale on the map, convert these distances to miles or kilometers. The actual road distance is given in the mileage chart on the map. Calculate the ratio of each actual distance to straight-hne distance, and then calculate the ratio of total actual distance to total straight-line distance for the ten pairs of cities. Present your results in a table and comment on the implications for using the straight-line distance function (multiplied by a constant) to predict actual distances.

1.2 Given the problem:

minimize W(X) = w,[(x, - a,,Y + {x - aj], X

prove that the center-of-gravity location is optimal.

REFERE4CE NOTES

SECTION 1.3 References to early work related to Fermats problem and to the dual problem (including that posed by Mr. Moss) are from Kuhn (1967, 1976). Historical references for the minimax problem may be found in Elzinga and Heam (I972a,b). Francis and Goldstein (1974) published a research bibliography containing 226 references on facilities location-allocation. In the succeeding decade, the literature increased dramatically. The bibliography by Domschke and Drexl (1985) lists some 1,800 publications on location and layout planning. Francis, McGinnis, and White (1983) and Hansen, Peeters, and Thisse (1983) provide selective literature reviews. Two early facility location texts that use an operations 4; research framework are by Eilon, Watson-Gandy, and Christofides (1971), and Francis and White (1974).

Endre Vaszonyi Weiszfeld used his second name after immigrating to the United States during the early part of World War II. He is well known to management scientists as Andrew Vaszonyi.* He started his work while studying geometry in secondary school. An eariier paper Weiszfeld (1936) was a geometrical treatment of a four-point location problem in three-dimensional space.

*This information was given verbally to one of the authors by Professor Vaszonyi.

Introduction to

Single-Facility

Location

This chapter treats the more common versions of the single-facility location problem. In addition to the usefulness of the models themselves, the methods of their analysis introduce many concepts and techniques that will be employed in treating the more complex models of subsequent chapters.

We will first consider location problems where both the new facility location and the existing facility locations are treated mathematically as points, and where demands and costs are known. Distances are found according to one of the distance metrics discussed in Chapter 1; for additional discussion of distances, refer to Chapter 10. All transportation costs are assumed to be proportional to distance. Finding the optimal location!, of the new facility is equivalent to solving the following optimization problem:

minimize W{X) = X hAC.j),

(2.1)

where

n is the number of existing facilities (or "demand points"), Wj converts the distance between the new facility and existing

facility j into cost and Wj > 0, X = (x„X2) is the location of the new facility on the plane, aj = (aji,aj2) is the location of existing faciUty j, p(X,aj) is the distance between the new facility and existing facility j, and

Waj) = (x, - a,,!" + - !")"", P > 1.