基于集合粒子群优化与自组织映射混合的带容量约束车辆路径问题元启发式算法

《Algorithms》：A Hybrid Metaheuristics Based on an Improved Set-Based Particle Swarm Optimization and a Self-Organizing Map for the Capacitated Vehicle Routing Problem

　　

带容量约束车辆路径问题（CVRP）是一类具有广泛物流与运输应用背景的代表性NP难组合优化问题。研究人员提出一种称为SPSOM-CVRP的混合元启发式算法，其将改进的基于集合的粒子群优化（SPSO）与自组织映射（SOM）相集成。在SPSOM-CVRP中，改进的SPSO负责构建可行的CVRP解，而SOM执行路径级精炼以提升解质量。为强化探索，当粒子的个体最优在预定代数内未变化时，随机重新分配两个新的学习范例给该粒子。为增强开发并避免过高计算代价，仅当全局最优解停滞时激活基于SOM的路径优化，并施用于选中的精英解。由此，粒子级与种群级停滞信息被联合用于协调探索与开发。在三个基准数据集上的实验研究表明，SPSOM-CVRP以相对较低的计算代价取得了具竞争力的解质量。此外，该方法获得了若干有前景的路径配置，包括在修改路径数下比已有报道结果更短行驶距离的的解。需注意，所提算法配置是经验驱动的；其有效性在所选CVRP基准套件及被测特定路径数设置上得到验证，而非宣称对所有可能CVRP实例或所有组合优化问题均普适最优。

研究背景方面，带容量约束车辆路径问题（Capacitated Vehicle Routing Problem, CVRP）由Dantzig与Ramser首次提出，因在物流、运输与配送系统中具有广泛实践相关性而长期受到关注。CVRP考虑一支由容量受限的同构车辆组成的车队从公共仓库出发服务地理分散且需求已知的客户并最终返回仓库，目标通常为最小化总行驶成本，同时每个客户恰被服务一次且每车总需不超过容量，属NP难问题。随着实例规模增大，精确算法计算代价高昂，启发式与元启发式成为在可接受时间内获取高质量解的重要替代。经典启发式分构造式与改进式两类，前者按预定义准则增量插客户，后者从现有解出发迭代精炼，常用2-opt、3-opt及交换算子，但易陷于劣质局部最优。元启发式如差分进化（Differential Evolution, DE）、蚁群优化（Ant Colony Optimization, ACO）、粒子群优化（Particle Swarm Optimization, PSO）、禁忌搜索（Tabu Search, TS）与遗传算法（Genetic Algorithms, GAs）提供更灵活全局搜索框架，但仍可能早熟收敛，需结合问题特有构造、修复或局部搜索形成混合算法。自组织映射（Self-Organizing Map, SOM）原用于拓扑保持映射，曾扩展至旅行商问题（Traveling Salesman Problem, TSP）与CVRP，但直接用于CVRP需显式处理容量约束，常伴不可行或低质解。基于集合的粒子群优化（Set-Based PSO, SPSO）以弧集与概率表示位置速度，构造式更新可在生成解时维持可行性，故SPSO与SOM在功能上互补：前者全局探索与可行构造，后者路径级开发。该研究即在此动机下开展。

研究人员开展的研究为提出SPSOM-CVRP混合元启发式，将去掉加速系数的改进SPSO与增长式SOM（Growing SOM, GSOM）集成，并以停滞信息驱动两组件激活。改进SPSO中速度更新弃用认知与社会加速系数c₁、c₂，改为从种群随机选两粒子历史最优作学习范例；若粒子个体最优停滞代数超阈值τ_p则重分配范例以增强探索。SOM不作为独立CVRP求解器，而将每可行解的単车路径视为TSP子类子问题作路线级精炼；仅当全局最优停滞代数超τ_g时对选中比例α的精英解激活SOM，避免每代调用之算力浪费。论文发表于MDPI期刊《Algorithms》（algorithms-19-00740）。

关键技术方法上，研究人员采用三基准数据集A、B、P共74例（客户16–101，车辆2–15，单仓库）作评测样本；算法以Matlab R2022a实现，Intel Core i7 4.20 GHz/16 GB环境独立运行30次；改进SPSO用线性递减惯性权w∈[0.9,0.4]、种群规模N=?D/2?、最大代T=500、全局停滞停限25；停滞阈值经灵敏度分析定为τ_p=5、τ_p重分配模5、τ_g=20、SOM激活模20、精英比α=0.1；SOM用GSOM以客户坐标为输入、输出神经元竞争胜者并按邻域更新权值、每λ_g=10代插新神经元；位置构造用速度模糊集转清晰集后按贪婪概率ρ(t)=0.5+0.5t/T选下一客户，兼顾早期探索与后期开发。

研究结果部分，第2节给出CVRP图论模型与(1)–(5)式目标约束（总距离最小、每客一次、容量不超Q、起讫仓库）。第3节述标准PSO连续速度位置更新式(6)(7)及去掉c₁c₂的简化式(8)；SPSO以位置X_i^t为节点邻弧集、速度V_i^t为弧选概率集，速度更新式(12)–(17)、位置经模糊化式(18)与Algorithm 1–2顺序构造满足容量解。第4节述SOM/GSOM竞争胜者式(20)、邻域更新式(21)(22)、生长插入式(23)–(25)及Algorithm 3（SOMTSP）。第5节给出SPSOM-CVRP动机（SPSO保可行、SOM精炼TSP类子路径）、Algorithm 4骨架与复杂度：时间主导O(NTD²+(T/τ_g)αND²)≈O(NTD²)，空间O(ND)。第6节实验中，6.2.1显示c₁=c₂=1与去系数间误差和差异不大故简化合理；6.2.2热图表明τ_p=5、τ_g=20综合优；6.2.3消融显示SPSOM-CVRP在A、B集Best/Avg均优于纯SPSO且Wilcoxon检验显著，收敛图显示前50代两算法相近、后段SOM提速提质；6.3综合对比七种同行算法（ABC、CS、FA系、PSOGWO、HGA-VNS、DRL-CVRP等），SPSOM-CVRP在A集27例获16优，与HGA-VNS、CVRP-CHFA、RBMC-ABC无显著差异，平均耗时26.16/27.77/26.49秒低于HGA-VNS与RBMC-ABC；并在B-n57-k7、P-n22-k8、P-n55-k15以多一车换更短距，P-n55-k8以7车580距优于已知8车588距，证明全局搜索力强。

讨论与结论部分，研究人员指出SPSOM-CVRP以粒子级停滞重分配范例与种群级停滞启SOM精炼协调探索开发，在A/B/P集以低计算代价得竞争力解；简化速度更新与停滞阈值为经验驱动、非任意CVRP实例普适最优之证；局限含理论缺分析保证、阈值预设未必跨景观最优、规模扩展性未全探。结论重申：改进SPSO作可行构造与全局探索，GSOM作路径级开发，停滞双级驱动免每代高代价精炼；实验证τ_p=5、τ_g=20平衡良，SOM组件一致提质伴适度时增；P-n55-k8获7路线580距支配已知8路线588距，彰显集合PSO与SOM路线精炼结合之潜力。