Computing Time

-►-1-1-1----I-1-1-1-1- m

10 20 30 40 50 60 70 80 90

Figure 7.5 Computing Time in Relation to w for n = 100.

bution system with m m* distribution centers is relatively flat in the neighborhood of m*.

7.2 SOLVING THE TWO-FACILITY EUCLIDEAN DISTANCE PROBLEM

Suppose that two distribution centers are to be located in relation to the demand points depicted in Figure 7.1, and that Euclidean distances are used in problem (7.1). Imagine a line drawn between the points labeled with weights 2.5 and 86.8. Call these points A and B, respectively. The line defines two possible allocations of the 19 demand points. One allocation includes demand point A with the group of points to one side of the line and includes demand point with the group of points to the other side of the line. The second allocation reverses the group associations of demand points A and B. Another conceptualization is to think of the Une as being rotated slightly, first clockwise and then counterclockwise about an axis on the segment between points A and B. In this way the two different partitions of the 19 demand points are graphically apparent. This is a useful construction because it is readily proven that there is an optimal partitioning of the demand points such that the two groupings of the points are strictly separated by some straight line.

More formally, let be the index set {\,2,...,n\; let ( , ) be a partition of the set J, ie, 7, and J2 are mutually exclusive and collectively exhaustive with respect to J. Then the two-facility location-allocation problem with Euclidean distances has an optimal partition ( . ) such that locations of existing facilities with indices in are strictly separated by some straight line from the locations of those with indices in Jf. There are

Cost (per unit time)

Weighted-Distance Cost

--I-► m

1 2 3 4 5 6 7 Figure 7.6 Cost Versus the Number of New Facilities.

n(n-1)/2 pairs of existing facility locations. Each pair determines a line, which in turn determines a pair of partitions. Hence we need only consider n{n-\) partitions if no three existing facility locations lie on the same line, and fewer otherwise. The maximum number n{n- 1) of these candidate partitions is much smaller than the total number 2"--1 of partitions of J that would have to be examined using an exhaustive enumeration approach.

Perhaps the case of three collinear existing facility locations needs am-plificatk)n. Suppose the line through the demand points labeled with weights 24.0 and 67.0 in Figure 7.1 also passes through the point labeled with weight 86.8, that we have called B. Call these additional points and D, respectively. This single Une corresponds to the three point pairs , BD, and CD. Potentially there are two partitions to be considered for each point pair. However, we see that only four partitions need actually be considered in this collinear case. These are the two partitions for which points and are in one grouping while point D is in the other grouping, and the two partitions for which points and D are in one grouping while point is in the other grouping. By the strictly separating line property of an optimal partition, points and D cannot be in one grouping while the point (between and D on the same line) is in the other grouping.

There are several ways to implement these ideas to create an algorithm. In the discussion to follow we will not distinguish between a subset I of

the index set J and the corresponding subset \aj\jtl\ of the existing faciUty locations. Consider an optimal partition {J,!) and an associated strictly separating line. Move the line parallel to itself toward the grouping of points in Jf until it first passes through one or more points in Jf (J cannot be empty in an optimal partition). This means there exists a line passing through a point of Jf such that all points on the line or to one side belong to /f, while the points on the other side of the line belong to Jf. Summing up, we need only consider those partitions (J,,) as candidates for optimahty for which J, and are separated by a line passing through some existing facility location in J,, termed the "pivot." If for each such partition we solve the corresponding pair of single-facility location problems defined by /, and Jj, and the least pair-wise sum of minimized single-facility objective values is chosen, then the two-facility location-allocation problem with Euclidean distances will have been solved. The following is a method for determining candidate partitions.

Drezner Algorithm

For each 7 = 1,2,...,«, let a, be the pivot point. Then for each r j, calculate the angle, say 9,., that the ray originating at the pivot aj and passing through a, makes with the positive A-.-axis. Sort these - 1 angles in nondecreasing order. Then, for a given angle 6, let 7,(6) include aj together with existing faciUty locations a, such that , + , and let J2{e) = J ~ Ji(e). To obtain the candidate partitions with as the pivot, begin with = 0° and generate (J,(0°),/2(0°)). Then choose the least angle from among ,, 2,..., , „ ,„...,9„ for which J,(6) is different from /,(0°). Ingeneral, suppose has just been considered. Calculate a = min{e,j6l,. > ] and = { ,\ , > + ]. Then = { , - } is the next angle after for which J,(e) is different from ,(5). Increase from to and continue until .

A logical question is whether or not an analog of the strictly separating line property for the two-facility problem exists for the three-facility problem with Euclidean distances. Viewing Figure 7.3 we see that a three-way partition of a set of points is based on a configuration of three rays emanating from a single point. That point may or may not be inside the convex hull of the existing facility locations. The way to an efficient algorithm that checks all three-way partitions using this observation is not yet clear.

7.3 SOLVING RECTANGULAR DISTANCE PROBLEMS AS m-MEDIAN PROBLEMS

In this section we single out the case of problem (7.1) with p = I. The two-dimensional rectangular distance location-allocation problem contains structure inherited from the location problem that can be exploited.

