Question 10.17: Using the Shannon/Ignizio heuristic to solve a partial cover...

Consider a facility location problem involving five customers and four potential sites for locating, at most, three facilities. The distances between customer locations and potential sites are given as follows:

The number of trips made monthly between facility $j$ and customer $i$ equals $75,171,153$, 137 , and 805 for $i=1, \ldots, 5$, respectively. The objective is to assign facilities and customers to sites in order to minimize the total distance traveled in a month. Multiplying the distances and frequencies yields the following matrix of $a_{i j}$ values for the partial cover problem:

The Shannon/Ignizio heuristic algorithm is as follows:

1. First site selection. Let the cover matrix $\boldsymbol{A}$ consist of $n$ column vectors $\boldsymbol{a}_{1}, \ldots, \boldsymbol{a}_{\boldsymbol{n}}$. Calculate $c_{j}=\sum_{i=1}^{m} a_{i j}$ for $j=1, \ldots, n$. Let $t$ correspond to the site index having minimum $c_{j}$. Let $\boldsymbol{a}^{*}=\boldsymbol{a}_{t}$, set $x_{t}=1$, and place $t$ in the ordered set $\theta(x)$, where $\theta(x)=\left\{t: x_{t}=1\right\} .$ If $k=1$, go to to step $7 ;$ otherwise, go to step $2($ see Table 10.5 $)$

2. Selection of next site. For each $j \notin \theta(x)$, calculate

Where $\boldsymbol{a}^{*}=\left(a^{*}{ }_{i}\right) .$ If all $D T C_{j}=0$, go to step 4 ; otherwise, let $t$ correspond to index $j$ having maximum $D T C_{j}$. Set $x_{t}=1$, place $t$ in the next position in $\theta(x)$, and go to step 3 (see Table 10.6).

3. Formation of best combination. Let $\boldsymbol{a}^{*}=\left(a^{*}{ }_{i}\right)$, where, for $i=1, \ldots, m, a_{i}^{*}=\min _{t \in \theta(x)} a_{i t}$. If $\sum_{t \in \theta(x)} x_{t}=2$ and $k=2$, go to step $7 ;$ if $\sum_{t \in \theta(x)} x_{t}=2$ and $k>2$, go to step 2 ; otherwise, go to step 4 (see Table 10.7).

4. Formation of current assignment. Let $b=\sum_{t \in \theta(x)} x_{t}$. Thus, $\theta(x)=\left\{j_{1}, \ldots, j_{b}\right\}$. Let $R=\left(\boldsymbol{a}_{j_{1}}, \boldsymbol{a}_{j_{2}}, \ldots, \boldsymbol{a}_{j_{b}}\right) .$ If step 4 is entered directly from step 2, go to step $7 ;$ otherwise, go to step 5 .
5. Combination improvement and elimination check. For each column of $R$, calculate

If $\min \Delta T C_{t}=\Delta T C_{j_{k}}$, go to step 6 ; otherwise, remove from $R$ the $\boldsymbol{a}_{t}$ having min $\Delta T C_{t}$, remove $t$ from $\theta(x)$, set $x_{\mathrm{t}}=0$, set $a_{t}^{*}=\min _{t \in \theta(x)} a_{i t}$, and go to step 2 (see Table 10.8).

6. Check. If $b=\sum_{t \in \theta(x)} x_{t}=k$, go to step 7 ; otherwise, go to step 2 .
7. Assignment. From matrix $R$, for each value of $i i$, find the index $t$ having $\min _{t \in \theta(x)} a_{i t}$. 

   Assign customer $i$ to a facility at site $t$ for those $i$ and $t$ corresponding to each min $a_{i t}$ (see Table 10.9).

For the example, facilities are to be assigned to sites 2,3, and $4 ;$ customers 1 and 2 will be served by a facility at site 2 , customers 3 and 4 will be served by a facility at site 3 , and customer 5 will be served by a facility at site $4 .$

Now, let’s use the $\text { Excel }^{\circledR}$ SOLVER tool for this example. Figure $10.25 a$ depicts the setup of the partial cover problem for a SOLVER solution.

Because of the presence of the number 999,999 , an explanation of the entries in column $F$, rows 3 through 7 is in order. The entry in cell $F 7$ is shown. Notice, it consists of a MIN worksheet function, within which are embedded four IF worksheet functions. The IF function plays the same role as $\theta(x)$ in the Shannon/Ignizio heuristic algorithm; namely, only those sites at which a facility has been located are included in the MIN function. The MIN function ensures that a customer is assigned to the closest facility; it contains the minimum $a_{i j}$

value for each customer $i$. Since we do not want to assign a customer to a site at which no facility has been located, if the entry in row 8 for a particular site is 0, then a very large number is entered in the MIN function for that particular site; otherwise, the $a_{i j}$ value is entered. Since we initialize the SOLVER search by assigning values of 0 for all $x_{j}$ values, all entries in $\boldsymbol{a}^{*}$, the vector of weighted distances from customers to the nearest facility, have the value 999999. Column G contains the assignment of customers to sites; the entries consist of a number of embedded IF functions which compare the $a_{i j}$ values to the entry in $\boldsymbol{a}^{*} ;$ if a match occurs, the site number is entered; otherwise, the empty vector designation $(\phi)$ is entered.

The target cell (F8) contains the sum of the entries in $\boldsymbol{a}^{*}$. The limitation on the number of new facilities, three for the example, is compared with the entry in B9, which is the sum of the decision variables. The SOLVER parameter box is shown in Figure $10.25 b$.

The two constraints shown in the SOLVER box include a requirement that the decision variables be binary and a requirement that the number of facilities located at sites not exceed the capacity limit (three). As shown in Figure $10.25 c$, the optimum locations for new facilities are sites 2,3, and 4 . (If a capacity limit of one is imposed, then the optimum location is site 4 ; if a capacity limit of two is imposed, then the optimum locations are sites 2 and 4-the same sequence of selections obtained using the Shannon/Ignizio heuristic algorithm.)