基于聚类的变邻域模拟退火算法求解VRPTW

Simulated annealing with variable neighborhood based on clustering for vehicle routing problem with time window

为求解带时间窗车辆路径问题(vehicle routing problem with time window,VRPTW),针对启发式算法求解路径优化问题的精确度低、时间长等缺点,提出了一种基于密度聚类方法的变邻域模拟退火算法(simulated annealing with variable neighborhood based on density-based spatial clustering of application with noise,DBSCAN/SAVN)。DBSCAN/SAVN算法首先用DBSCAN聚类算法确定出若干簇类来降低数据规模;针对模拟退火算法中的metropolis准则在求解VRPTW时收敛速度慢、容易陷入局部最优解的缺点,使用3种扰动算子构造出变邻域模拟退火算法的邻域结构;最后通过改进的模拟退火算法对簇类中的小规模车辆路径问题进行求解。通过仿真实验与其他优化启发式算法相比,DBSCAN/SAVN求得解的质量更好,具有可靠的全局稳定性。

In order to solve the vehicle routing problem with time window,aiming at the shortcomings of heuristic algorithm,such as low accuracy and long time,a simulated annealing with variable neighborhood based on density-based spatial clustering of application with noise(DBSCAN/SAVN)is proposed.The DBSCAN/SAVN algorithm first uses DBSCAN clustering algorithm to determine several clusters to reduce the data size,then uses three perturbation operators to construct the neighborhood set of variable neighborhood simulated annealing algorithm to avoid slow convergence speed and falling into local optimal solution.Finally,the improved simulated annealing algorithm is used to solve the small-scale vehicle routing problem of the cluster.Compared with other heuristic optimization algorithms,DBSCAN/SAVN has better quality and reliable global stability.