Programming models for facility dispersion: the p-dispersion and maxisum dispersion problems

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)792
Number of pages1
JournalMathematical and Computer Modelling
Issue number10
StatePublished - 1988
Externally publishedYes

ASJC Scopus subject areas

  • Modeling and Simulation
  • Computer Science Applications


Dive into the research topics of 'Programming models for facility dispersion: the p-dispersion and maxisum dispersion problems'. Together they form a unique fingerprint.

Cite this