A Network Flow Solution to a Multifacility Minimax Location Problem Involving Rectilinear Distances

Abstract

The problem considered is to locate new facilities with respect to existing facilities so as to minimize the maximum cost; costs are incurred that are linearly proportional to the rectilinear distances between new and existing facilities, or to the rectinlinear distances between new facilities. Constraints on the distances between facilities are also included in the problem formulation. It is shown that the problem can be decomposed into two subproblems that have identical structure, and that may be solved independently. Each subproblem is solved efficiently by converting it into an equivalent network flow problem that is in turn solved by determining a simple chain of maximum “cost” to “weight” ratio.