PC集群环境下的并行地理网络车辆路径算法

编号 zgly0000836972

文献类型 期刊论文

文献题名 PC集群环境下的并行地理网络车辆路径算法

作者 闫志远  孙文彬  陈宗娟  赵帅阳 

作者单位 中国矿业大学(北京)地球科学与测绘工程学院 

母体文献 测绘学报 

年卷期 2014(7)

页码 753-760

年份 2014 

关键词 地理网络分析  车辆路径问题  禁忌搜索  并行算法 

文摘内容 针对PC集群计算节点内存小、进程间通信速度慢的问题,设计了分布式的数据存储机制;提出了用同步变换规则代替解编码传输的进程间通信方式;基于邻域分解策略实现了禁忌搜索过程的并行化,发展了一种适用于PC集群环境的并行地理网络VRP算法。应用模拟路网数据进行了相关试验,结果表明,本文算法的计算结果与ArcGIS基本一致,二者平均偏差率在2.11%~2.87%之间;分布式数据存储策略有效地降低了各进程对内存的需求量,保证了算法的稳健性和扩展性;通过算法的并行化提高了VRP算法的求解效率;该算法具有良好的加速性能,8进程时在各测试数据集中的加速比均在4.46~6.32之间。