requires that exactly m new facilities are to be located. Problem (7.4) is a mixed-integer linear programming problem that has been termed the m-median problem. Special purpose solution methods are discussed in the following chapter. We note that compared to solving the resulting m-median problem, the computing time required to generate I, is negligible.

More on Hulls

There is a hull related to that must contain the entire set of optimal solutions to problem (2.10). We will denote this hull by E. For the example given after the statement of Property 7.1 where n = 2, a, = (2,0), and 2 = (0,1), the elements of E are the points in the rectangle with corners at a, and - If vw, = W2 = 1, this is indeed the entire set of optimal solutions. The following property indicates when a point cannot solve (the cZ-dimensional case of) problem (2.10), and is therefore not in E„.

Property 7.3 [Exclusion property for £«]. If for X = (x„X2.....xJ any two

sets, say A and B, chosen from among the 2d sets and Gk= 1,2....,d are disjoint, and if A and are not collectively exhaustive with respect to J, then XiEn and X cannot be optimal in the d-dimensional case of problem (2.10).

Property 7.3 implies that « is a subset of E. Reconsidering the intersection point X = ( ,„ 2) in Figure 7.7 the only disjoint pair of sets is and Lj. As the union of L, and Lj is {1,3,4,5} J, we find that X is neither in „ nor in E,. The following example illustrates the use of Property 7.3 to analyze a three-dimensional problem.

Example 7.2 There are four offices in a two-story building, with coordinates as given in Table 7.5. A copying machine is to be located to minimize the sum of weights times distances to the existing offices.

The intersection set / (which must contain an optimal location) contains eight points, of which four are existing office locations. The remaining four points are analyzed in Table 7.6, using Property 7.3. As a

Table 7.5 Present Office Locations and Weights.

Table 7.6 Using Property 7.3.

result, we conclude that the set \ „ 2, , ,(0,1,0) must contain an optimal location.

The total cost values ) = /.(Z,) for each Xd are shown in

Table 7.7. The optimal location of the copy machine is :* = (0,1,0). We note that X* is outside the convex hull of existing office locations.

Table 7.7 Values of W{.X) for Each Xd.

For two-dimensional location problems of the form (2.17) such that the new facilities are chained and 1 < < , the smallest set that must contain the entire set of optimal solutions is the convex hull of the existing facility locjitions. Because the convex hull contains an infinite number of points, the transformation of the associated location-allocation problem to the w-median formulation [where in problem (7.4) must be finite] is no longer possible. Even if p = 1 but is a large number, the m-median approach becomes impractical. The need for heuristic solution procedures becomes apparent.

7.4 LOCATION-ALLOCATION HEURISTICS

In this section we present heuristics for solving relatively large instances of problem (7.1). We first formulate the problem as a concave minimi-

zation problem with Hnear constraints (concave minimization problems are nonUnear programming problems whose objective is to minimize a concave objective function). A heuristic strategy is then developed based on this structure.

Structural Properties

When IV in problem (7.1) is temporarily held fixed (such that each w,, 0), the problem reduces to a pure location problem. Then from problem

(5.31) (with all -,,, = 0), letting Uu, p > 1 can be written as:

HI n

max DMiU) = 2

f/,„ the dual location problem with

subject to

(7.5)

2 = 0, /• = l,...,m,

\\UJ

i = l,...,m\j = 1,...,«,

where q = p/(p-1) and 0 denotes a vector of zeros. From Chapter 4 we know that when p = 1, we can write the pure location problem as a linear programming problem. Hence, forp = 1, the dual location problem also can be written as a linear programming problem. Problem (7.5) is a nonhnear programming problem.

Consider the perturbalion function v( W) which is defined as the optimal value of problem (7.5) for a given W 0. When /» = 1, v{W) is the optimal value of the associated linear programming dual problem. We invoke the following result for v( W).

Property 7.4 [Concavity of the perturbation fiinction]. v(W) is a concave function on the set of Ws such that W 0.

A proof found in Geoffrion (1971) shows that ~v{W)h convex and hence that vW) is concave. Using Property 7.4, we may state problem (7.1) as the following concave minimization problem:

minimize v{W) W

subject to

(7.6)

S = W„ j = 1,

w,j > 0, = \,...,m-J = 1,...,«.

Heuristics

Although algorithms for concave minimization problems are available, large instances of problem (7.6) are yet beyond their computational reach. One property of problem (7.1) that follows from the concavity of v{W) is that the optimal solution must lie at an extreme point of the feasible region in (7.6). A logical computational strategy, therefore, is to search along such extreme points. [We should emphasize here that an objective fiinction value in problem (7.6) is realized only when, given the current Wij values, the locations for all new facilities are optimal.] An algorithm that proceeds from one extreme point (basic solution) to an adjacent extreme point (one basic variable changed) is not guaranteed to reach optimality for concave minimization problems in general, however. The HI, H2, and H3 heuristics given below are of this type. A more elaborate heuristic is to change two basic variables at a time in order to "step over" adjacent extreme points, in addition to investigating adjacent extreme points. The H4 and H5 heuristics are of this type.

