7 12 3

1

12 9 8 5

6 14 11 10 10 7

Each transportation subproblem involves 2 sources (plants) and 3 destinations (demand zones). The solutions are shown below. These represent x and with the understanding that all -0 for

-Ui(P)g

j I 2 3 S„ „

1 150 0 0 600 0

2 0 50 450 600 0

Z)„ 150 50 450 MINIMUM COST = 3250

7 1 2 3 S2j lv

1 25 0 0 50 0

2 0 25 25 50 0

A, 25 25 25 MINIMUM COST = 575

Tly) = 3250 + 575 = 3825, so UB = 6725 + 3825 = 10550, presently. Store {y\z,x) as the incumbent solution to the distribution design problem (DD). As UB - LB = 10550 - 6725 = 3825 > « = 0, proceed to Step 3.

Step 3 ul = ix]j = 0 (as found in Step 2) for all ij

TTJAp = maxJ-0-c„tJ = maxi-c,itf,-c,2j, which gives the following:

Sel H = 0 + \ = \ and return to Step 1. Step 1 For convenience, use problem (8.47) for the master problem in Step 1, and therefore we must solve:

minimize SOOOz, + 3000z2 + -I- 3000z4

4 3 2

subject to

constraints (8.34), (8.35), (8.44), and

3000z, + 3000Z2 + 3OOOZ3 -f- 30OOZ4

+ E fZ E (nAf-x!„A,)],-0 < UB~( = 10550.

The coefficients for j in the objective function and in the UB~i constraint are given in the following display.

Though only a feasible solution is required, the problem was solved optimally to produce z, = z = y,, = 2 = 4 = 1 and all other variables equal to zero. This represents (yz). The optimal objective value is 10400. As = 1, this is also the optimal value of in Step 1. Hence we have a viable lower bound given by LB = 10400. Presently UB-LB = 10550 - 10400 = 150 > ˆ, so we proceed to Step 2.

Step 2 Now il) = 1, 2) = 1, 3) = 4. Objective function coefficients for the independent transportation problems are:

J 1

J 1

6 8 11 10 12 7

The respective solutions are:

£

T\y) = 3150 -H 525 = 3675. Using expression (8.45), compute:

4 2 3

S ( 4 + V, 2 2 AA) + Tiy) = 3000Z, + 3000Z,

k-] i-l e-i

+ I75y,, + 75y,2 + 47543 + 3675 = 10400 < UB = 10550,

so UB becomes 10400 and (y,z,x) becomes the new incumbent solution. This solution is optimal because UB - LB = 0. It calls for locating a DC at site 1 to serve demand zones 1 and 2, and locating a DC at site 4 to serve demand zone 3. The optimal transportation variables are given by:

x,,i, = 150, x,2,2 = 50, x,243 = 450, Xj,,, = 25, X2243 = 25, and all others equal to zero.

Only two iterations were needed for convergence even though the suboptimality bound e was set to zero, requiring an exact optimal solution. (To gain a greater appreciation of this decomposition approach, the reader is invited to attempt solving the problem in its original form using any available mixed-integer programming computer code.) It must be emphasized that successful computer implementation of the algorithm is not straightforward. This would involve sophisticated computer science, and some cleverness.

8.4 DEMAND POINT AGGREGATION ISSUES REVISITED

The demand point aggregation error bound given by Property 8.2 for single-stage distribution models provides a convenient yet powerful basis for evaluating potential demand point aggregations in single-commodity distribution planning. The property extends to two-stage distribution system design for the case of a single commodity when single sourcing of customer is not required. The following model serves as a frame of reference:

minimize 2 S

x,y,z j *

CjkXjk

(8.48)

subject to

Slightly revised interpretations are used here:

Xjk = annual amount of flow from procurement zone j to a faciUty at site k,

= fraction of demand Dg satisfied by a faciUty at site k, Cjk = average unit cost of procurement plus transportation from procurement zone j to site k, ki = annual variable costs incurred if demand point £ is served fully by a facility at site k\ typically includes transportation plus facility-related costs.

All other notation has been used previously and is self-evident. The amount of flow from a facility at site to demand point £ is exactly . Therefore, the outbound transportation flow information resident in the £ subscript ofxjks is superfluous, given the f%, and has been dropped. Property 8.2 can now be restated for the present context.

Property 8.3 [Customer aggregation error bound-two-stage distribution]. L0 L,.....Lf, be disjoint subsets of demand point indices satisfying,

for each h, the condition: for each .PeL,,, the same k£ links exist. Then, if

for h = \,...,H and all k, the ygS are identical over jPeL,

(8.54)

v[problem (8.48)-(8.53)] =¸ v[problem (8.48)-(8.54)]

s v[problem (8.48)-(8.53)] +

where t,, =

max.

An analogous aggregation property has not been developed for the multi-commodity single-sourcing distribution design problem (DD).

EXERCISES

8.1 Complete the trade-off curve started in Figure 8.2.

8.2 Kolesar and Walker (1974) Consider the dynamic fire company relocation problem described in Section 8.1. The output of the associated set-covering problem is a set of empty fire houses to be filled so that all RNs are covered with a minimum number of fire company relocations. A second-stage problem is to decide which available fire companies to relocate into the empty houses identified in the first stage. However, this two-stage strategy may yield suboptimal solutions because there may be multiple optima in the first-stage problem. All alternate optima for the first-stage problem must be considered in the second stage to guarantee an optimal relocation. The following problem considers both stages simultaneously:

minimize X (c,t + w)x,„

subject to

X X,, = 1 for all i

A V

S 2 " -. + X «< , > 1 for all e

x,j = 0 or 1 for all i and k,

where / = 1,...,N refers to available fire companies, = 1,...,K refers to empty houses, and £ = l,...,L refers to RNs associated with both empty houses and houses occupied by available companies, x,„ = 1 indicates company / isnt relocated, c,t is the "cost" in increased system response time for relocating company / into empty house k, and w is a large positive number.

a. Explain the model in detail.

b. Give another location application for this model and explain why the model applies.

c. Consider an alternative approach. Solve the first-stage problem to obtain g*, say, the minimum number of companies that need to be relocated. Then solve the following problem:

minimize max jc,j ,» = Ij

subject to

together with the constraints above. Contrast this approach to relocation with the approach implied by the combined problem.

d. Describe how Miniekas algorithm might be adapted to solve the program in Exercise 8.2c.

8.3 a. Plane and Hendrick (1977) Explain how the objective in problem (8.12) accomplishes the intended purpose, b. Daskin and Stern (1981) Emergency medical service (EMS) vehicle deployment might be guided by the following hierarchical set-covering model:

minimize w X ~ 1 x,

subject to

X azj - x« > 1

for all e

= 0 or 1 for all

X, 3s 0 and integer for all £,

where a„ is 1 if the expected response time of an EMS unit traveling from zone to RNs is acceptable and is 0 otherwise; x<, = number of additional EMS units capable of responding to RN, in an acceptable time; = 1 if a unit is to be located in zone and 0 otherwise; vf is a positive weight.

Explain how the model works and how to determine w; then solve the problem with coefficients from Table 8.3 and w = 13.

8.4 Schilling, Elzinga, Cohon, Church and ReVelle (1979) The problem is to locate engine (pumper) companies and truck (ladder) companies in a study of the Baltimore City Fire Protection System. A model considered is the following:

" v maximize 2 ff x,z\z>

subject to

zi,zi = 0 or 1, for all A: and .v, = 0 or 1, for all jP,