8.2 SINGLE-STAGE, SINGLE-COMMODITY DISTRIBUTION SYSTEM DESIGN

Here we consider the design of a distribution system. Analysis begins with a single-stage 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,

non-negative fixed cost of operating and/or locating a facility at site k,

a zero-one 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 mixed-integer 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 cost-effective 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 zip-coded 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 site-generating (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, plant-to-warehouse 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 well-behaved functions of distance (no look-ups allowed).

In such cases continuous models might be used to generate sites based on approximate cost relationships. Site-selecting models can then be used to assist final locational decisions based on more accurate cost data (table look-ups allowed).

It is important to note that some source-destination 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 multi-commodity 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 so-called m-median problem. The m-median 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 m-median 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 mixed-integer 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 branch-and-bound 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 m-median 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 large-scale problems are within computational reach of the linear programming method.

We now turn to an in-depth 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 non-decreasing order as 4, = 1,-,K, and include a cost parameter cf+ = -1-00. 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, v-c,g] = /J