基于混合人工蜂群算法的容量约束车辆路径优化  

Optimization of Capacitated Vehicle Routing Based on Hybrid Artificial Bee Colony Algorithm

作　　者：李阳[1] 谷雯雯 LI Yang;GU Wen-wen(School of Economics and Management,Liaoning Petrochemical University,Fushun,Liaoning 113001)

机构地区：[1]辽宁石油化工大学经济管理学院,辽宁抚顺113001

出　　处：《供应链管理》2025年第4期97-112,共16页SUPPLY CHAIN MANAGEMENT

基　　金：2020年教育部人文社会科学研究青年基金项目“共享经济下众包物流的动态协同配送机制研究”(20YJC630070);2019年辽宁省教育厅科学研究经费项目“O2O新零售环境下电商同城配送的合单协同及即时优化研究”(L2019050);2022年辽宁省社会科学规划基金一般项目“动态订单即时匹配下的电商物流配送优化研究”(L22BGL034)。

摘　　要：针对容量约束车辆路径问题,文章构建了以路径成本最低为目标的混合整数规划模型,结合模型及CVRP问题特征设计了混合启发式算法进行求解。混合启发式算法集合人工蜂群算法及变邻域搜索算法,在人工蜂群局部搜索环节嵌入多变邻域算子展开迭代,算子中包含对路径节点、字符串及子路径的针对性变换操作,保证蜂群种群多样性,设计侦察蜂变邻域算子扰动策略强化算法跳出局部最优的能力。文献算例集及其算法求解的对比分析表明,混合变邻域人工蜂群算法参数及局部搜索策略设置合理有效,全局搜索能力强,能求得74个算例中47个最优解,求解精度高,最优解平均最小偏差为0.34%,尤其在求解稳定性方面表现良好,平均算例集平均值偏差为0.57%,整体性能优于所对比文献算法。Aiming at the capacitated vehicle routing problem,a hybrid integer programming model with the goal of lowest path cost is constructed,and a hybrid artificial bee colony algorithm based on the model and the characteristics of the CVRP problem is proposed to solve the problem.The hybrid algorithm integrates the artificial bee colony algorithm and the variable neighborhood search algorithm,embeds a multi-variable neighborhood operator in the local search link of the artificial bee colony to carry out iteration.And the operator contains targeted transformation operations on path nodes,strings,and sub paths to ensure the diversity of the bee population.In addition,a variable neighborhood perturbation strategy is used to strengthen the algorithm s ability to escape from local optima.The comparative analysis of the literature study sets and its algorithm solution shows that the designed hybrid artificial bee colony algorithm has strong global search ability and high solution accuracy,especially in solution stability.HABC can obtain 47 optimal solutions in 74 examples.The average minimum deviation of the optimal solution is 0.34%,and the average deviation of the average CVRP set is 0.57%.The overall performance is better than the algorithm in the comparative literature.

关 键 词：组合优化 车辆路径问题 人工蜂群算法 变邻域搜索算子 容量约束 路径优化 

分 类 号：F252[经济管理—国民经济]