a. Formulate the layout problem in a nonlinear programming format.

b. Analyze the objective function and constraints of the nonlinear program for their convexity and/or concavity properties.

c. What would happen if you attempted to solve this nonlinear problem using a nonlinear programming algorithm?

9.2 The following exercises refer to the data from Exercise 9.1.

a. Display the W and D matrices of the Hall method. Then use the Hall method to develop a layout of the departments. Calculate the associated cost.

b. Use a pair-wise exchange method to obtain a final layout of the departments and its associated cost using the layout developed in Exercise 9.2a as an initial layout.

9.3 Solve the following four-facility layout problem using the branch-and-bound technique.

Interfacility Traffic Row

Interlocation Distances

9.4 Four machines are to be located on an aisle on a plant floor. The average number of fork-lift trips made each week between the machines is given below.

Starting with the machines in the order 1-2-3-4, use pair-exchanging to improve the solution as much as possible.

9.5 A company that does job machining and assembly would like to re-layout its production facilities in order to reduce its materials handling costs (see Figure 9E. 1). The required floor space, interfacility activity flows, and present layout are given below. Develop a new floor layout using the Hall method followed by an improvement method such as pair-exchanging.

Facility

Name

Required Area (Square Meters)

40 meters

60 meters

Figure 9E.1 Present Floor Layout.

Activity

Note: As an aid to reading the preceding table, consider part type 8. It has a total volume of 250 per year. Each part starts in department 1, then moves successively through departments 4, 9, 11, and 12.

REFERENCE NOTES

SECTION 9.1 The branch-and-bound example is based on the approach suggested by Gavett and Plyter (1966). Branch-and-bound methods were also given by Bazaraa and Elshafei (1979), Elshafei (1977), Gilmore (1962), Graves and Whinston (1970), Lawler (1963), Bazaraa and Kirca (1983), Burkard and Strat-mann (1978), Pierce and Crowston (1971), and Land (1963). Through suitable transformations the problem can be formulated as a mixed-integer programming problem. Transformation of this type was given by Love and Wong (1976a, 1976b), Bazaraa and Sherah (1980), and Kaufman and Broeckx (1978). Comparisons of the efficiencies of various algorithms were given by Nugent, VoUmann, and Ruml (1968) and Ritzman (1972). An early discussion of the floor layout problem was given by Wimmert (1958).

Burkard (1984) and Kusiak and Heragu (1987) surveyed applications, formulations, and exact and heuristic solution methods.

SECTION 9.2 The CRAFT procedure was developed by Armour and Buffa (1963). HC63-66 was given by Hillier and Connors (1966).

SECTION 9.3 It was shown by Scriabin and Vergin (1975) that in some cases experienced practitioners using computer graphics can improve layouts given by heuristic algorithms. The example problem given in Table 9.27 was given by Nugent, Vollmann, and Ruml (1968). An important background article for this section is that by Steinberg (1961). Hall (1970) proposed the eigenvector approach to quadratic placement.

Mathematical Models of Travel Distances

In this chapter we discuss mathematical models for estimating travel distances from point references. Consider the £p metric* given by £X,r) = - , + - !]/", p I, where q and r are points in the plane. Clearly if p is tailored to actual travel distances in a study area, the resultant metric must be at least as accurate as the special cases of;? = 1 and p = 2. Experimental evidence presented here indicates that it is inappropriate to simply assume a convenient value for p in a location study. This suggests the general strategy of using such empirical distance functions in facihties location studies, and motivates the attention we have paid to models.

Of course, greater accuracy can be expected from methods that calculate inter-site distances using actual road network data bases. eindorfer, Kochenberger, and Reutzel (1981) described such a method. However, it is difficult to incorporate actual distances in the iterative location algorithms described in previous chapters. Those algorithms depend on an explicit functional relationship between location coordinates and distances. Looking up actual distances would be impractical because source locations are changed continuously as iterations proceed. In a reverse sense, Ginsburgh and Hansen (1974) suggested the use of empirical distance functions to verify arc lengths between nodes in road network data bases. Screening road network data is advisable because these data often contain errors.