Furthermore, optimal aUocations are often close to the optimal allocations for the distance problem.

As we are not considering capacity restrictions in problem (7.1), the requirement w, of each existing facility will be optimally aUocated entirely to the closest new facility. Hence, before the location-allocation problem is solved, every existing facility is potentially in the allocation set of every new facility. This means that the set of candidate points for optimal location of each new facility is the same as that for a single new facility serving all n of the existing facilities. From Property 2.5 we observe that at least one optimal location for the single-facility rectangular distance location problem is included in the set /, say, consisting of intersection points of lines drawn vertically and horizontally through the existing facility locations. Call this the inclusion property. As set / satisfies the inclusion property, / must include a set of optimal locations for the location-allocation problem when distances are rectangular.

We now show how to construct a subset /r, say, of set / that also satisfies the inclusion property. Figure 7.7 shows six existing facility locations and their associated convex hull. The intersection points marked by a circle together with the existing faciUty locations make up the set 7. These are points in set I that are also in the so-caUed rectangular hull of the existing faciUty locations. Let the rectangular hull be denoted by H, and as in the previous section, let J = {\,...,n] be the index set for the existing facilities. Then is defined as the set of points X = (X,X2) that satisfy the following four conditions simultaneously:

X < ai and A-2 > a2 for some jtJ, Xl a„ and ajj for some jU, A, and Xj < aj2 for some jd, " V A, = and X2 3= aj2 for some jtJ.

Figure 7.7 Intersection Points for Six Existing Facilities.

□ Intersection points eliminated

Remaining candidates for new facility location-intersection points in Ir

• Existing facility

(7.3)

31134, ag.

32, .

These four inequahties specify that for each point X in Hr. at least one existing facility lies no farther west and no farther north than X; at least one lies no farther east and no farther south than X; at least one lies no farther west and no farther south than X; and at least one lies no farther east and no farther north than X, respectively. This implies a geometrical interpretation of the rectangular hull. is the set of points that cannot be reached by translation of any quadrant of the coordinate system without including one of the existing facihty locations as an interior point of the quadrant. In Figure 7.8 the shaded region (including its boundary) plus all the outlying existing facility points together with their connecting lines to the shaded region constitute Hr. From Figure 7.7 we observe that the intersection point ( . ,) marked by a square is in the convex hull, but is not in the rectangular hull H, and is therefore not in I. The following property establishes the significance of H.

Property 7.1 [Inclusion property of the rectangular hull]. An optimal solution to the single-facility rectangular distance location problem given by problem (2.10) is included in Hr.

The proof is given in the Appendix, mathematical note 7.1. As a simple example of the inclusion property of Hr consider the case: = 2, vw, = - = 1, , = (2,0), and «2 = (0,1). Then / = !(0,0),a„a2,(2,l)j and H = { , = /r, as is the intersection of H and /. Points in the entire rectangle with corners at a, and aj are optimal for problem (2.10). We see that unless the optimal location is unique, Hr doesnt necessarily include the entire set of the optimal locations. Typically, four distinct existing facilities are needed to satisfy the four pairs of inequalities in conditions (7.3). An exception occurs when X = a„ in which case a alone suffices. This shows that the existing facility locations are always in and, hence, in /«.

Figure 7.8 Rectangular Hull «.

322 62 352 «32

• Existing facility

The set Ir may be determined from the intersection set / using conditions (7.3). For reference we state this central result as a property. Define the index sets Gj. = aJ and U = i/fc/K aJ for = 1,2.

Property 7.2 [Determining the set /„]. The point X = (x„X2)d satisfies conditions (7.3) and is hence a member ofiR, if, and only if no pair of sets, G„ L2 or Ll, G2 or Gj, G or L,, L2 is disjoint.

For example, the intersection point X = ( . ,) in Figure 7.7 defines the sets L, = 5,1}, L = (3,4), G, = il,4,6,2,3) and G = 3,5,6,2,1). Because the pair of sets L,, L2 is disjoint, the fourth pair of inequahties in conditions (7.3) is violated, and we conclude X/.

Transformation to an / -Median Problem

Suppose we wish to solve problem (7.1) with p = \. We have estabhshed that an optimal set of locations for the new facilities will be contained in Ik. Let the points in be denoted by ., = \,..., , and let:

Ci,i = Wj£i{Pk,aj), which is the weighted-distance cost of allocating the entire requirement vv, of existing facility j to a new facility at location ,

yi,j = proportion of requirement Wj of existing facility j allocated to a new facility at location P,, = 1 if P is chosen as a location for a new facility; or 0 otherwise.

Then an optimal solution can be found by solving:

minimize X Z ( y,z

subject to

1 , =1

/1=1

, - =>

1 2, =

(7.4)

for all j for all k,j

= 0 or 1, yf,j > 0 for all k,j.

The first set of constraints ensures that the requirement of each existing faciUty is fully allocated. The second set ensures that there is no allocation to location P unless a new facility is located there. The final constraint

"]