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

doi:10.13485/j.cnki.11-2089.2014.0153

Abstract

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.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 0

Recommended Articles

Metrics

Comments