The H4 and H5 procedures are analogous in linear programming to testing all possible pairs of nonbasic variables for entry into the basis at each step of the simplex method, in addition to testing all single nonbasic variables for entry to the basis. For linear programming problems, the examination of pairs of nonbasic variables for entry into the basis is not necessary, as a single variable entry method (the simplex method) converges to optimality. However, because problem (7.1) typically has many local minima, testing pairs of variables for possible entry into the basis at each iteration enables the algorithm to step over a local optimum, thus increasing the chances of reaching a global optimum.

Because problem (7.6) contains n linear equality constraints, there will be n basic variables in a basic solution. Furthermore, each constraint must include one basic variable. Since basic feasible solutions correspond to extreme points of the feasible region, each extreme point corresponds to allocating each of the n existing facilities to a single new facility. Consideration of a pair of variables for entry into the basis corresponds to changing the allocations of two existing facilities.

All of the tested heuristics start with a trial solution to problem (7.1). Then the solution is perturbed by changing the allocations systematically, each time determining the associated optimal locations. Five procedures with varying degrees of perturbation are investigated. Each of the methods starts with an arbitrary allocation. Each method stops when the perturbations do not produce any further improvement. The following describes the perturbations employed for each heuristic.

HI: For each new facility /,, /, = l,2,...,w, the new facility /2 closest to , is found. Among the existing facilities allocated to i,, the one closest to i is tentatively reallocated to z,. Once an improvement is found, the perturbation scheme is restarted.

H2: For each new faciUty i, each existing facility is tentatively reallocated to i (if not already allocated to 0- Once an improvement is found, the perturbation scheme is restarted.

H3: This heuristic is identical to H2 except that all tentative reallocations are checked in order to adopt the best one before the perturbation scheme is restarted.

H4 and H5: These heuristics are similar to H2 and , respectively, except that reallocations here additionally involve two existing faciUties. In H5 all possible pairs as well as all possible single existing facilities are tried at each iteration.

Specifically, the procedure for H5 is as follows:

Procedure for H5

Step 0 InitiaUze "least cost achieved thus far" to a large number. Step 1 Set i = 0.

Step 2 Set i = i+l. If i > m, go to Step 9. Otherwise set y, = 0 and go to Step 3.

Step 3 Set 7, = y, -I- 1. If 7, > n, go to Step 2. Otherwise, set J2 = J, and go to Step 4.

Step 4 Set 7, = J2 + 1. If J2 > «, go to Step 3.

Step 5 If existing facilities j, and J2 are both allocated to new facility /, go to Step 4.

Step 6 Allocate existing facilities 7, and J2 to new facility /. (Note that either of the existing facilities y, or J2 may already be allocated to new facility In this case, a single existing facility is being reallocated.)

Step 7 Check to see if any new facility has no existing facilities allocated to it. If so, reverse Step 6 and go to Step 4.

Step 8 Optimally locate all m new facilities and compute the total cost. If this cost is less than the least cost achieved thus far, record this new cost, the corresponding allocations of existing facilities, and the locations of new facilities. Go to Step 4.

Step 9 Check if i has been completely indexed from 0 to m once without recording an improved solution. If not, go to Step 1. Otherwise, the best solution recorded to date in Step 8 is reported, and the procedure terminates.

The procedure for H4 is identical to H5 with the exception that as soon as a pair change produces a reduction in total cost, that pair change

is adopted and the perturbation procedure is restarted at Step 1. Heuristics H2 and H3 are less likely to produce optimal solutions, but require less computation time than H4 and H5.

To test the five heuristics, data sets (a/s and w/s) for 28 problems with rectangular distances were generated randomly. Optimal solutions were found by determining and solving the ,M-median formulation (7.4). Table 7.8 shows the percentage by which the cost of the solution found exceeds the optimal cost (0% means less than 0.5%). A dash (-) indicates that an optimal solution was found. Optimal solutions were found in all cases by H4 and H5. Computation times were minimal.

A second set of 74 randomly generated rectangular distance test problems ranging in size from m = 2, n = 11 to m = 3, = 16 were optimally solved using the -median approach and then resolved by H5. Again, optimal solutions were produced in all cases. Further testing indicated that problems with w = 2, = 100 and m = 5, n = 60 can be "solved"

Table 7.8 Sample Results for the Heuristics.