Abstract: Vehicle Routing Problem (VRP) is crucial in logistics and distribution, especially in the case of constraints with time windows, the difficulty of solving it increases significantly. A Hybrid Particle Swarm Optimization (HPSO) algorithm was proposed for efficiently solving the Vehicle Routing Problem with Time Windows (VRPTW). The algorithm adopts Partially-matched crossover (PMX) to replace the traditional particle updating method, combines the worst-nearest-neighbor particle selection and roulette mechanism to enhance the diversity, and balances the global exploration and local exploitation capabilities through the dynamic weight adjustment strategy; designs the variable-neighborhood search optimization solution by integrating the 2-opt flipping, sequential insertion, and swapping operations, and optimizes the solution quality based on the greedy algorithm. quality, while generating high-quality initial solutions quickly based on the greedy algorithm. The experimental results show that the travel distance error of the HPSO algorithm stays within 1% of the known optimal solution for 69% of the test problems in the datasets of 25 and 50 customers on Solomon's standard test set, and obtains results consistent with the optimal solution in Class C instances with 100 customers, proving its effectiveness and competitiveness in solving complex VRPTW problems. Compared to the Neighbourhood Comprehensive Learning Particle Swarm Algorithm (N-CLPSO) in a dataset of 100 customers, the HPSO algorithm achieved a maximum reduction of 56% in standard deviation on the R102 test problem, and an average improvement of 41% in convergence speed on the C101 and R101 test problems. Experimental results show that HPSO algorithm significantly improves the solution accuracy, convergence efficiency and robustness of complex VRPTW problems through multi-strategy co-optimization.

Key words: Particle Swarm Optimization &#40, PSO&#41, Vehicle Routing Problem &#40, VRP&#41

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

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