*A metric, ci(t],r), is a measure of distance between points q and r and is defined by the following properties: symmetry: d(q,r) = d(j,q); positivity: d(q,r) > 0; identity: d{q,r) = 0 if, and only if, <? = and triangle inequality: d(q,r) -i d(q,t) + d(t,r).

Empirical distance functions are useful in initial stages of distribution studies. Rough estimates of unit transportation costs can be efficiently determined by weighting the distance estimates that are computed from point coordinates. This avoids measuring actual unit costs between myriads of potential source-demand point links and supports a demand point aggregation analysis. Thereafter, more accurate cost data can be obtained by actually looking up best transportation rates for the source-demand zone links chosen for inclusion in the model.

In their distribution study, Mairs et al. (1978) reported that transportation costs to small demand zones had to be approximated because shipments were made by a truck delivering to several zones on a delivery tour. As thousands of such transportation costs were involved, a quick, reasonably accurate approach was needed. The cost-estimating relationship used (see Section 8.3) was based on the Euclidean metric.

In another study, Westwood (1977) used an empirical distance function to compare trunking versus tramping modes of bulk transfer of finished product linked with backloading of raw materials. In Section 8.1 we cited the following model of Kolesar et al. (1975) for predicting fire engine travel time, where d is travel distance:

nd) =

2{d/d) ,ifd2d, vja + d/v,, if uf > 2d,.

(10.1)

This model or a variation of it should be useful for other types of vehicle travel times. Using the empirical methods suggested here, given the coordinates of any point in the area to be served and the coordinates of the service center, the travel distance may be generated within the model. When large numbers of points are to be considered or the points are not known in advance, there is great advantage to using an empirical distance function. These benefits motivate the use of the continuous location models of Chapters 2 through 7 to generate candidate sites for more detailed study. Furthermore, when the planning horizon is quite distant, transportation cost estimates based on distances may be more accurate than using current freight rates.

10.1 EMPIRICAL DISTANCE FUNCTIONS

To study the relative merits of empirical distance functions, Love and Morris (1972, 1979) fit a variety of mathematical forms to samples of intercity, urban, and rural road distances. Let us discuss these five forms initially:

dXg,n , ) = A: 2 \ - = )), k>0.

where ,(9) = cos + q2 sin , qii9) = -q, sin + q2 cos

and similarly for { ),

d2(q,r- k) = A:[X (, - "

= kUg,rl fc>o,

d,{q,r; k,p) = \q, - ,

= ke,{q,r),k> 0,p 1,

d,i,q,r, k,p,s) = k[J \qi - r,\V"

= kmq,r)]"\ > 0, p 1, > 1,

ds{q,r; ) = [m,(,-r,)2-bm2(Q,-/•,)(92-2)+ (2-2)] where m, > 0 and ml < 4m .

Discussion

The indicated parameter restrictions are required for convexity of the fimctions. The parameters are to be evaluated empirically. The mathematical forms might be considered variations on the theme of the Eu-chdean metric, scaled by a constant k. di is the rectangular metric with axes rotated through an angle from the original coordinate axes, d and d replace the square root and square of the Euclidean metric by 1 and 2 parameters, respectively, d provides for weighted squared coordinate differences. A multiplicative constant can be considered to have been factored into the values of m,, W2, and m,. d chooses the best direction of axes through the parameter in accordance with a best-fit criterion. Except for the special case of p = 2, the analysts choice of axes affects the ability of d and d to predict distances accurately. The inclusion of in d, allows for a properly oriented coordinate system to study the accuracy of the weighted rectangular metric. For all but sets of points equidistant from the origin 0 = (0,0) are symmetric with respect to orthogonal coordinate axes. To illustrate this symmetry, Figure 10.1 plots unit distance contours for the jp metric. The contours bulge from being diamond shaped for p = 1, to being circular when p = 2, and ultimately toward the shape of a square as p is increased still further. For 0 < p < 1, the contours bend inward indicating the triangle inequahty is actually reversed, and so is no longer a metric in this range. The unit distance contour for ds is an ellipse. This is because ds(q,0; ,, 2, ) = 1 implies m, + m2q,q2 + rn,qi = 1, which is the equation for an ellipse when mi < 4m,m,. The directional bias inherent in ds is such that the travel