back start next
[start] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [ 37 ] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]
37 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 = maxJ0ctJ = maxic,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 (nAfx!A,)],0 < UB~( = 10550. The coefficients for j in the objective function and in the UB~i constraint are given in the following display.  175[4(150) 6(25)] = 925  75[6(50) 8(25)] = 575  475[11(450) 13(25)1 = 5750   350[6(150) 8(25)] = 1450  150[4(50) 6(25)] = 500  950[9(450) 11(25)1 = 5275   350[8(150) 10(25)1 = 1800  150[4(50) 6(25)1 = 500  950[7(450) 9(25)1 = 4325   175[12(150) 14(25)1 = 2325  75[8(50) 10(25)] = 725  475[5(450) 7(25)1=2900 
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 UBLB = 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:
£ 1 150 50 0  600 0  1 25 25 0  50 0  2 0 0 450  600 0  2 0 0 25  50 0  D,, 150 50 450   D2, 25 25 25   MINIMUM COST  = 3150  MINIMUM COST  = 525 
T\y) = 3150 H 525 = 3675. Using expression (8.45), compute: 4 2 3 S ( 4 + V, 2 2 AA) + Tiy) = 3000Z, + 3000Z, k] il ei + 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 mixedinteger 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 singlestage distribution models provides a convenient yet powerful basis for evaluating potential demand point aggregations in singlecommodity distribution planning. The property extends to twostage 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 5, < 2 < Sj  for all j  (8.49)   for all  (8.50)  2 = 1  for all £  (8.51)  V,z, < 2 V,z,  for all  (8.52)  Xjk > 0, 0 < jAf 1, Za = 0 or 1 for all j,k,2.  (8.53) 
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 facilityrelated costs. All other notation has been used previously and is selfevident. 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 boundtwostage 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 multicommodity singlesourcing distribution design problem (DD).
EXERCISES 8.1 Complete the tradeoff 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 setcovering 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 secondstage problem is to decide which available fire companies to relocate into the empty houses identified in the first stage. However, this twostage strategy may yield suboptimal solutions because there may be multiple optima in the firststage problem. All alternate optima for the firststage 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 firststage 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 setcovering 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   > X,  for all 2    » X,  for all S.        = rt     < 21  for all 
zi,zi = 0 or 1, for all A: and .v, = 0 or 1, for all jP,
[start] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [ 37 ] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]
