基于鲨鱼优化算法的农产品物流配送路径优化

尚 猛, 曹峻玮

(1. 安阳工学院飞行学院, 河南 安阳 455000; 2. 岭南大学经营学院, 韩国 庆山 385141)

在农产品物流配送系统中最重要的是配送中心选址和配送路径规划．由于农产品具有易变质的自然属性,对配送条件要求苛刻,因此对于农产品配送效率要求极高．为了尽可能减少农产品在物流配送过程中的损失, 从运行管理的角度优化设计物流配送路线被认为是解决问题最有效的方法[1]．目前, 用于求解物流配送路径优化问题的算法有两类:精确算法和启发式算法．精确算法是可以找到最优解的算法, 包括分支定界法,网络流算法和动态规划,但精确算法只适用于小问题或解决局部最优问题[2]; 启发式算法是一种基于直觉或经验结构的算法,可以快速获得满意的解决方案,但不一定能找到最优解,也不能解决复杂的节点问题[3]; 因此不少学者通过引用鲁棒交叉对接优化[4]或信息素动态更新[5]等方法对算法进行改进．Hamed[6]运用粒子群算法对物流配送的最短路径问题进行了求解, 取得了显著的结果; Wang等[7]提出一种多中心协同的的物流配送路径规划; Xiao等[8]提出一种带时间窗口约束的物流配送路径规划, 大幅降低了配送成本和配送时间; Guo等[9]提出一种正反向物流网络的物流路径规划策略, 用作业成本法对成本目标进行优化,提高了配送效率．此外还有列生成方法[10]、基于迭代局部搜索的模拟退火算法[11]以及可变惩罚函数的局部搜索算法[12]等优化策略．

近年来, Abedinia等[13]提出的鲨鱼优化算法(shark smell optimization, SSO)作为一种新的群体智能优化算法得到了广泛的关注。因调整的参数少且基于鲨鱼的螺旋猎食机制, 故SSO具有很强的局部搜索能力, 同时由于其局部搜索能力过强而使搜索陷入局部最优; 因此, 本文拟引入正弦运动机制和高斯变异策略帮助粒子跳出局部最优,并通过改进后的鲨鱼优化算法(improved shark smell optimization, ISSO)对农产品物流配送的最短路径问题进行求解．

1 农产品物流配送路径优化模型

1.1 问题描述及假设

农产品物流配送车辆调度问题为: 在客户需求量、车载量以及配送中心数目已知的条件下, 以物流车辆配送距离最短为目标函数,在规定时间内将货物由配送中心送达指定地点, 以保证农产品损失最小, 并使每个客户有且仅有1辆车进行1次配送, 完成配送任务后车辆返回配送中心; 所以农产品物流配送车辆调度问题的关键在于通过优化配送路线和车辆的行驶路线使总运输距离最短且耗时较少．

从配送中心发送货物时, 假设：① 每个客户点的需求量已知; ② 配送车的出发点和终点均为配送中心; ③ 车载量须大于其配送路线上客户需求量的总和; ④ 每条配送路线有且仅有1辆配送车; ⑤ 每辆配送车的行驶路线不重复; ⑥ 每辆车的总配送里程不超过配送车辆的最大行程; ⑦ 超过配送时间后, 货物因变质产生的损失与超出时间成线性关系．

1.2 模型目标函数和约束条件

2 改进的鲨鱼算法

2.1 标准SSO算法

在标准SSO算法[15]中, 先定义NP个最初的速度矢量, 则不同阶段的速度vi,k=ηkR1fO|xi,k, 其中i=1,2,…,NP; 所处状态数k=1,2,…,kmax; 参数ηk∈[0,1]表示每个阶段下鲨鱼的速度小于等于目标函数梯度所对应的速度值; 随机数R1均匀分布在[0,1]之间, 使算法具有更多的随机性;fO是目标函数;xi,k是鲨鱼在各个阶段的初始位置．考虑到惯性, 则第j维度上鲨鱼的速度为其中惯性系数αk∈[0,1], 在k阶段内为恒定值, 该值的增大意味着更高的惯性;R2是另一个均匀分布在[0,1]之间的随机数, 可进一步提高搜索的多样性．vij,0是开始搜索前的初始速度, 可忽略或随机设置成一个很小的值．

2.2 ISSO算法

改进算法求解的具体步骤为: ① 初始化参数, 即鲨鱼种群规模大小为NP, 最大迭代次数为Tmax; ② 求解种群中个体的适应度函数; ③ 判断是否达到最大迭代次数, 若是,则直接输出最终结果; ④ 更新速度和位置; ⑤ 通过高斯变异改变种群部分个体特性,并做边界处理; ⑥ 输出最终结果．

3 算例仿真

为验证所提出方法的可行性和有效性, 本文通过一个算例对改进的鲨鱼优化算法与标准鲨鱼算进行了对比仿真实验．算例参数设置为m=5,N=15,Q=10, 即配送中心利用5辆配送车为15位客户配送货物,其中每辆物流车的最大载物量为10, 表1为客户间及客户与配送中心间的距离．应用上面所构建的模型及算法在Matlab平台上进行仿真实验, 对此算例进行了500次求解,表2为随机选取的2种优化算法下得到的结果,表3为优化所得路径的配送车行程．

表1 客户之间及客户与配送中心距离

由表3可知,完成所有订单任务,ISSO算法较SSO算法所优化路径的总里程平均减少了100 km, 较大地降低了运输成本, 表明ISSO算法可有效地解决供应商路由问题．同时, 计算结果显示,ISSO算法下优化得到的每辆车行驶里程也相对较小,降低了车辆损耗及维修成本,从而进一步降低物流配送成本,大大增加配送企业的收益．

表2 不同算法得到的优化路径

表3 不同算法下的优化路径里程表

4 结论

传统的农产品物流配送路径因规划不合理导致农产品在配送过程中损失量较大,这不仅影响企业的收益,而且也造成资源的浪费．为防止传统鲨鱼优化算法因粒子陷入局部最优导致无法找到最优解,影响配送效率,造成农产品损失,本文应用正弦策略和高斯变异改进了算法．实验结果表明,本文算法与传统鲨鱼优化算法相比,配送路径的规划更加合理,可大大提高农产品的运输效率,有效地降低运输成本,提高收益．新方法满足了当代农产品物流所需要的时间性要求．