《选址问题研究的比较牛X的总结》由会员分享，可在线阅读，更多相关《选址问题研究的比较牛X的总结（7页珍藏版）》请在金锄头文库上搜索。
1、对选址问题研究的比较牛X的总结转自马云峰 现代选址研究起于 1909 年，当时 Alfred Weber 为解决如何为单个仓库选址使得仓库到多个顾客间的总距离最小的问题，他在欧氏空间里建立了一个 1-中位问题模型，就是著名的 Weber 问题。1）基本选址问题（1）P-中位问题（p-median problems） P-中位问题是研究如何选择P个服务站使得需求点和服务站之间的距离与需求量的乘积之和最小。Hakimi13,16提出该问题之后给出了 P-中位问题的 Hakimi 特性，他证明了 P-中位问题的服务站候选点限制在网络节点上时至少有一个最优解是与不对选址点限制时的最优解是一致的，所以将
2、网络连续选址的 P-中位问题简化到离散选址问题不会影响到目标函数的最优值。Goldman17给出了在树和只有一个环的网络上为单个服务站选址中位问题的简单算法。Miehle 于 1958 年也研究过平面 1-中位问题，也就是 Weber 问题，是他发现了 Weiszfeld 的研究成果，被选址-分配问题的里程碑文章 Cooper14 誉为 Weiszfeld 研究的发现者。对于空间 P-中位问题，也就是更一般的Weber 问题，Rosing18提出了最优解法。Garey 和 Johnson19证明了 P-中位问题是 NP-困难问题。Francis20、Francis 和 Cabot21、Chen
3、22以及 Chen 和 Handler23研究了基于欧氏距离的 P-中位问题。近年来，P-中位问题仍然是研究的热点，许多学者研究 P-中位问题的各种变形和扩展模型：Wesolowsky24、Wesolowsky 和ruscott25、Drezner26研究了动态 P-中位问题。ReVelle27将目标函数定义为新建的服务站所占据的市场份额的最大化，成功地将中位问题运用于竞争环境下的零售商店选址问题中。Lorena、Senne28和 Luiz 等29运用列生成方法解决带容量限制的 P-中位问题。Berman 等30研究服务的可靠度随着服务设施与需求的距离变化的设施问题问题。Church 提出了通
4、过减少分配的变量来减少约束的传统 P-中位问题的新建模方法31。Drezner32、Chen33、Chen 和 Handler34在此基础上研究条件中位问题，又称 PQ-中位问题，即网络中已存在 Q 个服务站的条件下，如何为 P 个同类服务站选址的中位问题。（2）P-中心问题（p-center problems） P-中心问题也叫 minmax 问题，是探讨如何在网络中选择 P 个服务站，使得任意一需求点到距离该需求点最近的服务站的最大距离最小问题。Hakimi13首先提出网络中 P-中心问题，Kariv 和 Hakimi35证明了 P-中心问题为 NP-困难问题。Drezner 和Wesol
5、owsky36提出了 Drezner-Wesolowsky 法解决多服务站的 P-中心问题。Francis37在平面上的 P-中心问题研究中取得一些进展, Wesolowsky38研究基于直线距离 P-中心问题；十年后，Chen22、Ward 和 Wendell39对基于欧几里德距离的 P-中心问题作了研究。Masuyayma，Ibaraki 和 Hasegawa40、Megiddo 和 Supowit41证明了基于直线距离和欧氏距离的 P-中心问题都是 NP-完全问题。C. Caruso 等42通过求解一系列集覆盖的问题的办法求解 P-中心问题。Hassin, Levin, Morad D4
6、3提出了运用词典区域局部搜索法来求解 P-中心问题。Yuri Levin,Adi Ben-Israel44对大规模 P-中心问题给出了启发式算法，对一些著名的问题进行了计算分析。（3）覆盖问题（covering problems） 覆盖问题分为最大覆盖问题和集覆盖问题两类。集覆盖问题研究满足覆盖所有需求点顾客的前提下，服务站总的建站个数或建设费用最小的问题。集覆盖问题最早是由 Roth45和 Toregas46等提出的，用于解决消防中心和救护车等的应急服务设施的选址问题，他们分别建立了服务站建站成本不同和相同情况下集覆盖问题的整数规划模型。随后 Minieka47、Moore 和 ReVell
7、e48等都继续研究集覆盖问题。Plane 和Hendrick49、Daskin 和 Stern50建立了服务站个数最小和备用覆盖的顾客最大的双目标集覆盖问题。Heung-Suk Huang51研究了产品会随时间变坏或变好时的动态集覆盖问题。最近十几年来许多基于启发式的算法被用于解决集覆盖问题，M.L. Fisher 和 P.Kedia52提出了基于对偶的启发算法并用来解决最多有 200 个候选点、2000 个需求点的集覆盖问题；Beasley J.E. 和 Jornsten. K53将次梯度优化法和拉格朗日松弛算法结合起来求解这类问题；Marcos Alminana 和 Jesus T. Pa
8、stor54应用代理启发式算法求解集覆盖问题。J.E. Beasley 和 P.C. Chu55给出了求解服务站建站成本不同时集覆盖问题的遗传算法。Grossman 和 Wool56用大量的实验对比了九种用于求解 SCLP 的启发式算法，其中随机贪婪算法(R-Gr)、简单贪婪算法(S-Gr)和转换贪婪算法(Alt-Gr)在几乎所有问题中都是最好的前四种算法之一，其中随机贪婪算法表现最好，在 60 个随机问题中有 56 次获得最好的解。Karp57证明了集覆盖问题是 NP-完全问题。 最大覆盖问题或 P-覆盖问题是研究在服务站的数目和服务半径已知的条件下，如何设立 P 个服务站使得可接受服务的需
9、求量最大的问题。同其它基本问题一样，最大网络覆盖问题也是 NP-困难问题(Mark s.Daskin)58。最初的最大覆盖问题是由 Church RL 和 ReVelle C59提出的，他们将服务站最优选址点限制在网络节点上；Church RL和 Meadows ME60在确定的关键候选节点集合中给出了一般情况下的最优算法，他们通过线性规划的方法求解，如果最优解不是整数就用分枝定界法求解；Church 和Meadows60提出了最大覆盖问题的伪 Hakimi 特性，即在任何一个网络中，存在一个有限节点的扩展集，在这个集合中至少包含一个最大覆盖问题的最优解。Benedict61，Hogan 和
10、ReVelle62，Daskin63考虑服务系统拥挤情况下的最大覆盖问题，他们把任意一个服务站繁忙的概率当作外生变量，目标函数是服务站可以覆盖的期望需求量最大。Haldun Aytug 和 Cem Saydam64用遗传算法来求解大规模最大期望覆盖问题，并进行了比较。Fernando Y65等对最大期望覆盖问题中排队与非排队的情况进行了对比。Berman66研究了最大覆盖问题和部分覆盖问题之间的关系。Oded Berman 和 DmitryKrass67 、Oded Berman, Dmitry Krass 和 Zvi Drezner68讨论比传统最大覆盖问题更一般的最大覆盖问题，并给出了拉格
11、朗日松弛算法。Orhan Karasakal 和 Esra K.Karasakal69讨论了部分覆盖问题，对覆盖程度进行了定义。Jorge H. Jaramillo、Joy Bhadury 和 Rajan Batta70 在选址问题的遗传算法应用研究时介绍了最大覆盖问题遗传算法的操作策略。2）扩展选址问题 在前面三个基本选址问题的基础上考虑其它因素就形成了扩展选址问题。由于扩展选址问题是由不同的分类方法根据实际应用需要组合而成，所以各类型之间存在较大的交叉，本文仅以最具代表特征的部分对不同的类型命名并进行综述。（1）带固定费用和/或容量限制的选址问题 最容易也最常想到也最有实际意义的就是考虑服
12、务站建站的固定费用和服务站的容量(服务能力)限制这两个因素，所以早期对基本选址问题的扩展研究较多地集中在将这两个因素加进基本选址问题上。无容量限制固定费用下的选址问题(UFLP)就是将固定建站费用加到 P-中位问题的目标函数上，并且去掉对服务站建站个数的约束。Cornuejols、Fisher 和 Nemhauser71对该问题进行了细致的分类和具体的分析，Swain72运用 Bender 分解法求解 UFLP，Barros 和 Labbe73、Holmberg74对 UFLP 进行了更深入的研究。Geoffrion 和 McBride75研究用拉格朗日算法解决带容量限制的服务站选址问题。Mu
13、kundan 和 Daskin76将固定费用有容量限制的选址问题模型(CFLP)用于解决利润最大化的类似问题，Bender 分解法也被 Mark s. Daskin58用来求解 CFLP。最近Hinojosa，Puerto 和 Fernandez77研究了多产品带容量限制的服务站选址问题，Melkote和 Daskin78总结了网络上带容量限制的服务站选址问题的各种模型。Roberto Baldacci等79提出了一种基于集剖分的方法来求解容量限制的选址问题。（2）截流问题 截流问题研究顾客需求产生在路线上的问题，根据服务站工作性质可以分为服务型和对抗型两大类。服务型截流问题广泛应用于交通规划
14、、交通服务、交通监测等方面，比如如何在交通路网中设立交通量观测点使监测到的交通流量最大的问题就是服务型截流问题。对抗型截流问题用于解决收费、检查、缉私等站点的选址问题。Hodgson80，Berman、Fouska 和 Larson81最早提出截流问题，研究了需求路线确定的条件下，给定设施的数目，如何在网络中选址使通过服务站的需求量总和达到最大的截流问题，并建立了此类问题的基本模型，提出了启发式的贪婪算法来求解截流问题模型。Mirchandani 、Rebello 和 Agnetis82通过基本截流问题向集覆盖问题的转换证明了基本的截流问题是 NP-困难问题。Hodgson 等83研究了服务站
15、的顾客流量是由两部分组成的截流问题，一部分是产生于日常路线上的过路需求，另一部分是产生于节点的固定需求。Averbakh、Berman84研究了顾客流量细分和接受多次服务的一般模型和扩展模型。Berman 和 Krass85首先给出了竞争环境下的服务站截流选址问题，并给出了启发式算法和最坏情况分析。Mirchandani、Rebello 和 Agnetis86最早提出了对抗型服务站的截流问题。Yang.H和 Yang.C87研究了用户路线不确定条件下，检查站设在网络的边上的截流问题，建立了线性规划模型，并用列生成法求得精确解。（3）Hub 选址问题 Hub 选址问题是和截流问题有些类似的选址问题，需求也是产生在 OD 对上，在顾客从 O 点出发到 D 的过程中要接受 Hub 的服务。同截流问题不同的是，OD 流并不是走最短路从 O 点到 D 点，经过 Hub 中转服务后要比直接从 O 点到 D 点要快，比如交通系统中的中转站、通信系统的交换机或服务器等。OKelly88,89开创了 Hub 选址问题的研究工作，Marianov90研究了竞争环境下的 Hub 选址问题，Kara 和 Tansel91研究了单分配 P-Hub 选址问题，Ebery 和 Kri
