Table 8E.1 Regions for Columbia Express.

Region

States

1 Maine, New Hampshire, Vermont, Massachusetts, Rhode Island, Connecticut, New York, New Jersey

2 Pennsylvania, Delaware, Maryland, West Virginia, District of Columbia, Virginia

3 North Carolina, South Carolina, Florida, Georgia, Alabama, Tennessee

4 Mississippi, Louisiana, Arkansas, Oklahoma, Texas

5 Kentucky, Ohio, Indiana, Michigan, Illinois, Wisconsin

6 Missouri, Iowa, Minnesota, Kansas, Nebraska, North Dakota, South Dakota

7 New Mexico, Arizona, Colorado, Utah

8 Wyoming, Montana, Idaho, Oregon, Washington

9 Nevada, California

Table 8E.2. Regional Traffic Averages".

"Traffic averages given are daily poundage (in thousands) in and out of the region, Monday through Friday (next-day service from Friday is Monday). These typically fluctuate by up to 30%.

Suggested Format for Solution Report

1. Executive summary: No more than one page, containing the main issues, conclusions, and recommendations.

2. Analysis and recommendations: Discussion of the analysis, emphasizing assumptions made, criteria applied, and conclusions drawn. Recommendations should follow, and they should be clearly supported by the analysis. DO NOT do mathematical modeling in this section.

3. Appendix containing mathematical models, computer results, and any other technical material needed.

Exhibit 8E.1 Fleet and Cost Data, Columbia Express.

Most of Columbias present fleet is composed of AV-55 twin-jet transport aircraft. These are suitable for the mostly short-haul trips with frequent landings required in Columbias operations. These craft have a payload of31,250 pounds under normal operating conditions.

Estimated operating costs for the AV-55 arc $9.92 per minute when on ground hold, and $14.59 per minute when airborne. These are marginal costs and they assume a normal cruising speed of 525 mph. A degradation factor of 75% to convert from cruising speed to average speed is normal for reasonably long flights, but this may require modification for very short flights. About half of the above costs are fuel and oil costs.

Based on the experience of other forwarders, if Columbia were to open additional hubs it would require an outlay of between $425,000 and $460,000 yearly for fixed expenses at each hub. To this would have to be added a variable cost for staffing and operations that would run between $22 and $24 per thousand pounds of freight processed through the center.

REFERENCE NOTES

SECTION 8.1 Set-covering models for facility location came into prominence with Toregas, Swain, ReVelle, and Bergman (1971), who suggested the cutting plane procedure. Toregas and ReVelle (1973) applied the reduction rules. Minieka (1970) treated the w-center problem. Church and ReVelle (1974) introduced the maximal covering location problem. Belardo, Harrald, Wallace, and Ward (1984) gave an application of the model to siting oil spill response equipment. Hogan and ReVelle (1986) discussed backup coverage.

SECTION 8.2 Baumol and Wolfe (1958), Kuehn and Hamburger (1963) and Manne (1964) contributed early formulations and (heuristic) solution procedures to the warehouse location literature. Balinski (1965) gave a counterexample due to Gomory to show that problem (SRS) would not automatically produce an integer optimal solution; Benders decomposition was suggested as a solution approach. Efroymson and Ray (1966) were the first to develop an efficient branch-and-bound procedure for solving problem (SPLP). They noted that the linear programming relaxation, problem (SRS), frequently produced integer optimal solutions. Khumawala (1972) improved the branching rules of their algorithm, and Spielberg (1969) developed an implicit enumeration method. ReVelle and Swain (1970) first suggested using linear programming directly to solve the problem in its w-median form; and in the "unlikely event of a non-integer solution," to use a branch-and-bound scheme. Morris (1978) discussed the linear programming approach applied to problem (SPLP). Schrage (1975) showed how the assignment constraints (8.15) can be handled implicitly in the simplex method. Erlenkotter (1978) developed DUALOC. The article by Bilde and Krarup (1977) contained a version with minor revisions of their earlier research report (in Danish), which introduced an approach similar to DUALOC. The discussion of surcharges applied to problem (SPLP) is from Mavrides (1979), who studied the problem of locating lock-boxes.

Comuejols, Fisher, and Nemhauser (1977) gave a formal analysis of heuristics, whereas Geoffrion and Van Roy (1979) offered an informal analysis. A definitive account of the literature of problem (SPLP) was the survey and synthesis by Krarup and Pruzan (1983).

The demand point aggregation section is from Geoffrion (1976a), as is Section

8.4.

SECTION 83 This section is based on the work of Geoffrion and Graves (1974), which stands unique in its optimizing treatment of large-scale problems that contain most aspects of distribution design. The problem narrative follows Geoffrion (1976b). Aikens (1985) provided a review of location models for distribution planning.

APPENDIX-CHAPTER 8 Mathematical Notes

8.1 On Benders Decomposition. If tfie zero-one variables in problem (DD) are temporarily held fixed at feasible values, say zf, jfi, the reduced problem is given by:

minimize E Z S 2 „ . , ,

subject to

Z Z x,jkf

2 = D„iyf,

(8.38)

for all i,j for all i,kj

