Programming Models for Facility Dispersion: The p‐Dispersion and Maxisum Dispersion Problems
Programming Models for Facility Dispersion: The p‐Dispersion and Maxisum Dispersion Problems
复制标题
DOI：
10.1111/j.1538-4632.1987.tb00133.x
复制
发表时间：
2010-09
影响因子：
3.6
通讯作者：
M. Kuby
中科院分区：
文献类型：
--
作者：
M. Kuby
P-离散问题是指在一个网络上寻找p个设施，使得任意一对开放设施之间的最小间隔距离最大化。这个问题适用于对彼此构成威胁的设施以及零售或服务特许经营系统。在这两种应用中，设施应尽可能远离距离最近的其他设施。建立了一个混合整数规划，它依赖于倒置距离约束中的0-1个位置变量的值，使得只有开放设施对之间的距离才能约束最大化。提出并求解了一个相关问题，即以最大化开放设施间平均间隔距离为目标的最大离散度问题。文中给出了在25个节点的网络上选址5个和10个设施的两种模型的计算结果，以及结合离散和最大值问题的多准则方法。P-色散问题与(p-1)-中心问题具有弱对偶关系，因为p-色散问题中极大极大距离的一半是(p-1)设施的中心问题中极小极大距离的下界。由于p-中心问题通常通过一系列集合覆盖问题来解决，因此p-离散度问题可能被证明是有用的，以求出一系列覆盖问题的起始距离。
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.