A new method for solving capacitated location problems based on a set partitioning approach

We consider the capacitated p-median problem (CPMP) in which a set of n cus tomers must be partitioned into p disjoint clusters so that the total dissi milarity within each cluster is minimized and constraints on maximum cluste r capacities are met. The dissimilarity of a cluster is computed as the sum of the dissimilarities existing between each entity of the cluster and the median associated to such cluster. In this paper we present an exact algor ithm for solving the CPMP based on a set partitioning formulation of the pr oblem. A valid lower bound to the optimal solution cost is obtained by comb ining two different heuristic methods for solving the dual of the LP-relaxa tion of the exact formulation. Computational tests on problems proposed in the literature and on new sets of test problems show the effectiveness of t he proposed algorithm.