选址问题研究的比较牛X的总结.doc

对选址问题研究的比较牛X的总结 摘自 /wiki/A435695.html 〔转自马云峰〕 ?????? 现代选址研究起于 1909 年，当时 Alfred Weber 为解决如何为单个仓库选址使得仓库到多个顾客间的总距离最小的问题，他在欧氏空间里建立了一个 1-中位问题模型，就是著名的 Weber 问题。 1）基本选址问题 （1）P-中位问题（p-median problems） ?????? P-中位问题是研究如何选择P个服务站使得需求点和服务站之间的距离与需求量的乘积之和最小。Hakimi[13,16]提出该问题之后给出了 P-中位问题的 Hakimi 特性，他证明了 P-中位问题的服务站候选点限制在网络节点上时至少有一个最优解是与不对选址点限制时的最优解是一致的，所以将网络连续选址的 P-中位问题简化到离散选址问题不会影响到目标函数的最优值。Goldman[17]给出了在树和只有一个环的网络上为单个服务站选址中位问题的简单算法。Miehle 于 1958 年也研究过平面 1-中位问题，也就是 Weber 问题，是他发现了 Weiszfeld 的研究成果，被选址-分配问题的里程碑文章 Cooper[14] 誉为 Weiszfeld 研究的发现者。对于空间 P-中位问题，也就是更一般的Weber 问题，Rosing[18]提出了最优解法。Garey 和 Johnson[19]证明了 P-中位问题是 NP-困难问题。Francis[20]、Francis 和 Cabot[21]、Chen[22]以及 Chen 和 Handler[23]研究了基于欧氏距离的 P-中位问题。 　　近年来，P-中位问题仍然是研究的热点，许多学者研究 P-中位问题的各种变形和扩展模型：Wesolowsky[24]、Wesolowsky 和ruscott[25]、Drezner[26]研究了动态 P-中位问题。ReVelle[27]将目标函数定义为新建的服务站所占据的市场份额的最大化，成功地将中位问题运用于竞争环境下的零售商店选址问题中。Lorena、Senne[28]和 Luiz 等[29]运用列生成方法解决带容量限制的 P-中位问题。Berman 等[30]研究服务的可靠度随着服务设施与需求的距离变化的设施问题问题。Church 提出了通过减少分配的变量来减少约束的传统 P-中位问题的新建模方法[31]。Drezner[32]、Chen[33]、Chen 和 Handler[34]在此基础上研究条件中位问题，又称 PQ-中位问题，即网络中已存在 Q 个服务站的条件下，如何为 P 个同类服务站选址的中位问题。 （2）P-中心问题（p-center problems） ??????? P-中心问题也叫 minmax 问题，是探讨如何在网络中选择 P 个服务站，使得任意一需求点到距离该需求点最近的服务站的最大距离最小问题。Hakimi[13]首先提出网络中 P-中心问题，Kariv 和 Hakimi[35]证明了 P-中心问题为 NP-困难问题。Drezner 和Wesolowsky[36]提出了 Drezner-Wesolowsky 法解决多服务站的 P-中心问题。Francis[37]在平面上的 P-中心问题研究中取得一些进展, Wesolowsky[38]研究基于直线距离 P-中心问题；十年后，Chen[22]、Ward 和 Wendell[39]对基于欧几里德距离的 P-中心问题作了研究。Masuyayma，Ibaraki 和 Hasegawa[40]、Megiddo 和 Supowit[41]证明了基于直线距离和欧氏距离的 P-中心问题都是 NP-完全问题。C. Caruso 等[42]通过求解一系列集覆盖的问题的办法求解 P-中心问题。Hassin, Levin, Morad D[43]提出了运用词典区域局部有哪些信誉好的足球投注网站法来求解 P-中心问题。Yuri Levin,Adi Ben-Israel[44]对大规模 P-中心问题给出了启发式算法，对一些著名的问题进行了计算分析。 （3）覆盖问题（covering problems） ??????? 覆盖问题分为最大覆盖问题和集覆盖问题两类。集覆盖问题研究满足覆盖所有需求点顾客的前提下，服务站总的建站个数或建设费用最小的问题。集覆盖问题最早是由 Roth[45]和 Toregas[46]等提出的，用于解决消防中心和救护车等的应急服务设施的选址问题，他们分别建立了服务站建站成本不同和相同情况下集覆盖问题的整数规划模型。随后 Minieka[47]、Moore 和 ReVelle[48]等都继续研究集覆盖问题。Plane 和Hendrick[49]、Daskin 和 Stern[50]建立了服务站个数最小和备用