A new location-allocation problem, called p-Center-Sum, is considered: given n clients (or demand points) locate p facilities among a given set of sites and allocate clients to these facilities in order to minimize the sum over all facilities of the maximum distance between their location and that of any of their clients. This problem is shown to be NP-hard, even if the locations of the facilities are fixed. An algorithm combining generalized linear programming with integer programming is proposed to solve it. Computational results for problems with up to 50 locations and 20 facilities are reported.
Published July 1994 , 19 pages
This cahier was revised in October 1995