为求解带时间窗车辆路径问题(vehicle routing problem with time window,VRPTW),针对启发式算法求解路径优化问题的精确度低、时间长等缺点,提出了一种基于密度聚类方法的变邻域模拟退火算法(simulated annealing with variable neighb...为求解带时间窗车辆路径问题(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求得解的质量更好,具有可靠的全局稳定性。展开更多
文摘为求解带时间窗车辆路径问题(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求得解的质量更好,具有可靠的全局稳定性。