该文研究带时间窗约束的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW),这是一个典型的NP-Hard问题。针对传统粒子群算法求解带时间窗约束的车辆路径问题容易陷入局部最优的缺陷,提出了一种基于多策略方法改进的粒子...该文研究带时间窗约束的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW),这是一个典型的NP-Hard问题。针对传统粒子群算法求解带时间窗约束的车辆路径问题容易陷入局部最优的缺陷,提出了一种基于多策略方法改进的粒子群算法(Multi-Strategy improved particle Swarm Optimization Algorithm,MSPSO)来解决该问题。该算法采用惯性权重递减策略,使得算法在前期的全局搜索和后期的局部搜索都能够有良好的表现,通过引入随机选择策略更新粒子最优位置,可以增加解空间的多样性,有效避免算法陷入局部最优。最后通过测试Solomon Benchmark算例的结果,在25个客户的C103数据集上MSPSO算法对比RWPSO算法的行驶距离降低了38.29,对比S-PSO算法在C103、R103这两个数据集与最优解误差分别降低了1.76%和3.99%。在50个客户C1系列数据集上MSPSO算法对比PSO算法行驶距离分别减少了14.26、45.66、67.7,与数据集的最优解误差基本能保持在1%以内。从实验结果可以证明MSPSO算法在求解VRPTW问题方面具有优越性和有效性。展开更多
文摘该文研究带时间窗约束的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW),这是一个典型的NP-Hard问题。针对传统粒子群算法求解带时间窗约束的车辆路径问题容易陷入局部最优的缺陷,提出了一种基于多策略方法改进的粒子群算法(Multi-Strategy improved particle Swarm Optimization Algorithm,MSPSO)来解决该问题。该算法采用惯性权重递减策略,使得算法在前期的全局搜索和后期的局部搜索都能够有良好的表现,通过引入随机选择策略更新粒子最优位置,可以增加解空间的多样性,有效避免算法陷入局部最优。最后通过测试Solomon Benchmark算例的结果,在25个客户的C103数据集上MSPSO算法对比RWPSO算法的行驶距离降低了38.29,对比S-PSO算法在C103、R103这两个数据集与最优解误差分别降低了1.76%和3.99%。在50个客户C1系列数据集上MSPSO算法对比PSO算法行驶距离分别减少了14.26、45.66、67.7,与数据集的最优解误差基本能保持在1%以内。从实验结果可以证明MSPSO算法在求解VRPTW问题方面具有优越性和有效性。
