A Parallel Geographical Network VRP Algorithm Based on PC Clusters

Abstract

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

CLC Number:

P208

References

[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