Obnoxious facility location in multiple dimensional space

Abstract

The obnoxious facility location problem in three dimensions is optimally solved by an exact method based on Apollonius spheres, and in three or more dimensions by a modification of the Big-Cube-Small-Cube (BCSC, Schobel and Scholz in Comput Oper Res 37:115–122, 2010) global optimization method to within a pre-specified accuracy. In our implementation, no specifically designed bounds are required. The general purpose bounds proposed in this paper do not employ derivatives of the functions. Such an approach can be used, for example, for locating multiple obnoxious facilities in two dimensional space, locating obnoxious facilities on the plane with demand points in three-dimensional space, or applying different distance norms. We concentrated mainly on three-dimensional problems which have the most practical applications. A four dimensional practical application is presented. We solved problems in a cube, part of a cube, a non-convex building, and locating a facility on the plane when demand points are in a three-dimensional space. We also solved problems in 4–6 dimensions to illustrate the effectiveness of the BCSC method.

Appendices

Appendix A: Intersection points of 3 spheres

For notation purposes all upper case variables are vectors of 3 components: a vector $X=(x_1,x_2,x_3)$. Greek letters or lower case letters are single numbers. The scalar product $\cdot$ is: $A\cdot B=a_1b_1+a_2b_2+a_3b_3$. The cross operator $\times$ of two vectors A and B is: $A\times B=(a_2b_3-a_3b_2,-a_1b_3+a_3b_1,a_1b_2-a_2b_1)$. The norm of a vector is $||X||=\sqrt{x_1^2+x_2^2+x_3^2}$.

The centers of the three spheres are $X_1, X_2, X_3$ with radii $r_1,r_2,r_3$. The intersection points are calculated by the following sequence:

• 1. $U=\frac{X_2-X_1}{||X_2-X_1||}$;  $\alpha =U\cdot (X_3-X_1)$

• 2. $V=\frac{X_3-X_1-\alpha U}{||X_3-X_1-\alpha U||}$;  $\beta =V\cdot (X_3-X_1)$

• 3. $\gamma =\frac{r_1^2-r_2^2+||X_2-X_1||^2}{2||X_2-X_1||}$;  $\delta =\frac{r_1^2-r_3^2-2\alpha \gamma +\alpha ^2+\beta ^2}{2\beta }$

• 4. $\Delta =r_1^2-\gamma ^2-\delta ^2$

• 5. If $\Delta <0$ there are no intersection points.

• 6. Otherwise, the two intersection points are: $X=X_1+\gamma U+\delta V\pm \sqrt{\Delta }(U\times V)$.

Appendix B: The Fortran program

Fig. 5

A FORTRAN code that finds all the intersection points of 3 spheres

The part of the FORTRAN program that finds all feasible intersections of 3 spheres is depicted in Fig. 5. An additional part of the program (not shown) evaluates intersections between spheres and the boundary of the cube. The three centers are $x_i, y_i, z_i$ for $i=1,2,3$. The demand points are in the vectors $x(\cdot ), y(\cdot ), z(\cdot )$ with weights $w(\cdot )$ and weight squared in $w2(\cdot )$. The function “fall” calculates the squared value of the objective function and stops the evaluation if the value drops below the best known solution:

Appendix C: Finding the $3^{\delta} -2^{\delta}$ sequences

See Fig. 6.

Fig. 6

A FORTRAN code to find the $3^{\delta} -2^{\delta}$ sequences of length $\delta$, and the $\delta =3$ sequences