Table 3.14 Evaluation of Candidate Lines.

pairs (2,4) and (2,3) are eliminated. In larger examples, of course, the savings in computational time is much larger.

3.4 SINGLE-FACILITY DYNAMIC LOCATION

Let us assume that a facility is expected to serve over r periods of time. The facility may be relocated repeatedly during that time. To simplify matters, let us stipulate that this facility may be moved only at the beginning of each period. The reasons for relocating the facility may lie in changing costs of transportation, changing demands from the existing facilities, or even changes in the numbers and locations of the existing facilities themselves. It is obvious that if no costs were associated with moving the facility, we could relocate it optimally at the beginning of each period provided we knew the weights and locations of the existing

Figure 3.13 Candidate Lines.

facilities for that period. The inclusion of relocation costs, however, may make relocation inadvisable in some periods. Again for simplicity, we assume that relocation costs are not affected by the distance that the facility must be moved through space, but are incurred only by the act of relocation.

The first question that anses is this: How do we balance present and future costs? One approach could be not even to try. We could compare the costs of the present location with the cost of the optimal location for the forthcoming period. If the difference is greater than the cost of relocation, then we would move the facility. This myopic approach has its faults. For example, relocation costs may be very low now but may be predicted to be very high several periods hence. It may be wise to move the facility now even though the move is not strictly justified in the immediately following period.

What is needed is some way of balancing present costs against future costs. First, however, we must know future costs. It is assumed in dynamic location that future costs and the future locations of demand points can be predicted. Of course, in practice, such predictions may have a measure of uncertainty attached to them. For the present we will assume "perfect" predictions for the sake of simplicity. If future costs are known, we can take their present values and thus treat present and future costs on a comparable basis.

As a first step toward formulation, let us recall the "nondynamic" single-facility location problem of Chapter 2 as expressed in problem (2.1). We will henceforth call this problem the static problem. Problem (2.1) (renumbered for convenience) is:

minimize W(X) = / ,,).

(3.23)

We now wish to find not a single location for the facility, but a location for each of r periods. The notation of problem (3.23) must be modified to accommodate the dynamic problem. Let the weight be the present value of the cost per unit distance between the new facility and existing facility j in period k. The present value of a cost that is periods in the future is /( - )*. We will neglect the contentious practical issue of how to determine the discount rate r; much has been written about that elsewhere. Let the present value of the cost of relocating the facility in period be . The object, then, is to find a series of locations X == ( .), = l,...,r that minimize the present value of the location-relocation plan. The dynamic location problem to be considered is:

minimize 2! S X,Z

MXi,,aj) + X

(3.24)

where:

1 if X. X is allowed, 0 otherwise.

The zs serve as indicator variables that tell us whether the facility is "permitted to move" from where it was the previous period. If it is so permitted, a relocation cost is incurred whether a move takes place or not. However, if = X, then = 1 cannot be optimal. This interpretation will be used shortly.

In the problem statement (3.24), the locations of the existing facilities do not have period subscripts, and it appears (as n has no subscript) that we are assuming that the number of existing facilities does not change over time. This is not necessarily so. We can assume the creation and deletion of existing facilities over time simply by changing Wj. from zero to some positive value, or from some positive value to zero. The difficulty is that n must equal the total number of the sites that will ever be used. We only do this to simplify notation. The problem could have posed with Uk and ays and the optimization methods to be discussed would be basically unchanged.

When p = 1 distances are rectangular and problem (3.24) can be expressed as a zero-one linear integer programming problem. This formulation is explored in Exercise 3.13. The method discussed here is more generally applicable and can be used with 0. distances. Consider the vector Z = (Z2,...,z,). Any particular vector is a plan for relocation. For example, (1,0,0,1) tells us that we can move the facility at the beginning of period 2 to a new location where it must stay for two periods (we pass up two chances for relocation). We can relocate again at the beginning of period 5. Given any such vector, problem (3.24) can be solved by the methods

of Chapter 2 because cz is constant and does not enter into the

Ar-2

optimization. The example vector causes X2 = - = X, which reduces problem (3.24) to a problem in the variables X, X, and X, which in turn can be solved as three separate static problems. It is evident that if we find the costs for all possible vectors Z and pick the best one, we will have found the optimal location-relocation plan.

Example 3.5 Table 3.15 gives the locations of three existing facilities and the predicted weights for three periods.

The relocation costs Cj and Cj at the beginning of the second and third periods are 2 and 10, respectively. For ease of computation assume that distances are rectangular (p = 1). If there were no relocation costs, we could use the weight Wy, to find the best location in period 1, the weights to find the best location in period 2, and the weights to find the

Table 3.15 Three Period Locations and Weights.

best location in period 3. We can use the median weight method in Chapter 2 to find the best locations; these locations and the resulting transportation costs are given in Table 3.16.

