The Origins of Discrete Diversity

The p-dispersion facility location problem first emerged in the 1970s as a byproduct of covering and center location problems and the dual relationship between the continuous 1-center solution on a tree network and the two most distant points on the tree. Building on this insight, Shier (Transpor Sci 11(3):243–252, 1977) was the first to recognize the dispersion problem as worthy of study in its own right, with useful real-world applications such as locating oil storage tanks and retail franchises. In the 1980s, two milestones were achieved by researchers who were notably motivated by trying to solve other problems. First, Chandrasekaran and Daughety (Math Oper Res 6(1):50–57, 1981) introduced the “dispersion” nomenclature for the problem of maximizing the diversity of location of points on a tree network, motivated by the need to diversify simulation experiments for fitting a railroad cost surface (Daughety and Turnquist (Oper Res 29(3):485–500, 1981)). Second, Kuby (Geograph Analy 19(4):315–329, 1987) developed the first mixed-integer programming formulation of the discrete dispersion problem in order to generate a regularly spaced solution for his optimization model of central place theory, a geographical theory of retail and services in an urban hierarchy. Finally, Erkut and Neuman (Eur J Oper Res 40(3):275–291, 1989) and Erkut (Eur J Oper Res 46(1):48–60, 1990) popularized dispersion for locating “mutually obnoxious” types of undesirable facilities and developed faster solution methods for the discrete diversity problem.