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]
33 8.2 SINGLESTAGE, SINGLECOMMODITY DISTRIBUTION SYSTEM DESIGN Here we consider the design of a distribution system. Analysis begins with a singlestage distribution system for a single commodity (or standard product mix). The following notation is adopted: demand for the commodity in demand zone £, average unit cost of transporting the commodity from a facility at site to demand zone £, average manufacturing and/or handling costs per unit of the commodity supplied from a facility at site k, fraction of Df supplied from a facihty at site k, {hi + v,)Di, nonnegative fixed cost of operating and/or locating a facility at site k, a zeroone variable equal to 1 if a facility is to be located at site k, and equal to 0 otherwise, number of candidate sites for facility location, number of demand zones. Di = = Vk = = fk = z, = The basic mixedinteger linear program is: minimize Z + 2 / (8.13) subject to 2k  0 lz,=m 2 , 9 0 = 0 or 1 for all.? (8.14) for all M (8.15) (8.16) foralU,.? (8.17) foralU. (8.18) Constraints (8.14) stipulate that each demand zone is to be totally supplied. Constraints (8.15) guarantee that no demand zone is to be supplied from a site not chosen for facility location. Constraint (8.16) states that no more than m facilities are to be located. The optimal number of facilities may be determined as an element of the solution by omitting constraint (8.16). As there are no capacity restrictions on the facihties, at optimahty each demand zone will be supplied entirely from the most costeffective located facility (ties can be broken arbitrarily). This may be fortuitous because many firms require single sourcing of customers to gain efficiencies and ensure good customer service. Data Considerations Individual demand points are often aggregated into demand zones in order to reduce Z to a manageable number. The zones may be defined by postal zip codes and be represented by a key city with significant demand together with neighboring areas with relatively small associated demand. Using zipcoded zones facilitates linking customer demand records such as invoices with customer locations. However, more detailed demand data by geographical area are often required because billing address and delivery address frequently differ. This naturally leads to construction of an appropriate data base and anticipates development of a comprehensive distribution planning system as suggested by Geoffrion and Powers (1980). This model does not require that transportation costs be proportional to distance, in contrast to the sitegenerating (continuous) models. As Geoffrion (1975) stated. One serious limitation of continuous location models is the impossibility of achieving a realistic cost structure for transportation flows. Consider, for instance, planttowarehouse flows. For any particular warehouse location one can look up the unit transportation rates by mode, weight, and product and combine these appropriately to achieve a suitable composite unit transportation cost. It is well known that such costs in many cases cannot be reliably predicted based on a knowledge of distance alone. Yet this is exactly what must be attempted in a continuous location model: all transportation costs must be expressed as explicit wellbehaved functions of distance (no lookups allowed). In such cases continuous models might be used to generate sites based on approximate cost relationships. Siteselecting models can then be used to assist final locational decisions based on more accurate cost data (table lookups allowed). It is important to note that some sourcedestination combinations are not practicable in a given application. The associated assignment variables can therefore be omitted from the model, together with the associated assignment constraints, z,,  y« 0. This reduces data requirements and computational difficulty. Most organizations have multiple products. When multiple products share manufacturing and distribution facilities, the single commodity treated here would be a "standard commodity bundle." This is a combination of the multiple products proportional to their respective de
mands. However, if the relative demands for the products differ significantly in different demand zones, or if some products are not supplied from some facilities, this approach breaks down. Treatment of the then necessary multicommodity model is deferred until the succeeding section. The model structure has been found useful in contexts other than distribution of a commodity. When = L, and and S are the nodes of a graph, all / = 0 and equality is used in constraint (8.16), the problem becomes the socalled mmedian problem. The mmedian problem was encountered in Chapter 7 as problem (7.4). (Constraints such as z I may need to be added when attempting to solve the mmedian problem using its linear programming relaxation.) Model Representation and Linear Programming Relaxation A more compact problem formulation is possible. This is obtained by summing constraints (8.15) over jP to produce: Lz,  2 0 for all k, (8.15a) and substituting these for constraints (8.15). This reduces the number of constraints substantially. There is a pitfall here, however. Let the linear programming relaxations (8.13) through (8.17) corresponding to using constraints (8.15) and (8.15a) be denoted as the "strong relaxation" (SR) and the "weak relaxation" (WR), respectively. Problem (SR) is a stronger relaxation than problem (WR), as every feasible solution to problem (SR) is also a feasible solution to problem (WR), but not conversely. Problem (SR) renders the original mixedinteger program and the linear programming relaxation more nearly the same. In fact, computational experience indicates that problem (SR) usually produces solutions that are integer in the variables, as required by the omitted constraint (8.18). This is not true for problem (WR). In problem (SR), but not problem (WR), the z/s corresponding to chosen sites will frequently have unit values, ie, the associated facility will supply some demand zones entirely, and,  y., = 0 becomes z  1 > 0 for those zones. The remaining zs will usually have zero value. If the solution to problem (SR) does not satisfy constraint (8.18), some form of branchandbound analysis would be required. Example 8.4 Let Figure 8.1 represent a problem with 12 demand zones (population centers), which are the nodes of the graph. Let the demand zone locations be the only candidate sites for locating health outreach clinics. Let all / = 0 and define each c„ as the shortest travel distance (from Table 8.2) between nodes and £ Solving problem (SR) with constraint (8.16) written as an equality, and letting m = 3, produces the optimal integer solution indicated in Figure 8.1, with an objective value of 284 kilometers. The minimized average distance from a demand zone to the nearest clinic is therefore 23.67 kilometers. This mmedian problem would likely be solved for different values of m to construct the tradeoff curve for m versus minimized average travel distance. The assignment constraints (8.15) expand rapidly in number as AT and L increase. A computational expedient that saves required storage (and usually computational time) is to solve problem (SR) initially excluding constraints (8.15). Those assignment constraints violated by the solution are augmented to the problem and dual simplex iterations are performed to obtain the next solution. The process continues until no assignment constraints are violated. Indeed, mechanics of the (revised) simplex method may be altered to represent constraints (8.15) implicitly when solving problem (SR). Striking computational efficiency is gained because KL constraints may be represented implicitly. For example, problems with = L = require only L + 1 = 34 of 1123 constraints to be considered explicitly. The relatively minor computational burden of a great number of implicitly represented constraints (8.15) suggests that largescale problems are within computational reach of the linear programming method. We now turn to an indepth discussion of a special purpose algorithm called DUALOC, which solves a classic location problem. We provide this detailed account because the algorithm has been found to be very efficient. DUALOC Problem (8.13)(8.18), with the omission of constraint (8.16), is often referred to as the simple plant location problem (SPLP); "simple" implies the absence of plant capacity constraints. For ease of exposition we state problem (SPLP) here: minimize 2 + S/* (8.13) y,z " subject to  0 Zk,yki 0 z = 0 or 1 for all £ for all k,£ for all k,£ for all k. (8.14) (8.15) (8.17) (8.18)
DUALOC solves problem (SPLP). The efficiency of DUALOC derives from the high frequency of integer solutions derived from the hnear programming relaxation (constraints (8.18) omitted) of problem (SPLP), denoted here by problem (SRS). However, the algorithm operates on the dual of problem (SRS) denoted problem (DSRS), given by: maximize Z Vf v,w subject to fk for all for all k,S. 0 for all kX Let v[ • ] denote the optimal value of an optimization problem. Then evidently v[SPLP] v[SRS] = v[DSRS], where the equality holds by the strong duahty property of linear programming. The idea, then, is to solve problem (DSRS) in order to have a lower bound on v[SPLP]. A first attempt at solving problem (DSRS) is called dual ascent. Throughout the discussion, is to be evaluated as minCt, + wJ. Let an assignment ik,S) be called admissible if v, = c„ + „. Dual ascent begins with all vv2t = 0 and attempts to increase the ws in order to increase the vs. (The superscript indicates the iteration number.) To illustrate the method, consider the following example employed in Erlenkotter (1978). Cost data are from Khumawala (1972). Example 8.5a The ATs represent large positive numbers and indicate prohibited assignments. Let the vector (f) of fixed costs be (100, 70, 60, 110, 80). Then {Vi) = (min,{cj) = (120, 150, 100, 150, 50, 120, 110, 120). The procedure cycles through the v/s, attempting to increase each to the next higher value of To maintain feasibility in problem (DSRS), Table 8.4 Total Demand Cost c„ for an Instance of Problem (SPLP). w« s corresponding to admissible assignments must be increased simultaneously. If the X "ks < fk constraint blocks the increase of Vf to the next highest , then Vp is increased as much as the constraint allows. To specify the procedure formally, reindex the c. for each H in nondecreasing order as 4, = 1,,K, and include a cost parameter cf+ = 100. Let L+ be the index set {1,2,...,L). Then observe that for any feasible choice of Vg we can set wp = maxjO,v,  cs\. This allows the Wj/s to remain implicit in the following procedure. Dual Ascent Procedure Step 1 Set (v,) = (c)), (5,) = (  2 max \0, v,  c«j), and k{£) = 2. Step 2 Initialize 2 = 1 and 5 = 0. Step 3 It 2 f L, go to Step 7. Step 4 Set , = mint {5]v(.  c > 0). Step 5 If Af > cp<«  Vt, set Af = c/<«  Vp and 5=1. Increment k{2) by 1. Step 6 Decrease s,, by Ag for each with Vg  Cg > 0; then increase Vg by Ag. Step 7 2 L, increment 2by 1 and return to Step 3. Step 8 If 5 = 1, return to Step 2; otherwise, terminate the procedure. At the end of the first cycle we have (v = (170, 180, 110, 180, 55, 195,J 60, 155). The slacks in the potentially blocking constraints are (4) = (40, 20, 55, 0, 20). All vs have been increased to the next higher values of cg, respectively, except = 155, which is blocked by s\ = 0. After another cycle we have (vi) = (180, 190, 110, 180, 60, 195, 160, 155), whereas {si) = (20, 15, 50, 0, 0). The only unblocked Vg is . We find (v) =F= (180, 190, 110, 180, 65, 195, 160, 155), with (A) = (15, 10, 45, 0, 0), and the dual ascent procedure terminates with 1 vj = 1235. The question of whether is optimal in problem (DSRS) must now be investigated. To do this we derive a feasible (integer) solution to problem (SRS), and hence to problem (SPLP), and check optimality via linear programming optimality conditions. Let (v/) be the solution vector generated by the dual ascent procedure. Let = \k\l max iO, vc,g] = /J
[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]
