P-中位问题
P-中位问题
P-中位问题简介
定义
P-中位问题（p-median problems，也叫P-中值问题）是研究如何选择P个服务站使得需求点和服务站之间的距离与需求量的乘积之和最小。
起源
Hakimi提出该问题之后给出了 P-中位问题的 Hakimi 特性，他证明了 P-中位问题的服务站候选点限制在网络节点上时至少有一个最优解是与不对选址点限制时的最优解是一致的，所以将网络连续选址的 P-中位问题简化到离散选址问题不会影响到目标函数的最优值。Goldman给出了在树和只有一个环的网络上为单个服务站选址中位问题的简单算法。Miehle 于 1958 年也研究过平面1-中位问题，也就是Weber 问题，是他发现了 Weiszfeld 的研究成果，被选址-分配问题的里程碑文章 Cooper誉为 Weiszfeld 研究的发现者。对于空间 P-中位问题，也就是更一般的Weber 问题，Rosing提出了最优解法。Garey 和 Johnson证明了 P-中位问题是 NP-困难问题。Francis、Francis 和 Cabot、Chen以及 Chen 和 Handler研究了基于欧氏距离的 P-中位问题。
研究现状
近年来，P-中位问题仍然是研究的热点，许多学者研究 P-中位问题的各种变形和扩展模型：Wesolowsky 和ruscott、Drezner研究了动态 P-中位问题。ReVelle将目标函数定义为新建的服务站所占据的市场份额的最大化，成功地将中位问题运用于竞争环境下的零售商店选址问题中。Lorena、Senne和 Luiz 等运用列生成方法解决带容量限制的 P-中位问题。Berman 等研究服务的可靠度随着服务设施与需求的距离变化的设施问题问题。Church 提出了通过减少分配的变量来减少约束的传统 P-中位问题的新建模方法。Drezner、Chen、Handler在此基础上研究条件中位问题，又称 PQ-中位问题，即网络中已存在 Q 个服务站的条件下，如何为 P 个同类服务站选址的中位问题。