Question 10.19: Solving a 1-center problem

Recall the example considered for the 1-median problem, in which a parts replenishment station is to be located on a manufacturing floor. Since only vertices with positive-valued weights are considered in the 1-center problem, the tree network is revised as shown in Figure 10.28 a. Notice, three vertices were removed from the tree, and the remaining eight vertices were renumbered. Hence, m=8.

Table 10.10 contains the b_{i j} values for 1=i<j=m . The maximum value \left(b_{s t}\right) equals 99.167 and corresponds to vertices 2 and 8 . Therefore, x^{*} is located on the path connecting v_{2} and v_{8}. Since d\left(v_{2}, v_{8}\right)=34, w_{2}=5, and w_{8}=7, the distance from v_{2} to x^{*} along the path to v_{8} equals (7 / 12)(8+6+8+6+6), or 19.833 . Another way to determine the distance is 99.167 / 5, or 19.833 . The optimum location on the tree is given in Figure 10.28 b. (Note: b_{s t}=f\left(x^{*}\right)=99.167 . )

For large-sized problems, the computations involved in solving the 1-center problem are formidable. The number of calculations required to determine the value of b_{s t}=m(m-1) / 2 . For the example, 28 calculations were required. If m=50, then 1,225 computations are required. As noted, it is generally more difficult to solve location problems on trees than in the plane, and it is far more difficult to solve them on cyclical networks.