Programming Models for Facility Dispersion: The p‐Dispersion and Maxisum Dispersion Problems

The p ‐dispersion problem is to locate p facilities on a network so that the minimum separation distance between any pair of open facilities is maximized. This problem is applicable to facilities that pose a threat to each other and to systems of retail or service franchises. In both of these applications, facilities should be as far away from the closest other facility as possible. A mixed‐integer program is formulated that relies on reversing the value of the 0–1 location variables in the distance constraints so that only the distance between pairs of open facilities constrain the maximization. A related problem, the maxisum dispersion problem, which aims to maximize the average separation distance between open facilities, is also formulated and solved. Computational results for both models for locating 5 and 10 facilities on a network of 25 nodes are presented, along with a multicriteria approach combining the dispersion and maxisum problems. The p ‐dispersion problem has a weak duality relationship with the ( p ‐1)‐center problem in that one‐half the maximin distance in the p ‐dispersion problem is a lower bound for the minimax distance in the center problem for ( p ‐1) facilities. Since the p ‐center problem is often solved via a series of set‐covering problems, the p ‐dispersion problem may prove useful for finding a starting distance for the series of covering problems.