Groupe d’études et de recherche en analyse des décisions

G-94-30

The p-Center-Sum Location Problem

, et

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.

, 19 pages

Ce cahier a été révisé en octobre 1995