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

测绘学报 ›› 2014, Vol. 43 ›› Issue (7): 753-760.

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

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

中国矿业大学（北京）

收稿日期:2013-12-18 修回日期:2014-01-16 出版日期:2014-07-20 发布日期:2014-07-29
通讯作者: 闫志远 E-mail:yan_zhi_yuan@163.com
基金资助:
国家自然科学基金项目;国家自然科学基金;中国矿业大学（北京）大学生创新计划

A Parallel Geographical Network VRP Algorithm Based on PC Clusters

Received:2013-12-18 Revised:2014-01-16 Online:2014-07-20 Published:2014-07-29

摘要/Abstract

摘要：

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

关键词: 地理信息系统, 地理网络分析, 车辆路径问题, 禁忌搜索, 并行算法

Abstract:

In PC clusters, the memory in each compute node is limited and the communication is inefficient. To solve these problems, a novel parallel algorithm for geographical network VRP is proposed. The main contents are as follows. Firstly, a distributed storage mechanism is designed to avoid the low memory problem. Then, instead of sending the complete solution, synchronizing the transformation of the solution is used to reduce the quantity of communication and improve the efficiency. Finally, a parallel geographical network VRP algorithm is implemented by parallelizing the OD matrix computing and the tabu search procedure. Several experiments are conducted on a PC cluster using simulated traffic networks. The results show that: the computational results of the proposed algorithm are consistent with ArcGIS, and the average deviation is between 2.11% - 2.87%; the distributed storage mechanism reduces the memory usage in each process and enhances the robustness and scalability of the algorithm; the parallelizing of the algorithm improves the efficiency of solving VRP; the proposed algorithm has good parallel performance, and the speedup is between 4.46 - 6.32 in all test datasets using 8 processes.

Key words: Geographical Information System (GIS), geographical network analysis, Vehicle Routing Problem, tabu search, parallel algorithms

中图分类号:

P208

闫志远孙文彬陈宗娟赵帅阳. PC集群环境下的并行地理网络车辆路径算法[J]. 测绘学报, 2014, 43(7): 753-760.

参考文献

[1] LIU Xia.Research on Vehicle Routing Problem [D]. Wuhan：Huazhong University of Science and Technology，2007.（刘霞.车辆路径问题的研究[D]. 武汉：华中科技大学，2007.） [2] LI Jun，GUO Yaohuang.Theories and Methods of Vehicle Scheduling Optimization [M]. Beijing：Chinese Materials Press，2001.（李军，郭耀煌. 车辆优化调度理论与方法[M]. 北京：中国物资出版社，2001.） [3]XIAO Han，ZHANG Zuxun.Parallel Image Matching Algorithm Based on GPGPU[J].Acta Geodaetica et Cartographica Sinica, 2010, 39(1):46-51 [4]ZHAO Yuan，ZHANG Xinchang，KANG Tingjun.A Parallel Ant Colony Optimization Algorithm for Site Location[J].Acta Geodaetica et Cartographica Sinica, 2010, 39(3):322-327 [5]ZOU Xiancai，LI Jiancheng，WANG Haihong，et al.Application of Parallel Computing with OpenMP in Data Processing for Satellite Gravity[J].Acta Geodaetica et Cartographica Sinica, 2010, 39(6):636-641 [6]SHEN Jie, GUO Lishuai, ZHU Wei, et al.Parallel Computing Suitability of Contour Simplification Based on MPI[J].Acta Geodaetica et Cartographica Sinica, 2013, 42(4):621-628 [7] MAISCHBERGER M，CORDEAU J.Solving Variants of the Vehicle Routing Problem with a Simple Parallel Iterated Tabu Search，in Network Optimization [M]. Berlin：Springer Berlin Heidelberg，2011：395-400. [8]CORDEAU J，MAISCHBERGER M.A Parallel Iterated Tabu Search Heuristic for Vehicle Routing Problems[J].Computers & Operations Research, 2012, 39(9):2033-2050 [9]GRO?RC，GOLDEN B，WASIL E.A Parallel Algorithm for the Vehicle Routing Problem[J].INFORMS Journal on Computing, 2011, 23(2):315-330 [10]JIN Jianyong，CRAINIC T G，LOKKETANGEN A.A Parallel Multi-Neighborhood Cooperative Tabu Search for Capacitated Vehicle Routing Problems[J].European Journal of Operational Research, 2012, 222(3):441-451 [11]RIBEIRO G M，LAPORTE G.An Adaptive Large Neighborhood Search Heuristic for the Cumulative Capacitated Vehicle Routing Problem[J].Computers & Operations Research, 2012, 39(3):728-735 [12]ZHU Haodong，LI Hongchan.Parallel Tabu Search Algorithm based on Double Tabu Objects[J].Computer Engineering andApplications, 2011, 47(29):31-33 [13]SHI Yarong，WAN Difang，LI Shuangyan，et al.Research of Vehicle Routing Problem based on GIS[J].System Engineering-Theory & Practice, 2009, 29(10):76-84 [14]KEENAN P.Modeling Vehicle Routing in GIS[J].Operational Research, 2008, 8(3):201-218 [15]BOYER V，ELKIHEL M，BAZ D E.Heuristics for the 0-1 Multidimensional Knapsack Problem[J].European Journal of Operational Research, 2009, 199(3):658-664 [16] GENDREAU M，POTVIN J-Y.Tabu Search，in Handbook of Metaheuristics [M]. Norwell：Kluwer Academic Publishers，2010：41-60. [17]ZACHARIADIS E E，TARANTILIS C D，KIRANOUDIS C T.A Guided Tabu Search for the Vehicle Routing Problem with Two-Dimensional Loading Constraints[J].European Journal of Operational Research, 2009, 195(3):729-743 [18]李志萍，高兴国.模拟退火法与禁忌搜索法求解VRP的对比分析[J].科技信息, 2010, 1(22):79-80 [19]BOLDUC M-C，LAPORTE G，RENAUD J，et al.A Tabu Search Heuristic for the Split Delivery Vehicle Routing Problem with Production and Demand Calendars[J].European Journal of Operational Research, 2010, 202(1):122-130 [20] NGUEVEU S U，PRINS C，CALVO R W.A Hybrid Tabu Search for the m-Peripatetic Vehicle Routing Problem，in Matheuristics [M]. New York：Springer，2010：253-266. [21]BRAND?O J.A Tabu Search Algorithm for the Heterogeneous Fixed Fleet Vehicle Routing Problem[J].Computers & Operations Research, 2011, 38(1):140-151 [22]CESCHIA S，GASPERO L D，SCHAERF A.TabuSearch Techniques for the Heterogeneous Vehicle Routing Problem with Time Windows and Carrier-Dependent Costs[J].Journal of Scheduling, 2011, 14(6):601-615 [23]MOCCIA L，CORDEAU J-F，LAPORTE G.An Incremental Tabu Search Heuristic for the Generalized Vehicle Routing Problem with Time Windows[J].Journal of the Operational Research Society, 2011, 63(2):232-244