基于网络Voronoi图的大规模多仓库物流配送路径优化

doi:10.13485/j.cnki.11-2089.2014.0153

测绘学报 ›› 2014, Vol. 43 ›› Issue (10): 1075-1082.doi: 10.13485/j.cnki.11-2089.2014.0153

基于网络Voronoi图的大规模多仓库物流配送路径优化

涂伟¹,²,李清泉³,方志祥⁴

1. 深圳大学海岸带地理环境监测国家测绘地理信息局重点实验室
2. 深圳大学空间信息智能感知与服务深圳市重点实验室
3. 深圳大学土木工程学院空间信息智能感知与服务深圳市重点实验室
4. 武汉大学测绘遥感信息工程国家重点实验室

收稿日期:2013-12-17 修回日期:2014-03-12 出版日期:2014-10-20 发布日期:2014-10-24
通讯作者: 李清泉 E-mail:qqli@whu.edu.cn
基金资助:
基于众源GPS路线数据的城市道路网自动更新与重构;深圳市科技研发资金项目;深圳市科技研发资金项目;测绘遥感信息工程工程国家重点实验室资助项目

Large Scale Multi-depot Logistics Routing Optimization based on Network Voronoi Diagram

TU Wei¹,²,LI QingquanFANG Zhixiang⁴

Received:2013-12-17 Revised:2014-03-12 Online:2014-10-20 Published:2014-10-24
Contact: LI Qingquan E-mail:qqli@whu.edu.cn

摘要/Abstract

摘要：

由于存在多约束和多个优化目标，物流配送决策非常困难。针对城市多仓库物流配送问题，提出基于网络Voronoi图的空间启发式优化方法。从空间角度，将多仓库物流配送优化分解为区域分割和路径优化两个空间子问题。基于网络Voronoi覆盖进行服务区域初始划分，顾及仓库容量差异，进行区域边界修正，并创建初始解。路径优化将局部搜索范围限定在网络K近邻内，只搜索最有可能的空间邻域，迭代改进解的质量。该算法最小化路径数量和路径长度。利用深圳市的大规模多仓库物流配送问题测试算法性能。试验结果表明：本文方法能够在15 min内求解6400个客户点的大规模物流配送问题，解的质量优于ArcGIS约10.8%，计算时间约为其21.2%。

关键词: 物流, 启发式优化, 网络Voronoi图, 多仓库车辆路径

Abstract:

Due to multi-constraints and multi-objectives, the optimization for large scale multi-depot logistics routing problem is very difficult. This paper proposed a spatial

heuristicsalgorithm based on the network Voronoi diagram. From the spatial perspective, two involved spatial issues in the multi-depot logistics routing problem are service

area partitionand routing optimization.By using of depots’network Voronoi diagram, service areais coarsely partitioned and refinedaccordingto the goods storage in each

depot. For the routing optimization, the local search space is limited within the spatial neighbors of customers. The proposed heuristics minimizesthe used vehicles number

and the total routes length.An experiment on several large scale logistics distribution instances in Shenzhen, China was implemented to validate the performance of the

proposed heuristics algorithm. Results indicated that itprovided high quality solution for large scale instances with 6400 customersin no more than 15 minutes. The proposed

heuristics algorithm could be widely used in e-commerce, express delivery,public utility in city to promote logistics efficiency.

涂伟李清泉方志祥. 基于网络Voronoi图的大规模多仓库物流配送路径优化[J]. 测绘学报, 2014, 43(10): 1075-1082.

