2024年SEVC SCI2区，用于求解带时间窗车辆路径问题的邻域综合学习粒子群算法，深度解析+性能实测-程序员充电站

1.摘要

针对带时间窗车辆路径问题这一典型NP-hard组合优化难题，本文提出邻域综合学习粒子群优化算法N-CLPSO，将PSO更有效地适配到离散路径优化中。该方法通过引入移除-重插入邻域搜索提升局部开发能力，并构建信息矩阵IM与成本矩阵CM来指导客户移除与重插入，从而优化路径生成；同时提出半随机扰动策略增强全局探索，并保留精英解最长公共序列以避免种群退化。

2.提出的算法

N-CLPSO将CLPSO与新的局部搜索结合，用离散化的相邻弧编码重新定义粒子的位置与速度表示，使其适配VRPTW。算法在每轮位置/速度更新后先通过车辆插入策略尽量减少车辆数，并在个体或全局最优停滞时分别触发邻域搜索与多样性保持策略以避免陷入局部最优。
f i t n e s s ( X i t ) = N V ( X i t ) + n o r m a l i z e ( T D ( X i t ) ) fitness(X_i^t)=NV(X_i^t)+normalize(TD(X_i^t))fitness(Xit)=NV(Xit)+normalize(TD(Xit))
n o r m a l i z e ( x ) = arctan ⁡ ( x ) π 2 \mathrm{normalize}(x)=\frac{\arctan(x)}{\frac{\pi}{2}}normalize(x)=2πarctan(x)

其中，N V ， T D NV，TDNV，TD分别表示粒子对应的车辆数量和总距离。

N-CLPSO基本算子

N-CLPSO将VRPTW的粒子速度与位置表示为弧集合+概率，并定义缩放、合并与差分等算子完成离散化更新；为加速收敛，算法依据适应度排名动态调整学习概率与学习样本数：
P c i = s c i 2 ∗ N Pc_i=\frac{sc_i}{2*N}Pci=2∗Nsci
n = 2 + r o u n d ( c e i l ( N 2 ) − 2 N ∗ s c i ) n=2+\mathrm{round}\left(\frac{\mathrm{ceil}\left(\frac{N}{2}\right)-2}{N*sc_i}\right)n=2+round(N∗sciceil(2N)−2)

这一方式使低适应度粒子更多向优秀粒子学习、高适应度粒子保持稳定。

车辆插入策略

车辆插入策略在每次粒子更新后采用车辆插入策略压缩车辆数：依次移除某条车辆子路径V c ( i ) Vc(i)Vc(i)得到r ∗ r^*r∗，再将其客户集合ins按引导插入法重新插入r ∗ r^*r∗；若全部成功则删除该车辆并令n = n − 1 n=n-1n=n−1，否则保留原解并继续尝试其他子路径，从而在保证可行性前提下尽量减少车辆数量。

基于局部信息的引导式重插入算子

引导式重插入算子通过同时考虑客户的时空匹配关系与插入带来的路径增量成本来提升重插入质量：用信息矩阵IM刻画客户对在精英解中相邻出现的概率，用成本矩阵CM刻画客户插入不同位置的增量代价，最终根据两者排序综合选择最优插入点，若无可行位置则新开路径保证可行性。

仅对精英个体P b e s t P_{best}Pbest执行移除-重插入邻域搜索：随机移除D DD个客户形成待插入集合，再用上述引导重插入修复并保留更优解，其中移除数量随全局最优停滞时间增加：
D = min ⁡ ( ceil ⁡ ( I 10 ) , ceil ⁡ ( N 10 ) ) D=\min\left(\operatorname{ceil}\left(\frac{I}{10}\right),\operatorname{ceil}\left(\frac{N}{10}\right)\right)D=min(ceil(10I),ceil(10N))
在停滞时扩大邻域范围，提高跳出局部最优的能力。

基于精英片段的多样性保持策略

多样性保持策略为防止PSO多样性下降导致早熟收敛，在扰动粒子时保留其与精英粒子之间的最长公共子序列（LCS）作为精英片段，再将剩余节点通过引导重插入逐个插回生成新解并择优保留，从而在提升种群多样性的同时避免随机扰动过大造成性能退化；两粒子差异越大，被重构的节点越多。

3.结果展示

4.参考文献

[1] Wu Q, Xia X, Song H, et al. A neighborhood comprehensive learning particle swarm optimization for the vehicle routing problem with time windows[J]. Swarm and Evolutionary Computation, 2024, 84: 101425.