| 基于密度峰值聚类的VRPTW问题研究 |
| |
| 引用本文： | 吴斌,宋琰,程晶,董敏.基于密度峰值聚类的VRPTW问题研究[J].工业工程,2020,23(5):58. |
| |
| 作者姓名： | 吴斌 宋琰 程晶 董敏 |
| |
| 作者单位： | 南京工业大学 经济与管理学院，江苏 南京 211816 |
| |
| 基金项目： | 国家自然科学基金资助项目(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%。这证明了该算法是求解车辆调度问题的高效算法。
|
| 关 键 词： | 密度峰值聚类 VRPTW问题 车辆调度 遗传算法 |
| 收稿时间： | 2019-08-20 |
A Research on Vehicle Routing Problems with Time Windows Based on Density Peak Clustering |
| |
| WU Bin,SONG Yan,CHENG Jing,DONG Min.A Research on Vehicle Routing Problems with Time Windows Based on Density Peak Clustering[J].Industrial Engineering Journal,2020,23(5):58. |
| |
| Authors: | WU Bin SONG Yan CHENG Jing DONG Min |
| |
| Affiliation: | School of Economics and Management, Nanjing Tech University, Nanjing 211816, China |
| |
| Abstract: | 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. |
| |
| Keywords: | density peak clustering vehicle routing problems with time windows (VRPTW) vehicle scheduling genetic algorithm |
|
| 点击此处可从《工业工程》浏览原始摘要信息 |
|
点击此处可从《工业工程》下载全文 |
