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

摘要

提出一种密度峰值聚类(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％.这证明了该算法是求解车辆调度问题的高效算法.