Abstract:

To efficiently solve Vehicle Routing Problems with Time Windows （VRPTW）， a Hybrid Particle Swarm Optimization （HPSO） algorithm was proposed. This algorithm replaced the traditional particle update method with Partially Matched Crossover （PMX）， enhanced diversity by combining the worst neighbor particle selection and roulette wheel selection mechanism， and balanced global exploration and local exploitation capabilities through a dynamic weight adjustment strategy. A Variable Neighborhood Search （VNS） integrating 2-opt inversion， sequential insertion， and swap operations was designed to optimize solution quality， and a greedy algorithm was used to quickly generate high-quality initial solutions. Experimental results on the Solomon standard test set show that the HPSO algorithm has the solution gap within 1% with the known optimal solution for 69% of the test problems in datasets with 25 and 50 customers， and has the solution almost close to the optimal solution for C-class test problems with 100 customers， demonstrating its effectiveness and competitiveness in solving complex VRPTW. On datasets with 100 customers， compared with the Neighborhood Comprehensive Learning Particle Swarm Optimization （N-CLPSO） algorithm， the HPSO algorithm reduces the standard deviation by at least 2.4% on the RC102 test problem， and improves the convergence speed by an average of 41% （59% and 23%） on the C101 and R101 test problems. Through the collaborative optimization of multiple strategies， the HPSO algorithm can significantly improve the solution accuracy， convergence efficiency， and robustness of complex VRPTW.

Key words: Particle Swarm Optimization (PSO) algorithm, Vehicle Routing Problem (VRP), time window, Variable Neighborhood Search (VNS), combinatorial optimization problem

摘要：

为了高效解决带时间窗的车辆路径规划问题（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的求解精度、收敛效率与鲁棒性。

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