吴慧君

(福建船政交通职业学院，福建 福州 350007)

带容量约束的车辆路径问题(capacitated vehicle routing problem，CVRP)的主要特征是车辆有最大容量限制、各客户需求点有货物配送需求，该问题是一种典型的非确定性多项式(non-deterministic polynomial，NP)难题组合优化问题[1]。传统算法很难求解CVRP问题，近年来很多研究人员将群智能算法应用于CVRP问题求解。文献[2]将混合变邻域生物共栖搜索算法应用于CVRP问题求解。文献[3]将多种群人工蜂群算法用来求解带重新路由策略的CVRP问题。文献[4]提出了一种基于改进的粒子群优化算法的车辆路径优化方法。

灰狼优化算法(grey wolf optimization algorithm，GWO)是模仿灰狼等级划分和灰狼捕食行为而提出的群智能搜索算法[5]。该算法具有控制参数少、收敛速度快和计算简单等优点，已在机器学习、函数寻优、数据挖掘、电力调度、控制器设计调优等方面得到广泛应用[6-7]。目前应用灰狼优化算法求解CVRP的文献较少，因此本文提出一种基于GWO的农产品物流配送车辆路径优化方法。研究结果表明，与PSO和GA相比，在行驶里程和平均行驶成本方面，GWO的成本最低且行驶里程最少。

1 GWO算法

GWO算法中，灰狼个体分为α、β、δ和ω，其中，α负责狼群的决策与管理；β和δ为适应度次于α的灰狼个体；ω为其他灰狼个体。GWO算法主要包括包围、捕猎和攻击三种行为。

1.1 包围

在整个算法过程中，首先灰狼包围猎物，数学模型如公式(1)和公式(2)所示：

(1)

(2)

1.2 捕猎

包围猎物之后，狼群将捕猎猎物。假定α、β、δ分别为全局最优解、全局第二解以及全局第三解，对α、β、δ重新定位：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

1.3 攻击

狼群捕食的最后阶段就是攻击捕获猎物，攻击过程主要通过调节参数a实现。……