The discrete p-dispersion-sum problem seeks to maximize the minimum of the sums of the shortest path distances between any facility and all of the other p-1 facilities. The authors establish that when p=3 and the underlying graph is a tree, an optimal solution to the discrete p-dispersion-sum problem is a subset of the degree-one vertices. In addition they evaluate the performance of eight heuristic solution procedures for the discrete p-dispersion-sum problem for any p in a general graph setting. A particular implementation of simulated annealing is shown to perform extremely well.
