Journal of Geo-information Science >
A Fast Algorithm for Large Scale Vehicle Routing Optimization Based on Voronoi Neighbors
Received date: 2012-11-02
Revised date: 2012-12-01
Online published: 2012-12-25
Logistic requires designing delivery plan intelligently and quickly. Traditional vehicle routing optimal algorithms can only solve vehicle routing problem no more than 2000 customers, and cost much computing efforts. This paper proposes a fast heuristic algorithm for large scale logistic vehicle routing optimization based on Voronoi neighbors. This algorithm creates an initial solution and improves it iteratively. The creation makes use of the Voronoi neighbors to cluster customers into groups from bottom to up, considering the vehicle capacity constraint. The route in each group is generated by the cheapest insertion algorithm. The improvement employs local search in k-order Voronoi neighbors to search the promising neighbor solution. The simulated annealing criterion is adopted to accept some bad solutions, escaping from local minima. The computational test has been done with a synthetic large scale vehicle routing problem dataset in Beijing. The result indicates the proposed algorithm could solve vehicle routing problem up to 12 000 customers in 4500 seconds. It costs few computational efforts, and has a quite stable performance. Comparison to other heuristics shows the proposed algorithm could provide high quality solution in a short time. The conclusion indicates the proposed algorithm is suitable for large scale logistic vehicle routing optimization.
Key words： spatial cluster; simulated annealing; logistic; Voronoi; vehicle routing problem
CHU Wei, FANG Zhi-Xiang, LI Qing-Quan, LU Shi-Wei . A Fast Algorithm for Large Scale Vehicle Routing Optimization Based on Voronoi Neighbors[J]. Journal of Geo-information Science, 2012 , 14(6) : 781 -787 . DOI: 10.3724/SP.J.1047.2012.00781
[1] 高自友,孙会君. 现代物流与交通运输系统[M]. 北京:人民交通出版社, 2003.
[2] Santos L, Coutinho-Rodrigues J, Antunes C H. A web spatial decision support system for vehicle routing using Google Maps[J]. Decision Support Systems, 2011. 51(1): 1-9.
[3] 肖桂荣,聂乔,吴升. 面向物流的空间信息Web服务集成研究[J]. 地球信息科学学报, 2011, 13(2): 630-636.
[4] 戚铭尧. 面向物流的空间信息服务及其关键技术研究 [D]. 北京:中国科学院遥感应用研究所,2006.
[5] Laporte G. Fifty years of vehicle routing[J]. Transportation Science, 2009, 43(4): 408-416.
[6] 李清泉,张金亭,黄经南. 一个物流配送优化算法[J]. 武汉大学学报·信息科学版, 2003, 28(1): 9-13.
[7] Kytöjoki J, Nuortio T, Bräysy O, et al. An efficient variable neighborhood search heuristic for very large scale vehicle routing problems [J]. Computers & Operations Research, 2007, 34(9): 2743-2757.
[8] Okabe A, Boots B, Sugihara K, et al. Spatial tessellations: Concepts and applications of Voronoi Diagrams[M]. Wiley. 2000.
[9] Chen J, Li C, Li Z, et al. A Voronoi-based 9-intersection model for spatial relations [J]. International Journal of Geographical Information Science, 2001, 15(3): 201-220.
[10] Fang Z X, Tu W, Li Q Q, et al. A Voronoi neighborhood-based search heuristic for distance/capacity constrained very large vehicle routing problems [J]. International Journal of Geographical Information Science, 2012, DOI: 10.1080/13658816.2012.707319.
[11] 梅新,崔伟宏,高飞,等. 基于空间聚类的物流配送决策研究[J]. 武汉大学学报·信息科学版, 2008, 33(4): 371-375.
[12] Barreto S, Ferreira C, Paix o J, Santos B S. Using clustering analysis in a capacitated location-routing problem [J]. European Journal of Operational Research, 2007, 179(3): 968-977.
[13] Han J W, Kamber M and Pei J. Data mining: Concepts and techniques [M]. The Morgan Kaufmann Series in Data Management Systems, Morgan Kaufmann Publishers, 2011(3rd edition).
[14] Toth P and Daniele V. The vehicle routing problem[M]. Society for Industrial and Applied Mathematics, 2002.
[15] Kirkpatrick S, Gelatt Jr, C D, Vecchi M P. Optimization by simulated annealing [J]. Science,1983, 220(4598): 671-680.
[16] 张波,叶家玮,胡郁葱.模拟退火算法在路径优化问题中的应用[J]. 中国公路学报, 2004. 17(1): 83-85.
[17] Zachariadis E E and Kiranoudis C T. A strategy for reducing the computational complexity of local search-based methods for the vehicle routing problem [J]. Computers & Operations Research,2010,37(12): 2089-2105.
[18] TransCAD. http://www.caliper.com/tcovu.htm
[19] Groër C, Golden B, Wasil E. A library of local search heuristics for the vehicle routing problem [J]. Mathematical Programming Computation, 2010,2(2): 79-101.
[20] Li F, Golden B, Wasil E. Very large-scale vehicle routing: New test problems, algorithms, and results [J]. Computers & Operations Research, 2005,32(5): 1165-1179.
/
| 〈 |
|
〉 |