An Experimental Comparison of Techniques for the Assignment of Facilities to Locations

Abstract

The optimal assignment of facilities to locations is a combinatorial problem that remains unsolved. None of the several optimal-producing procedures is computationally feasible for any but small problems. Three previously proposed heuristic techniques (craft, one by Hillier, one by Hillier and Connors) and one new one (Biased Sampling) are examined and experimentally compared for problems of from five departments to 30 departments. The new Biased Sampling procedure is seen to produce the best solutions but at relatively high computational cost. The Hillier-Connors procedure is especially interesting because it is considerably faster than craft and Biased Sampling and its solutions are only 2–6 per cent worse than Biased Sampling and only slightly worse than craft.