基于密度峰值聚类的VRPTW问题研究  

A Research on Vehicle Routing Problems with Time Windows Based on Density Peak Clustering

作　　者：吴斌[1] 宋琰 程晶 董敏[1] WU Bin;SONG Yan;CHENG Jing;DONG Min(School of Economics and Management,Nanjing Tech University,Nanjing 211816,China)

机构地区：[1]南京工业大学经济与管理学院,江苏南京211816

出　　处：《工业工程》2020年第5期58-66,74,共10页Industrial Engineering Journal

基　　金：国家自然科学基金资助项目(71671089);江苏省社会科学基金资助项目(18GLD005)。

摘　　要：提出一种密度峰值聚类(density peak clustering,DPC)与遗传算法(genetic algorithm,GA)相结合的新型混合算法(density peak clustering with genetic algorithm,DGA),求解带时间窗的车辆路径问题。首先应用DPC对客户进行聚类以缩减问题规模,再将聚类后的客户用GA进行线路优化。结果表明:DGA在9个数据集上的平均值比模拟退火(simulated annealing,SA)和禁忌搜索(Tabu)分别提高了13.41%和4.7%,单个数据集最大提高了26.4%。这证明了该算法是求解车辆调度问题的高效算法。A new hybrid algorithm(DGA)combining density peak clustering(DPC)and genetic algorithm(GA)is proposed to solve the vehicle routing problems with time windows.The DPC is used to cluster the customers to reduce the scale of the problem,and then the clustered customers are optimized by GA.The experimental results show that the average value of DGA on the nine data sets is 13.41%and 4.7%higher than simulated annealing(SA)and Tabu search,respectively,and the maximum increase of single data set is 26.4%.It is proved that the algorithm is an efficient method for solving vehicle scheduling problems.

关 键 词：密度峰值聚类 VRPTW问题 车辆调度 遗传算法 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]