A Network Flow Solution to a Rectilinear Distance Facility Location Problem

The problem of locating new facilities is considered with respect to existing facilities so as to minimize a sum of costs which consists of costs proportional to the rectilinear distances between new and existing facilities, and costs proportional to the rectilinear distances among new facilities. The location problem decomposes into two independent sub-problems, each of which is equivalent to a linear programming problem which is essentially the dual of a minimal cost network flow problem. Fulkerson's out-of-kilter algorithm provides an efficient means of solving each of the network flow problems as well as the location problem. The dual variables in each of the optimum tableaus to the two flow problems give the x and y coordinates respectively of the optimum locations of the new facilities. Several alternative approaches to solving the equivalent linear programming problems are also discussed, and some research questions are identified.