混合粒子群优化算法求解带时间窗的车辆路径规划问题

来源：计算机应用杂志2026年第1期北京时间：

作者：周璐辉, 岳雪芝

单位：江西理工大学 理学院，江西 赣州 341000

摘要：为了高效解决带时间窗的车辆路径规划问题（VRPTW），提出一种混合粒子群优化（HPSO）算法。该算法采用部分匹配交叉（PMX）替代传统粒子更新方式，结合最劣近邻粒子选择与轮盘赌机制增强多样性，并通过动态权重调整策略平衡全局探索与局部开发能力；设计融合2-opt翻转、顺序插入和交换操作的变邻域搜索（VNS）优化解质量，并基于贪婪算法快速生成优质初始解。实验结果表明，在Solomon标准测试集上， HPSO算法在25和50个顾客的数据集中的69%的测试问题上的解与已知最优解差距保持在1%以内，在100个顾客的C类测试问题上几乎接近最优解结果，表明它在求解复杂VRPTW上的有效性和竞争力；在100个顾客的数据集上，相较于邻域综合学习粒子群（N-CLPSO）算法，HPSO算法在RC102测试问题上标准差至少降低2.4%，在C101和R101测试问题上的收敛速度平均提升了41%（59%和23%）。HPSO算法通过多策略协同优化，能显著提升复杂VRPTW的求解精度、收敛效率与鲁棒性。

关键词：粒子群优化算法,路径规划,时间窗,变邻域搜索,组合优化问题

基金资助：国家自然科学基金资助项目(61966015)