PREFACE

tions of those facilities. These issues are further addressed in Chapter 8 wherein the set of possible locations for the new facilities is finite. The analysis proceeds from locating a minimal number of facilities to satisfy coverage constraints to designing one-stage, and then two-stage, distribution systems. These are the aforementioned discrete models of location.

Chapter 9 is concerned with the layout of facilities with known space requirements and known interfacility flow, in order to minimize transportation costs. In Chapter 10 the foundation is established for using mathematical distance functions to model actual travel distances in location models. Though this is the final chapter, it is an important support for the basic model of Chapter 1 and the various elaborations discussed through Chapter 7.

Chapter J

The Nature of Facilities Location Problems

ACKNOWLEDGMENTS

The first outline for the book was conceived during a beautiful winter week in February 1976 at the Love farm house in Southern Ontario. Since then the work has been influenced by many individuals including Paul Dowling, Zvi Drezner, Henrik Juel, Svend Kraemer, Chuin Shen, William Verdini, and Jsun Wong. We express our appreciation to the two anonymous reviewers whose suggestions led to substantial improvements over the original version of the book. We thank the many students at McMaster, Waterloo, and Wisconsin whose suggestions led to improvements on the earlier drafts that evolved into this final work. And we especially thank Kathy McCord at Wisconsin for her careful typing and cheerful manner as revisions seemed unending. We also acknowledge the continued commitment on the part of the Elsevier Science editorial staff. Finally, we thank our wives Ingrid Love, Verelene Morris, and Sharon Wesolowsky for their support, without which little would have been accomplished.

Financial assistance has been provided not only for much of the origiiial research upon which many of the models are based but for secretarial and other support by the following sources: The Natural Science and Engineering Research Council of Canada, The Wisconsin Alumni Research Foundation, The Graduate School of The University of Wisconsin at Madison, The Engineering Research Boards of The University of Wa-terioo and McMaster University, the Control Data Corporation, and the Social Science and Humanities Research Council of Canada.

Our analysis proceeds from an operations research framework. We will be concerned with formulating facilities location problems, constructing appropriate mathematical models, and deriving methods for solving the models. The problems considered involve the central question of where to locate an object (or objects) called a facility. The facility will interact with a group of other objects that have fixed locations, called existing facilities. A concept of distance between the facility to be located and the existing facilities will contribute to a performance measure. This will lead to an objective function that can be used to evaluate a trial location of the facility. The choice of locations may be restricted.

Consider the location of a regional warehouse for an electrical com-poiKnts manufacturer. Assume yearly demand for components in each of seven cities to be served by the warehouse is as given in Table 1.1. The location coordinates in the table are in centimeters measured from the left and bottom borders of the map shown in Figure 1.1. The faciUty to be located is the regional warehouse, and the existing facilities are the seven dties. The interactions stem from shipments of components from the warehouse to the cities. The performance criterion might be total annual pound-miles arrived at by calculating W where:

= X (total annual shipments from warehouse to city) (all cities) X (distance from warehouse to city).

Typically, demand is assumed to be fixed and cost is assumed to be proportional to distance. Thus, to maximize profit is to minimize W.

Perhaps the facility is a storage area on a factory floor. The existing facilities would correspond to the existing departments that will use the storage. If travel is via forklifit trucks, a typical performance criterion

Table 1.1 Yearly Electric Component Demand.

City

Location Demand (pounds)

would be the total daily travel distance of the forklift trucks. The objective would be to locate the storage area to minimize this total daily forklift truck travel, thus reducing transportation cost and traffic congestion in the aisles of the factory. In another instance, the facility is an electronic component in a wiring circuit. The objective function relates the location of the component to the total cost of wires or other conducting material connecting the component to other elements in the wiring system. These are examples of single-facility location problems.

A multi-facility location problem arises when there are two or more facilities to be located simultaneously, each interacting with the existing facilities and with each other. An example would be the location of two or more new departments in a manufacturing plant with flows of product taking place between each of the new departments and any number of

Figure 1.1 Locations of Cities to Be Served by a Regional Warehouse.

the existing departments, as well as between the new departments themselves.

In the general multi-facility case, the amount of flow between the existing facilities and the new facilities may not be known before locations have been determined. Suppose each existing facility has some given required amount of flow, perhaps pounds of product demanded. When the locations of several new facilities are to be determined simultaneously with the allocation of flow between each new facility and the existing facilities, the problem is referred to as a location-allocation problem. The storage example would be a location-allocation problem if it was required to locate two new storage areas to satisfy the known storage requirements of the existing departments, and allocations of storage were to be determined as part of the analysis. The usual aim of a facilities location study is to plan for the addition of new facilities to an existing structure, to rearrange an existing layout, or to plan a completely new system. In many cases a location-allocation model is necessary.

The possible sites for the new facilities may be a finite set of points (see Chapter 8) in two- or three-dimensional space such as cities for warehouse location problems or offices in an office building. The models for this type of problem use actual distances between points. The new facility sites may also be continuous subsets of two- or three-dimensional space (see Chapter 7). Here the distances are functions of the coordinates of the points. Often the continuous set models are used to generate candidate sites for selection by the finite set models.

