多策略改进的粒子群算法在VRPTW问题中的应用

来源：计算机技术与发展杂志2024年第11期北京时间：

作者：谢谢;周欢;杨裕霖

摘要：该文研究带时间窗约束的车辆路径问题(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 问题方面具有优越性和有效性。

关键词：车辆路径问题;粒子群算法;多策略改进;时间窗;组合优化问题