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

摘要

研究应急救援中心的选址问题,通过合理设置各中心的位置,使相应的专业应急小组及时到达事故点进行应急救援,最大限度地减少事故损失.上述问题可描述为网络的最大弧覆盖问题.针对建立最大弧覆盖的数学模型,提出了一种邻域搜索算法:首先将最大弧覆盖问题近似看作p-median问题,利用顶点替代算法给出初始解,再通过邻域搜索,对初始解进行改进.通过实例仿真表明,邻域搜索算法收敛速度快,求解精度接近最优解.