for all i,j,k,£.

Problem (8.38) is the partition of problem (DD) in terms of the transportation variables only and, as stated in the text, is assumed feasible for every choice of yi satisfying constraint (8.34). The dual of problem (8.38) can be written:

maximize 2 Z (-S,j)u,j + Z Z Z (- ) «

subject to

(8.40)

Ijkf

for all iJ,k,J? for all iJ

and , <> is unrestricted in sign for all i,k,C. The reason for considering problem (8.40) is that appears only in the objective function. The set of feasible solutions for problem (8.40), say F, is therefore the same for any choice of values for An optimal solutioij of problem (8.40) can be found by checking the extreme points of F, because problem (8.40) is a linear programming

problem. Let F contain extreme points denoted by { > ), h = l,...,N. In principle, then, problem (8.40) can be solved by finding:

max iV (-S„)«;; + E Z Z (- ! *, \ h N\. (8.40)

Using this form to represent the dual of problem (8.38) and therefore the x-partition of problem (DD), for a given j;-vector, problem (DD) can be solved by solving the following program, denoted problem (BDD):

minimize

B,y,z

subject to constraints (8.34) through (8.36) and:

(fz, + V, Z Z .) - Z Z "A

~ Z Z Z -ikuDieyh

(8.42)

h = 1,..., , (8.43) = or 1 for all k,e. (8.44)

This is because minimizing is equivalent to minimizing: "a Z Z ) + expression (8.40),

Z(/aZa

which is equivalent to the objective function of problem (DD). Of course, will be a prohibitively large number. The Benders decomposition procedure identifies only a small subset of the extreme points ( ,1 *) of F. Let be the number of extreme points identified so far and let problem (BDD") denote problem (BDD) with the associated < TV constraints imposed on B, ie, the program in Step 1 of the procedure. As iterations proceed, increases and upper and lower bounds {LB and UB) on the optimal value of and therefore on v[DD] are calculated.

Determination of Upper and Lower Bounds Consider an optimal solution of problem (BDD") when H < N. Denote the optimal solution by (j"+,z"+,5"+). Then LB = B"\ as problem (BDD") contains only a portion of the constraints of problem (BDD) when H <N. Using (j"+,z"+>) and solving problem (8.38) produces x"+\ Then, because (x"",y"+,z"+) is feasible for problem (DD):

= 2 Z Z Z C,,% + Z (/a4" + Va Z Z « /)-

LB and UB converge as H increases; LB is monotonic increasing. When the procedure is terminated, a feasible solution to the distribution design problem (DD) that is within UB-LB of v[DD] is thereby available.

8.2 Derivation of Equations (8.41). Consider problem (8.40) for a given (, again utiHzing the h,e) notation. We have:

maximize + E(~A>«(f)f

subject to

- - =e cvKw for all 7 u,, = 0 for all j

(8.40;0

and 1 , 1, unrestricted for all Q.

As -D,eyi,ii = 0 whenever £), the corresponding ir,« in problem (8.40) has no effect on the objective fimction value. Such variables have been omitted from problem (8.40) to produce problem (8.40;0 on the condition that these x, = maxj - u,j - Cy J in any synthesized dual solution to problem (8.38). Inspection of problem (8.40;/) reveals that this is the dual of the independent transportation problem given by problem (8.39). An immediate result is that = /tj, where the are the dual variables associated with the supply constraints in problem (8.39). Also, the irj/s are the dual variables associated with the demand constraints in problem (8.39). Now ,,, 1 problem (8.40;/) must satisfy:

ir,s(p)p

and in view of the objective function coefficients -Dn 0, / / can be set equal to maxj - , - Cijuiei in any optimal solution to problem (8.40;/). These conclusions underlie the synthesized dual solution to problem (8.38) given by equations (8.41).

Floor Layout- The Quadratic Assignment Problem

The general nature of the quadratic assignment problem (QAP) is one wherein m facilities must be assigned to m different locations. Each location has available a certain amount of space that will be occupied by the facility assigned there. For each pair of facihties a non-negative weight is associated with the activity between them. The problem is to place each facility in a location separate from all other facilities in such a way as to minimize the sum of weights times distances between pairs of facilities. An example is the placement of machines on a factory floor. The weights may represent trips that occur per unit time between each pair of machines. It is desirable to keep machines relatively close together in order to conserve space and minimize the weighted-distance costs. An example of a hospital layout problem is described by Elshafei (1977).

The following floor layout application was reported by Urquhart (1977). T and Mechanical Contractors, Ltd., decided to rent a building to complete a heat exchanger fabrication contract. The job consisted of fabricating an(l assembling oil refinery radiant and convection heat exchanger sections. The tubes used were 8-inch-diameter steel pipe, about 50 feet long. The production manager sought a plant layout that minimized total material handling cost while completing the contract.

The layout problem was complicated by factors inherent to the plant structure and the work involved. Certain departments required areas of specific shape, rather than simply a certain number of square feet. Neither the shape nor the area requirements of the departments were uniform. Fitting the departments to the building structure was another consideration. Part of the shop was only 15 feet high and could not accommodate