A Least Total Distance Facility Configuration Problem Involving Lattice Points

The problem considered in this paper is to find a layout of a given number of identical facilities so that the total (or average) rectilinear distance between facilities is minimized. The potential locations for the facilities are lattice points in the plane, which are points whose coordinates are integers. A set of geometric properties and necessary conditions for an optimal layout configuration is derived. Based on a symmetry assumption, an implicit enumeration procedure is developed that will yield all optimal configurations together with the least total distance between facilities.