An Efficient Computational Procedure for the Rectilinear MAXIMIN Location Problem

This paper deals with the problem of locating a facility among n existing facilities so that the shortest weighted distance with respect to all existing facilities is as large as possible. The new facility is to be placed within a bounded convex region S in R² where the existing facilities also lie. The rectilinear distance is used for a distance metric. Applications of the model include the location of an undesirable or obnoxious facility in a bounded region in which the underlying distance metric is rectilinear. Based upon the linearization of the solution space an efficient algorithm is developed that finds the MAXIMIN point by solving a sequence of LPs using Simplex. Computational results are provided. The algorithm is shown to be computationally more efficient than an existing combinatorial algorithm. The use of the algorithm is illustrated in a numerical example.