摘要:
针对现有优化算法求解带时间窗的车辆路径问题(vehicle routing problem with time windows, VRPTW)时存在易陷入局部最优解和收敛速度慢等问题,提出了一种基于K均值聚类和改进大规模邻域搜索算法(K-means clustering algorithm and improved large neighborhood search algorithm, K-means-ILNSA)的车辆路径优化算法。首先,采用先聚类后优化的策略,利用K-means算法对待配送客户进行分组,以提高优化效率。其次,采用遗传算法对聚类产生的每组客户进行单独优化,以初步规划配送路径。最后,引入大规模邻域搜索(large neighborhood search, LNS)算法对配送路径进一步优化,以有效避免算法陷入局部最优解。实验结果表明,所提算法能够有效解决带时间窗的车辆路径问题,其生成的车辆总路程短,优化求解效率高。