A continuous set model is appropriate for the large-farm water-supply problem (Exercise 7.4). The existing facilities are points of end use for the water, such as Uvestock barns, irrigation systems, or houses. The new facilities are the deep wells to be drilled. If a new system is to be designed, the relevant questions are: How many wells should there be? Where should they be located? Which subset of users should each well serve? An extreme design is to locate a well at each user location. In this case, piping costs are minimized but the drilling cost may be prohibitive. Another configuration is to have one large well. A single well minimizes drilling costs, but piping and pumping costs may be prohibitive. Using one well would entail solving a single-facility location problem. When two wells are considered, drilling costs are increased, but piping and pumping costs are reduced. The allocation question is thus introduced. Where should the two wells be located and to which set of users should each one be connected? If the two-well problem can be solved, then a three-well problem can be considered, and so on, until the most economical number of wells has been found.

Variants of such basic facility location problems are often encountered. One of these is the location of emergency service facilities such as ambulance bases and fire stations. Here it may be desirable to minimize the

THE NATURE OF FACILITIES LOCATION PROBLEMS

1.1 DISTANCE MEASURES IN LOCATION PROBLEMS

maximum distance from the new facility to any of the points serviced. These problems, called minimax problems, require different solution methods from the models described thus far. It may be necessary to consider the effect on optimal locations of new facilities over future periods during which the interfacility flows may change or the number or location of the fixed points may vary. Information about the future will only be "known" in the form of probabilities. Several dynamic and probabilistic location models have been developed to support the necessary analysis.

For most location models, there exists a corresponding dual model that can be solved independently to arrive at answers identical to the primal location model. As in the case of linear programming, these duals are pure in the sense that they do not incorporate any of the primal variables in their structure. The duals provide alternative computational possibilities and give useful insights into the theory of location.

The importance of location analysis has been growing rapidly over the last decade. This is due to increasing transportation costs and recent developments of management science techniques that enable optimal solutions of complex, realistic location .models to be computed. Heretofore, heuristic rules were often adopted to remove the locational aspect of a study. Optimization techniques can indicate the flaws in such rules. For example, let us suppose that a warehouse is to be located that will supply two retail outlets that are located on a single route, as shown in Figure 1.2. We have chosen an arbitrary point along the route to be the origin and have given the outlet locations as a, = 10 miles, and flj = 30 miles. Suppose that to supply outlet 1 requires w, = 20 truck trips per month, whereas the monthly requirement at outlet 2 is = 10 truck trips. Our problem is to locate the warehouse to minimize the total truck travel distance which, in turn, yields the lowest shipping cost.

An intuitive rule that has been used in practice is the center-of-gravity method. This method computes the warehouse location x° according to the following weighted average formula:

Arbitrary Origin

Outlet 1

Outlet 2

which for the example at hand yields

0 a, = 10

Figure \.2 Location of Two Retail Outlets.

= 30

The total truck travel distance for this solution is W(16.67) = 20(16.67 - 10) -I- 10(30 - 16.67) = 266.7 miles. However, the optimal location, found using techniques described in Chapter 2, is x* = 10, for which the total truck travel distance is IF(10) = 20(10 - 10) 4- 10(30 - 10) = 200 miles. (The center-of-gravity method gives the optimal location if it is desired to minimize the sum of weights times squared distances; see Exercise 1.2).

1.1 DISTANCE MEASURES IN LOCATION PROBLEMS

A basic element in the formulation of location problems is the concept of distance. The shortest distance between two points may be a straight line, but this ideal is seldom achieved in practice. The straight-line distance between two points is an example of a relatively short distance measure. An example of a relatively long distance measure is the case of movement on plant and warehouse floors that are arranged into rectangular bays. Movement is allowed only along the aisles between the bays. Figure 1.3 illustrates two possible paths in moving from point a, to point 02 in such a situation. The rectangular distance between a, and Ui is given by {a„ai) = [0.5 - 3.25 + jLO - 3.0] = 4.75. Notice that it is not important which of the two paths is followed in moving from point a, to point «2, as the rectangular distance is equal for each path.

The rectangular distance between a, = (a,,,/:) and a, = (aj„aj2) is given by SXai,aj) = [a„ - , + a,2 - aD- Compare this with the straight-hne distance given by .(„ ,) = [(a„ - ajtY + (a - . It can be shown that rectangular distances are always equal to or larger than the straight-line distahces. In this example, the straight-line distance is S2{a„<2) = [(0.3 - 3.25)2 -I- (1.0 - 3.0)2]/2 = 3.4. Rectangular distances frequently approximate those found in practice; the plant floor and city-street grid are two of the most common examples. As shown in Chapter 2, when the rectangular distance measure is adopted, the location problem quite often can be solved by back-of-the-envelope methods; however, solving straight-line distance problems usually requires a computer.

Perhaps it would seem that there are few applications for models using straight-line distances. Road travel between a pair of cities is seldom along a completely straight path. However, a good approximation of the