网络选址的方法.docx

对选址问题研究的比较牛X的总结摘自 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,AdiBen-lsrael[44]对大规模P-中心问题给出了启发式算法，对一些著名的问题进行 了计算分析3) 覆盖问题(cover ing problems)覆盖问题分为最大覆盖问题和集覆盖问题两类。

集覆盖问题研究满足覆盖所有需求点顾客的前提下，服务站总的建站个数或建设费用最小的问题集覆盖问题最早是由Roth[45]和Toregas[46]等提出的，用于解决消防中心和救护车等的应急服务设施的选址问题他们分别建立了服务站建站成本不同和相同情况下集覆盖问题的整数规划模型随后Minieka[47]、Moore和ReVelle[48]等都继续研究集覆盖问题Plane和Hendrick[49]、Daskin和Stern[50]建立了服务站个数最小和备用覆盖的顾客最大的双目标集覆盖问题Heung-SukHuan g[51]研究了产品会随时间变坏或变好时的动态集覆盖问题最近十几年来许多基于启发式的算法被用于解决集覆盖问题M.L. Fisher和P.Kedia[52]提出了基于对偶的启发算法并用来解决最多有200个候选点、2000个需求点的集覆盖问题；Beasley J.E.和Jornsten. K[53]将次梯度优化法和拉格朗日松弛算法结合起来求解这类问题；Marcos Alminana和Jesus T. Pastor[54应用代理启发式算法求解集覆盖问题J.E. Beasley和PC Chu[55]给出了求解服务站建站成本不同时集覆盖问题的遗传算法。

Grossman和Wool[56]用大量的实验对比了九种用于求解SCLP的启发式算法，其中随机贪婪算法(R-Gr)、简单贪婪算法(S-Gr )和转换贪婪算法(Alt-Gr)在几乎所有问题中都是最好的前四种算法之一，其中随机贪婪算法表现最好，在60个随机问题中有56次获得最好的解Karp[57]证明了集覆盖问题是NP-完全问题最大覆盖问题或P-覆盖问题是研究在服务站的数目和服务半径已知 的条件下，如何设立P个服务站使得可接受服务的需求量最大的问题同其它 基本问题一样，最大网络覆盖问题也是NP-困难问题(Mark s.Daskin)[58]最初 的最大覆盖问题是由Church RL和ReVelle C[59]提出的，他们将服务站最优 选址点限制在网络节点上；Church RL和Meadows ME[60]在确定的关键候选 节点集合中给出了一般情况下的最优算法，他们通过线性规划的方法求解，如果 最优解不是整数就用分枝定界法求解；Church和Meadows[60]提出了最大覆盖 问题的伪Hakimi特性，即在任何一个网络中，存在一个有限节点的扩展集，在 这个集合中至少包含一个最大覆盖问题的最优解。

Benedict[61]，Hogan和 ReVelle[62], Daskin[63]考虑服务系统拥挤情况下的最大覆盖问题，他们把任意 一个服务站繁忙的概率当作外生变量目标函数是服务站可以覆盖的期望需求量 最大Haldun Aytug和Cem Saydam[64]用遗传算法来求解大规模最大期望覆 盖问题，并进行了比较Fernando Y[65]等对最大期望覆盖问题中排队与非排队 的情况进行了对比Berman[66]研究了最大覆盖问题和部分覆盖问题之间的关 系Oded Berman 和 DmitryKrass[67]、Oded Berman, Dmitry Krass 和 Zvi Drez ner[68 ]讨论比传统最大覆盖问题更一般的最大覆盖问题，并给出了拉格朗 日松弛算法Orhan Karasakal和Esra K.Karasakal[69]讨论了部分覆盖问题， 对覆盖程度进行了定义Jorge H. Jaramillo、Joy Bhadury 和 Rajan Batta[70] 在选址问题的遗传算法应用研究时介绍了最大覆盖问题遗传算法的操作策略2)扩展选址问题在前面三个基本选址问题的基础上考虑其它因素就形成了扩展选址问 题。

由于扩展选址问题是由不同的分类方法根据实际应用需要组合而成，所以各 类型之间存在较大的交叉 本文仅以最具代表特征的部分对不同的类型命名并进 行综述1)带固定费用和/或容量限制的选址问题最容易也最常想到也最有实际意义的就是考虑服务站建站的固定费用 和服务站的容量(服务能力)限制这两个因素，所以早期对基本选址问题的扩展研 究较多地集中在将这两个因素加进基本选址问题上无容量限制固定费用下的选 址问题(UFLP)就是将固定建站费用加到P-中位问题的目标函数上，并且去掉对 服务站建站个数的约束Cornuejols、Fisher和Nemhauser［71］对该问题进行 了细致的分类和具体的分析，Swain［72］运用Bender分解法求解UFLP, Barros 和 Labbe［73］、Holmberg［74］对 UFLP 进行了更深入的研究Geoffrion 和McBride［75］研究用拉格朗日算法解决带容量限制的服务站选址问题Mukundan和Daskin［76］将固定费用有容量限制的选址问题模型(CFLP)用于解决利润最大化的类似问题，Bender分解法也被Mark s. Daskin［58］用来求解CFLP。

最近Hinojosa，Puerto和Fernandez［77］研究了多产品带容量限制的服务站选址问题Melkote和Daskin［78］总结了网络上带容量限制的服务站选址问题的各种模型Roberto Baldacci等［79］提出了一种基于集剖分的方法来求解容量限制的选址问题2)截流问题截流问题研究顾客需求产生在路线上的问题，根据服务站工作性质可 以分为服务型和对抗型两大类服务型截流问题广泛应用于交通规划、交通服 务、交通监测等方面，比如如何在交通路网中设立交通量观测点使监测到的交通 流量最大的问题就是服务型截流问题对抗型截流问题用于解决收费、检查、缉 私等站点的选址问题Hodgson［80］，Berman、Fouska和Larson［81］最早提 出截流问题，研究了需求路线确定的条件下，给定设施的数目，如何在网络中选 址使通过服务站的需求量总和达到最大的截流问题 并建立了此类问题的基本模 型，提出了启发式的贪婪算法来求解截流问题模型Mirchandani、Rebello和 Agn etis［82］通过基本截流问题向集覆盖问题的转换证明了基本的截流问题是 NP-困难问题Hodgson等［83］研究了服务站的顾客流量是由两部分组成的截流 问题，一部分是产生于日常路线上的过路需求，另一部分是产生于节点的固定需 求。

Averbakh、Berman［84］研究了顾客流量细分和接受多次服务的一般模型和 扩展模型Berman和Krass［85］首先给出了竞争环境下的服务站截流选址问 题并给出了启发式算法和最坏情况分析Mirchandank Rebello和Agnetis［86］ 最早提出了对抗型服务站的截流问题Yang.H和Yang.C［87］研究了用户路线不 确定条件下，检查站设在网络的边上的截流问题，建立了线性规划模型，并用列 生成法求得精确解3) Hub选址问题Hub选址问题是和截流问题有些类似的选址问题，需求也是产生在 OD对上，在顾客从0点出发到D的过程中要接受Hub的服务同截流问 题不同的是，0D流并不是走最短路从0点到D点，经过Hub中转服务后 要比直接从0点到D点要快，比如交通系统中的中转站、通信系统的交换机 或服务器等O'Kelly[88,89]创了 Hub选址问题的研究工作，Marianov[90] 研究了竞争环境下的Hub选址问题，Kara和Tansel[91研究了单分配P-Hub 选址问题，Ebery和Krishnamoorthy[92]研究了带容量限制多分配的Hub选 址问题4) 选址一分配问题。