The Solution of Distance Constrained Mini-Sum Location Problems

The problem considered in this paper requires determining the location of a given number of centers or facilities to minimize the sum of weighted distances to customers being served, subject to the constraint that no customer receives inadequate service. The method proposed is a partial enumerative procedure that employs both a graph-coloring algorithm (to generate feasible partitions) and an iterative location procedure with feasibility tests (to determine optimal locations). The procedure ensures the global optimum to this otherwise non-convex location-allocation problem. The procedure has been programmed and computational results are presented.