TU Wei LI Qingquan FANG Zhixiang. Large Scale Multi-depot Logistics Routing Optimization based on Network Voronoi Diagram[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(10): 1075-1082.

参考文献

[1]戚铭尧.面向物流的空间信息服务及其关键技术研究[J].博士后出站报告北京中科院遥感应用研究所, 2006, :- [2]REPOUSSIS P P, PARAKEVOPOULOS D.ZOBOLAS G,et al. A web- based decision support system for waste lube oils collection and recycling[J].European Journal of Operational Research, 2009, 195(3):676-700 [3]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 [4]SANTOS L, COUTINHO-RODRIGUES J, AND CURRENT J R.Implementing a multi-vehicle multi-route spatial decision support system for efficient trash collection in Portugal[J].Transportation Research Part A: Policy and Practice, 2008, 42(6):922-934 [5]LAPORTE, G.Fifty Years of Vehicle Routing[J].Transportation Science, 2009, 43(4):408-416 [6]LI F, GOLDEN B, AND WASIL E.Very large-scale vehicle routing: new test problems,algorithms,and results[J].Computers & Operations Research, 2005, 32(5):1165-1179 [7]TOTH P AND DANIELE V. .The Vehicle Routing Problem [J].Society for Industrial and Applied Mathematics, 2002, :- [8]ZACHARIADIS, E.E. AND KIRANOUDIS,CT. 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 [9]HO W.HO G T S,JI P,et alA hybrid genetic algorithm for the multi-depot vehicle routing problem[J].Engineering Applications of Artificial Intelligence, 2008, 21(4):548-557 [10]CORDEAU J F, GENDREAU M, AND LAPORTE G.A tabu search heuristic for periodic and multi-depot vehicle routing problems[J].Networks, 1997, 30(2):105-119 [11]Kuo, Y, and Wang C C.A variable neighborhood search for the multi-depot vehicle routing problem with loading cost[J].Expert Systems with Applications, 2012, 39:6949-6954 [12]YU B, YANG Z Z, and XIE J X.A parallel improved ant colony optimization for multi-depot vehicle routing problem[J].Journal of the Operational Research Society, 2010, 62:183-188 [13]SHI Yarong, WAN Difang, LI Shuangyan, and LV Zhenyu.Research of vehicle routing problem based on GISSystem Engineering- Theory & Practice[J].史亚容万迪昉李双燕吕珍玉基于的物流配送路线规划研究系统工程理论与实践, 2009, 29(10):76-85 [14]FANG Zhixiang, TU Wei, LI Qingquan, Shaw Shihlung, Chen Shunqing, and Chen Biyu.A Voronoi neighborhood-based search heuristic for distancecapacity constrained very large vehicle routing problems[J].International Journal of Geographical Information Science, 2013, 27(4):741-764 [15]涂伟，李清泉，方志祥.A heuristic algorithm for large scale vehicle routing problem[J].武汉大学学报信息科学版, 2013, 38(3):307-310 [16]ZHAO Yuan, ZHANG Xin-chang, KANG Ting-jun.A Parallel Ant Colony Optimization Algorithm for Site Location[J].Acta Geodaetica et Carto graphica Sinica, 2010, 39(3):322-327 [17]LIU Jiubao, TANG Xinming, LIU Zhengjun, WANG Hui-bin.Research algorithm of Shelter Assignment Based on Capabillity Limitation and Optimization of the Travel Cost[J].Acta Geodaetica et Carto graphica Sinica, 2011, 40(4):489-494 [18]OKABE A, SATOH T, FURUTA T, et al.Generalized network Voronoi diagrams: Concepts,computational methods,and applications[J].International Journal of Geographical Information Science, 2008, 22(9):965-994 [19]XIE Shunping, FENG Xuezhi, WANG Jiechen, LU Wei.Radiation Domain of Commercial Centers in Nanjing Based on Analysis of Road Network Weighted Voronoi Diagram[J].Acta Geograoghica Sinica, 2009, 64(12):1467-1476 [20]XIE Shunping, FENG Xuezhi, DU Jinkang.Maximal Covering Spatial Optimization Based on Network Voronoi Diagrams Heuristic and Swarm Intelligence[J].Acta Geodaetica et Carto graphica Sinica, 2011, 40(6):778-883 [21]AI Tinghua, YU Wenhao.Algorithm for Constructing Network Voronoi diagram Based on Flow Extension Ideas[J].Acta Geodaetica et Carto graphica Sinica, 2013, 42(5):760-766 [22]ZHU Weining, MA Jinsong, HUANG Xinyuan, XU Shou-chen.A Study of GIS Spatial Competition Analysis Model Based on Projective Weighted Voronoi Diagrams[J].Acta Geodaetica et Carto graphica Sinica, 2004, 33(2):146-150 [23]QI M, LIN W H, LI N, et al.A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows.[J].Transportation Research Part E: Logistics and Transportation Review, 2012, 48:248-257 [24]MOLE R AND JAMESON S.A sequential route-building algorithm employing a generalized savings criterion [J].Operational Research Quarterly, 1976, :503-511

基于网络Voronoi图的大规模多仓库物流配送路径优化

Large Scale Multi-depot Logistics Routing Optimization based on Network Voronoi Diagram

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价