最大弧覆盖问题的一种邻域搜索算法.pdf

《最大弧覆盖问题的一种邻域搜索算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第31卷第1O期计算机仿真2014年10月文章编号：1006—9348(2014)10—0445—05最大弧覆盖问题的一种邻域搜索算法王蕊，高随祥，石玮亮，戴龙飞(中国科学院大学数学科学学院，北京101408)摘要：研究应急救援中心的选址问题，通过合理设置各中心的位置，使相应的专业应急小组及时到达事故点进行应急救援，最大限度地减少事故损失。上述问题可描述为网络的最大弧覆盖问题。针对建立最大弧覆盖的数学模型，提出了一种邻域搜索算法：首先将最大弧覆盖问题近似看作P—median问题，利用顶点替代算法给出初始解，再通过邻域搜索，对初始解进行改进。通过实例仿真表明，邻域搜索算法收敛速度快，求解

2、精度接近最优解。关键词：应急救援；选址；最大弧覆盖；邻域搜索中图分类号：TP301．6文献标识码：BNeighborSearchAlgorithmforMaximalArc——CoveringProblemWANGRui，GAOSui—xiang，SHIWei—liang，DAILong—fei(UniversityofChineseAcademyofSciencesSchoolofMathematicalsciences，Beijing101408，China)ABSTRACT：Thefacilitylocationproblemofemergencyrescuecenterswas

3、studiedinthispaper．QuickarrivalofspecializedresponseteamsCallmitigateconsiderableaccidentlosswhenallocationofemergencyrescuecentersisrea-sonable．Theallocationproblemcanbedescribedasmaximalarc—coveringproblem．Thispaperpresentedaneigh—borsearchalgorithmbasedonthemathematicalmode1．Firstly，thepaperl

4、abeledthemaximalarc—coveringproblemasP—medianproblemapproximately．Then，aninitialsolutionwasgivenbyvertexsubstitutionalgorithm．Finally，theinitialsolutionwasimprovedbyneighborsearching．Simulationresultsdemonstratethatneighborsearchalgorithmhasfastconvergencespeedandhighprecision．KEYWORDS：Emergency

5、rescue；Facilitylocation；MaximalarC—covering；Neighborsearch各应急救援中心的位置，使得全网被应急中心覆盖的弧段总1引言长度达到最大(弧段上一点至少被一个应急中心覆盖则认为灾害性事故的发生，会造成人员的重大伤亡。事故发生该点被覆盖)。后，进行有效的应急救援是减少人员损伤的有效途径。通过上述应急中心设置问题可以归结为最大弧覆盖模型。合适的选址模型设立应急救援中心，使相应的专业应急小组网络最大弧覆盖问题是最大点覆盖选址问题的推广。最大在反应时间阈值内及时到达事故点进行应急救援，可以提高点覆盖选址问题由Church等于1974年提出。点覆

6、盖选应急反应能力，并最大限度地减少事故损失。址还包括集合覆盖模型J、P—center模型J、P—median模本文主要考虑在一定区域范围内，应急救援道路网络型[4]、广义最大覆盖模型J。有关点覆盖选址问题的研究上，给定数量的应急救援中心的设置问题。假设事故可能发综述可参考文献[6]。对于最大弧覆盖问题，目前的研究还生在网络中弧上任一点，应急中心可以设置在网络的任何节比较少。ReVelle等在1976年最早提出了最大弧覆盖选址点上。救援车辆从某个应急中心出发，沿道路到达事故点需问题。。。Church等于1979年将最大覆盖理论应用于弧覆盖要花费路途时间，若可在规定的时间阈值内到达事故点，

7、则选址，建立了最大弧覆盖问题的模型J。通过在弧上引入网称该事故点可由该救援中心覆盖。我们的目标是合理设置络交叉点集(NIPS)，他们将模型转化为一个混合整数线性规划模型，该模型类似于最大点覆盖模型。文献[8]中没有给基金项目：国家重点基础研究发展计划(973)项目(2011CB706901)和出具体算法，采用的是IBM数学规划系统求最优解。Berman国家自然科学基金项目(11331012)等于2007年引入弧段覆盖比例，提出了新的弧覆盖模型j