带有时间窗口的富网络配送问题研究及仿真

计算机科学 ›› 2014, Vol. 41 ›› Issue (Z11): 35-38.

带有时间窗口的富网络配送问题研究及仿真

张贝金,周晓根,明洁,姚春龙,张贵军

浙江工业大学信息工程学院杭州310023;浙江工业大学信息工程学院杭州310023;浙江工业大学信息工程学院杭州310023;浙江工业大学信息工程学院杭州310023;浙江工业大学信息工程学院杭州310023

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受国家自然科学基金(61075062),浙江省自然科学基金(LY13F030008),浙江省科技厅公益项目(2014C33088),浙江省重中之重学科开放基金(20120811),杭州市产学研合作资助

Vehicle Routing Problem with Time Window and its Application Based on Rich Road Network Weights

ZHANG Bei-jin,ZHOU Xiao-gen,MING Jie,YAO Chun-long and ZHANG Gui-jun

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 通过建立GIS富网络路网属性模型,并组合N阶最短近邻自适应聚类算法和遗传算法,来解决不确定车辆数目、较大规模网点和多层次交通网络的带时间窗口的联合配送问题。首先,为了解决传统带有时间窗口车辆线路调度模型中配送网点规模小(不超过20个网点)的问题,以及在建模时将各网点抽象为图的顶点的缺陷,建立基于实际道路数据的网络数据集,采用GIS技术精确计算各网点之间的距离,并建立距离OD矩阵；然后,为了降低对较大规模网点配送算法设计的复杂度,采用N阶最短近邻自适应算法确定聚类簇数,再通过聚类数划分配送网点。其次,为了确定配送车辆的种类、车辆数目以及时间窗口的限制,利用遗传算法对配送线路进行优化。最后,通过2个实例验证了所提方法的有效性。

关键词: 富网络模型,聚类算法,遗传算法,OD矩阵,路径规划

Abstract: To solve vehicle routing problem with indeterminate number of vehicles,large-scale outlets and multi-level transportation network,we established the road property mode based on rich network and GIS,mixed N-order nearest-neighbor adaptive clustering algorithm and genetic algorithm.Firstly,to solve the problem of small-scale outlets(less than 20 outlets) in traditional vehicle routing problem and the defect that abstracting the outlets into graph’s vertices during model establishing,we established network dataset based on actual road data,utilized GIS to exactly calculate the distance between outlets and built OD matrix of distance.Secondly,to reduce the complexity of designing large-scale outlets optimization algorithm,this paper used N-order nearest-neighbor adaptive clustering algorithm to determine the number of clusters,then divided the distribution outlets by clusters.Subsequently,to determine the kind and number of distribution vehicles and restriction of time window,we used genetic algorithm to optimize the distribution path.Finally,two examples verified the effectiveness of the proposed method.

Key words: Rich network model,Clustering algorithm,Genetic algorithm,OD matrix,Vehicle routing

张贝金,周晓根,明洁,姚春龙,张贵军. 带有时间窗口的富网络配送问题研究及仿真[J]. 计算机科学, 2014, 41(Z11): 35-38. https://doi.org/

ZHANG Bei-jin,ZHOU Xiao-gen,MING Jie,YAO Chun-long and ZHANG Gui-jun. Vehicle Routing Problem with Time Window and its Application Based on Rich Road Network Weights[J]. Computer Science, 2014, 41(Z11): 35-38. https://doi.org/

参考文献

[1] 杨弋,顾幸生.物流配送车辆优化调度的综述[J].东南大学学报:自然科学版,2003 (z1):105-111
[2] Lenstra J K,Kan A H G.Complexity of vehicle routing and scheduling problems[J].Networks,1981,11(2):221-227
[3] Solomon M M,Desrosiers J.Survey Paper-Time Window Constrained Routing and Scheduling Problems[J].Transportation science,1988,22(1):1-13
[4] Thangiah S R,Nygard K E,Juell P L.Gideon:A genetic algorithm system for vehicle routing with time windows[C]∥Se-venth IEEE Conference on Artificial Intelligence Applications,1991.IEEE,1991,1:322-328
[5] Blanton Jr J L,Wainwright R L.Multiple vehicle routing with time and capacity constraints using genetic algorithms[C]∥Proceedings of the 5th International Conference on Genetic Algorithms.Morgan Kaufmann Publishers Inc.,1993:452-459
[6] Hwang H S.An improved model for vehicle routing problemwith time constraint based on genetic algorithm[J].Computers & Industrial Engineering,2002,42(2):361-369
[7] Timucin Ozdemir H,Mohan C K.Evolving schedule graphs for the vehicle routing problem with time windows[C]∥Procee-dings of the 2000 Congress on Evolutionary Computation,2000.IEEE,2000,2:888-895
[8] Tan K C,Lee T H,Ou K,et al.A messy genetic algorithm for the vehicle routing problem with time window constraints[C]∥Proceedings of the 2001 Congress on Evolutionary Computation,2001.IEEE,2001,1:679-686
[9] Baker B M,Ayechew M A.A genetic algorithm for the vehicle routing problem[J].Computers & Operations Research,2003,30(5):787-800
[10] 戚铭尧,张金金,任丽.基于时空聚类的带时间窗车辆路径规划算法[J].计算机科学,2014,41(3):218-222
[11] Chen A Y,Pea-Mora F,Ouyang Y.A collaborative GIS framework to support equipment distribution for civil engineering disaster response operations[J].Automation in Construction,2011,20(5):637-648
[12] Zsigraiova Z,Semiao V,Beijoco F.Operation costs and pollutant emissions reduction by definition of new collection scheduling and optimization of MSW collection routes using GIS.The case study of Barreiro,Portugal[J].Waste management,2013,33(4):793-806
[13] 张贵军,吴惕华.GIS 线形矢量图形最优路径算法研究及仿真实现[J].系统仿真学报,2003,15(4):551-553
[14] 洪榛,张贵军,俞立.基于 N 阶近邻分析的自适应差分进化算法[J].控制理论与应用,2012,28(11):1613-1620

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed