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

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

作　　者：张贝金 周晓根 明洁[1] 姚春龙[1] 张贵军[1] 

机构地区：[1]浙江工业大学信息工程学院,杭州310023

出　　处：《计算机科学》2014年第B11期29-34,共6页Computer Science

基　　金：国家自然科学基金(61075062);浙江省自然科学基金(LY13F030008);浙江省科技厅公益项目(2014C33088);浙江省重中之重学科开放基金(20120811);杭州市产学研合作资助项目(20131631E31);浙江省大学生"新苗计划"(2014R403090)资助

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

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

分 类 号：TP274[自动化与计算机技术—检测技术与自动化装置]