Let us now consider a myopic location scheme. At the end of period 1 the facility is located at (3,3). If we leave it at (3,3), we can calculate the transportation cost during period 2 to be 15 (the reader should check this). If we move it to (4,5) the cost drops to 12. Because the cost of relocating at the beginning of period 2 is 2, the decisionmaker who does not look ahead to period 3 would relocate the facility to (4,5). Leaving the facility at (4,5) for the third period would mean a transportation cost of 36 (again, the reader should check this). The savings for moving back to (3,3), ie, 36-27 = 9, is not as big as the cost of relocation (10), and therefore our myopic decisionmaker would leave the facility at (4,5). In terms of the relocation vector Z, the scheme was (1,0). The total cost was: 9 + 12 + 36 + 2 = 59.

Of course, there are other schemes available, namely (1,1), (0,1), and (0,0). For example, let us calculate the best locations and cost for Z = (0,1). Because the facility must stay put for the first two periods, we can combine the weights for the three existing facilities and get 3, 4, and 5, respectively. Using conditions (2.16) with these combined weights we find that the best location for the first two periods is (3,3), giving a transportation cost of 24. Although Z specifies a move in the third period, the "move" is to (3,3) because this remains the best location. The move cost must still be charged, and so the total cost for the scheme is 24 + 27 + 10 = 61. The cost of all possible schemes is given in Table 3.17.

The above example has illustrated that we can solve problem (3.24) by evaluating all possible change plans and within each solving a set of static problems. Unfortunately, as the planning horizon increases, the number of change plans to be evaluated, 2-\ expands greatly. Exercise 3.14 asks the reader to show that the number of static problems that

Table 3.16 Best Static Locations and Costs.

Table 3.17 Total Costs for Z.

would have to be solved is 2-((r- l)/2-l-1). For example, ifr= 10, this number is 2816.

Fortunately, the amount of work involved can be greatly reduced by a simple branch-and-bound approach. The key is the following observation: Once a move is specified by the Z vector, subsequent optimal locations are not dependent on the preceding location "history." This leads to the conclusion that many of the static problems solved in the total enumeration of the Z vector are identical. The scheme to be explained avoids this duplication.

Let Z be that part of the Z vector pertaining to periods through r. For example, if Z = (0,1,1,0,1), = (1,0,1) and indicates that there is a move in the fourth period, none in the fifth, and a move again in the sixth. Let C(Z,J be the optimal cost connected with vector Z. This cost includes the lowest transportation costs possible in periods through r inclusive given change plan Zj, and includes the appropriate relocation costs. We begin our search for the best plan with period k. This search is illustrated in Figure 3.14. Inside each circle is a number; 1 indicates a relocation, 0 indicates that no relocation was made.

Costs where Z begins with 0, ie, C(0,1,0) or C(0,0), cannot be evaluated because the location of the facility at the beginning of period is not known. Let us ignore this difficulty for the moment. Consider the costs C(1,0) and C( 1,1) in Figure 3.14. Suppose C(l,l) > C(1,0). We can then remove the branch below C(l,l) from further consideration; in other words, we know that any plan that calls for a relocation in the r-1" period must require no change in the r period in order to be optimal. We generalize this procedure as follows: At each period k, we cancel all branches where the cost C(Z) is higher than the lowest.

Fortunately, we can do even more pruning. Let Z be any vector that starts with zero and Z be a vector identical except that it starts with one. For example, if Z = (0,1,1,0,1) then Zl = (1,1,1,0,1). First we justify the following inequality:

C(Zl) C(Zl) - c.

(3.25)

On the right-hand side, the k" period move cost is subtracted from the optimal cost of the scheme that allows a move in that period. This net

3.4 SINGLE-FACILITY DYNAMIC LOCATION

period r C(1)

period r-2 C(1,1,1)

Figure 3.14 Decision Tree for Relocation.

amount cannot be larger than the optimal cost of the scheme that doesnt allow a move in the period. Now define:

Z(Z?) = C(Zi) - c.

(3.26)

The cost L(Zl) is the lower bound on what the cost of a branch (from period k+1 on) can be. If it is higher than some cost C(Zj.), it follows that this branch also can be dropped. With some luck, and if we are not fussy about keeping ties, it is often possible to prune rather substantially the tree in Figure 3.14.

Example 3.6 The data in Example 3.5 were used to illustrate our "tree-pruning" method; Figure 3.15 gives the details. Note that the branches bearing the costs £(0,1) and C(l,l) were eliminated because they could not possilly be superior to the branch labeled C(1,0). The final result is that Z = (1,0) is the best location-relocation plan-the same solution that was found by complete enumeration of Zs in Example 3.5. The computation savings are not apparent in this small example, but would be in a larger one.

The basic concept of dynamic location was illustrated here with simple cost assumptions and with a simple single-facility location problem. Naturally, this concept can be extended to more complex problems.