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

Neighbor Search Algorithm for Maximal Arc-Covering Problem

作　　者：王蕊[1] 高随祥[1] 石玮亮 戴龙飞 

机构地区：[1]中国科学院大学数学科学学院,北京101408

出　　处：《计算机仿真》2014年第10期445-449,共5页Computer Simulation

基　　金：国家重点基础研究发展计划(973)项目(2011CB706901);国家自然科学基金项目(11331012)

摘　　要：研究应急救援中心的选址问题,通过合理设置各中心的位置,使相应的专业应急小组及时到达事故点进行应急救援,最大限度地减少事故损失。上述问题可描述为网络的最大弧覆盖问题。针对建立最大弧覆盖的数学模型,提出了一种邻域搜索算法:首先将最大弧覆盖问题近似看作p-median问题,利用顶点替代算法给出初始解,再通过邻域搜索,对初始解进行改进。通过实例仿真表明,邻域搜索算法收敛速度快,求解精度接近最优解。The facility location problem of emergency rescue centers was studied in this paper. Quick arrival of specialized response teams can mitigate considerable accident loss when allocation of emergency rescue centers is rea- sonable. The allocation problem can be described as maximal arc - covering problem. This paper presented a neigh- bor search algorithm based on the mathematical model. Firstly, the paper labeled the maximal arc - covering problem as p -median problem approximately. Then, an initial solution was given by vertex substitution algorithm. Finally, the initial solution was improved by neighbor searching. Simulation results demonstrate that neighbor search algorithm has fast convergence speed and high precision.

关 键 词：应急救援 选址 最大弧覆盖 邻域搜索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]