A Rectilinear Distance Round-Trip Location Problem

The problem considered is that of finding the location of a facility in the plane so that the maximum weighted rectilinear round-trip distance between the facility and N pairs of existing facilities is minimized. The round-trip distance is the total distance traveled starting from the new facility via a pair of existing facilities and back to the new facility. An efficient one-pass solution procedure is developed for finding all the optimal locations to the problem, and is compared computationally with the simplex method. Two special cases are investigated, namely, when the existing facilities lie on a line, and when all the weights are equal.