基于改进人工蜂群算法的生鲜农产品配送路径优化

汪 涛，潘 郁，潘 芳，朱晓峰

（1.南京工业大学经济与管理学院，江苏 南京 211816；2.南京中医药大学卫生经济管理学院，江苏 南京 210023）

经济快速发展，生活水平提高，人们对生鲜农产品的质量提出了更高要求。生鲜农产品是指由农户生产、养殖的初级农畜产品，主要包括新鲜肉蛋奶、蔬菜、水果、水产品，活禽五类产品，常温下易变质，对时间因素具有较强的敏感性［1］。合理高效的配送路径，一方面大大降低了配送成本，使商家和农户获得更高的利润；另一方面，高效率配送大大缩短生鲜农产品的配送时间，使得农产品的质量得以保证，从而提高了客户的满意度。因此，在生鲜农产品配送系统中，需要采取更合理高效的配送策略，实现高效率、低成本的物流配送。

近年来，由于生鲜农产品的配送路径优化研究具有较强的实践性和理论性，国内外学者对该问题进行了大量研究。Hsu等［2］以固定成本、运输成本、库存成本和惩罚成本构建最小化成本目标函数，提出了利用VRPTW模型优化配送路径问题；Osvald等［3］提出带时间窗的新鲜蔬菜配送车辆路径优化的数学模型，并通过禁忌搜索的启发式算法来进行求解；赵秀荣等［4］分析当前我国生鲜农产品冷链物流配送的现状及干扰因素，提出构建大型冷链物流配送中心、销地冷链物流共同配送联盟和"一站式"冷链配送网络信息平台等策略；Dabbene等［5］考虑到鲜活农产品的易腐特性，以最大程度保证鲜活农产品的品质和严格控制配送成本作为目标，对鲜活农产品供应链流程加以优化；康凯等［6］构建了考虑碳排放的生鲜农产品配送路径优化模型，提出一种结合2-opt局部搜索机制的改进蚁群算法，并用实例对模型及算法的有效性进行验证，同时对算法参数进行了敏感性分析；JuChia等［7］考虑到生鲜农产品对温度的敏感性，提出一种针对该问题的多温度共同配送物流模式，并通过相应的算例验证了该模式的合理性与有效性；Brito等［8］利用模糊方法来求解冷冻食品的配送路径优化问题，最终效果良好，且可以有效避免冷链的断裂；吕俊杰等［9］从物流配送商的角度出发，构建基于冷藏车能耗成本分析的路径优化模型，应用蚁群算法和MATLAB工具论证了模型的有效性；但斌等［10］以拼好货为例，分析得出生鲜农产品供应链C2B商业模式的实现路径包括产品与服务、供应链管理策略、市场营销策略、关键流程构建以及核心能力优化等因果关联的五大要素；孙明明等［11］针对生鲜农产品冷链物流的特殊性，分析和定义冷链物流配送过程中的时间、温度和货损成本，建立配送总成本最小化模型；丁秋雷等［12］分析了干扰事件对生产商、客户和物流配送运营商3个行为主体的影响，提出鲜活农产品物流配送的干扰管理模型，取得了良好的优化效果；张文峰等［13］同时考虑到冷链物流的网点布局问题和运输配送问题，提出了以冷链物流运输成本和网点运营成本为优化目标的非线性整数规划模型，并采用量子粒子群算法进行求解；朱佳祥等［14］考虑到生鲜农产品市场需求的时变性、模糊不确定性特点，以“多供应点选择”与“最早分发”为优化目标构建了模糊决策模型，有效解决了因市场需求信息模糊导致的配送成本增加问题。

通过对比发现，上述研究在构建模型时均存在生鲜农产品配送成本考虑不全的问题。大多研究都采用固定成本、运输成本和惩罚成本作为配送总成本，没有考虑随着时间推移，鲜活农产品本身也会产生损耗成本。鉴于此，本研究结合时间价格成本、固定成本、运输成本和惩罚成本，将鲜活农产品在运输过程中的时间价格成本考虑进来，构建一个求解鲜活农产品配送总成本最小的数学模型。在研究过程中，采用改进后的人工蜂群算法进行求解，避免了模型过早陷入局部最优的问题，加速了模型的收敛过程，具有更强的实践指导作用。

1 配送成本模型

1.1 模型假设

鲜活农产品物流配送模型是由1个配送中心向多个客户节点进行货物配送的模型。为简化模型，本研究作出如下假设：（1）配送中心有充足的配送车辆和货源，且每辆车的装载 重量、配送速度相同；（2）客户需求量已知，且单一客户的需求量不得高于车辆最大载重量；（3）客户需求以及配送中心配送产品相同且只有一种；（4）每辆车可对路径上任意客户进行配送，每个客户需求由一辆车完成配送；（5）模型只针对一个配送中心向其他客户节点进行配送。

1.2 符号说明

模型参数及其含义如表1所示。

1.3 成本模型构建

以生鲜农产品物流配送总成本作为最小化目标函数构建数学模型，总成本主要由固定成本、运输成本、惩罚成本和时间价格成本4个部分组成，其中固定成本为C1，而运输成本是生鲜农产品在向各个客户节点的运输过程中产生的费用，与车辆数量以及每辆车的配送距离成正比，运输成本计算公式为：

式中，Ck为车辆配送时单位里程的运输成本，xijk为变量0-1，当运输车辆从经过客户节点（i，j）时，xijk取值为1，否则为0。

惩罚成本的计算需要引入时间窗，时间窗分为软时间窗和硬时间窗，本研究模型中采用软时间窗，软时间窗比硬时间窗在时间范围内更具有弹性，当产品在客户期望时间内送达，惩罚成本为0；当产品不在客户期望时间内送达，按照时间惩罚函数来计算惩罚成本，M为单位时间惩罚费用，惩罚成本计算公式为：

考虑到随着时间的推移，鲜活农产品本身也会产生损耗成本，也就是时间价格成本，本研究不考虑运输完成后产品的损耗问题，只考虑到达客户节点i的时间和车辆出发时间， 再结合客户i的产品需求量以及单位产品价格P进行计算，时间价格成本计算公式为：

基于以上各类配送成本分析，建立配送总成本模型如下：

式（5）表示配送中心有充足的货源来满足所有客户需求；式（6）表示一条配送路径上的需求量之和不能超过车辆的最大载重量；式（7）和式（8）表示一个客户只有一辆车进行配送；式（9）表示每个客户都能够得到配送。

2 改进人工蜂群算法求解

2.1 算法改进

人工蜂群算法由埃尔吉耶斯大学学者Karaboga［15］首次提出。算法模拟蜜蜂采蜜过程，将蜜蜂分为3种：引领蜂、跟随蜂和侦察蜂，蜜蜂寻找食物源的过程就是模型求解过程，每个食物源对应物流配送路径优化问题中一个可行解，也就是一条路径。算法工作分为以下3个阶段，本研究分别对跟随蜂和侦察蜂阶段加以改进，具体如下：

式中，vid为候选食物源，，rid为[-1,1]之间的随机数。找到新的食物源之后，引领蜂采用贪心策略，若新食物源收益度高于当前食物源，则替换原来的解； 反之保持不变，随后引领蜂将收益度信息传递给跟随蜂。

2.1.2 跟随蜂阶段 在传统人工蜂群算法中，跟随蜂通常采用轮盘赌策略选择引领蜂，在这种策略下，适应值越大则被选择的概率也就越大，二者为线性关系，导致跟随蜂容易迅速向某一适应值高的食物源集中，从而使模型陷入局部最优。因此，本研究提出一种基于中位数的引领蜂选择策略来避免这个问题。基于中位数选择策略是以中间适应值为基准重新分配选择概率，从而在不影响高适应值食物源被选择概率的情况下，使适应值小的食物源也有被选择的几率。依据此策略跟随蜂选择引领蜂的概率公式如下：

式中，Fi为第i个食物源的适应值，Fmid为食物源适应值中位数，SN为表食物源的数量。通过改进后，有效提高了收益度较小食物源被选择的概率，同时不影响收益度较大的食物源被选择的概率，保证了选择的多样性，避免因某一食物源被集中选择导致局部最优情况的出现。选择引领蜂之后，跟随蜂会计算引领蜂传递信息中食物源的收益度值，计算公式如下所示：

式中，代表食物源，也就是一个可行解，为目标函数。

2.1.3 侦察蜂阶段 如果算法执行的搜索次数超过了设定值，某个食物源依旧保持不变，那么将抛弃这个食物源对应的可行解，对应的引领蜂变为侦查蜂，开始新一轮的食物源搜索。这种更新方式导致上一轮的有效搜索信息没有得到利用，使得算法存在一些迂回重复的搜索，导致算法效率偏低。鉴于此，本研究在新一轮的食物源搜索过程中引入禁忌表,将之前抛弃的食物源放入该禁忌表内,当跟随蜂在搜索过程中发现收益率值高的一组食物源后，首先查询该解是否在禁忌表内，如果是则放弃该可行解，除非满足释放准则，否则记录当前解为最优解。基于禁忌表的算法可行解更新流程如图1所示。

图1中，L为搜索次数，t为禁忌表长度参数，表示禁忌对象不被选取的最大迭代次数，t ＞ SN本文取释放准则为，表示当禁忌对象被禁次数超过食物源总数时，该对象即被解禁。禁忌表的引入，有效利用了上一轮搜索过程保留的食物源信息，避免了一些重复搜索，加速了算法的收敛。

2.2 改进人工蜂群算法实求解步骤

将改进后的算法对模型进行求解，具体求解步骤如下：

步骤1：设定算法中初始化阶段的各个参数，包括引领蜂、跟随蜂以及侦察蜂的数量，搜索次数上限limit、迭代次数上限MaxCycle；

图1 基于禁忌表的算法可行解更新流程

步骤3：根据式（10）生成算法初始解，并将初始解分配给对应的引领蜂，根据式（4）和式（13）对计算各个初始解的收益度值；

步骤4：开始迭代，重复步骤5～11；

步骤5：引领蜂根据式（11）在解的邻域内进行搜索，根据图1所示流程进行解的迭代更新；

步骤6：所有的解更新完成后，根据式（12）和式（13）计算引领蜂找到的解被跟随蜂选择的概率；

步骤7：根据步骤所选择的解，跟随蜂在该解对应的邻域内根据式（10）搜索新的解，然后根据式（12）计算对应的收益度值，再重复步骤5进行解的更新；

步骤8：如果某个解的limit值达到设定上限，则将该解加入禁忌表，侦察蜂重新生成一个新的解；

步骤9：记录当前最优解；

步骤10：迭代次数更新，cycle =cycle+1；

步骤11：判断算法迭代次数cycle是否超过MaxCycle，若次数超过MaxCycle，算法结束，步骤中所记录的解即为最优解；若没有超过则跳到步骤开始算法下一轮计算。

3 算例

本研究以某冷链物流公司配送中心作为研究对象，通过算例分析验证模型和算法的有效性。该配送中心需向个客户节点进行生鲜农产品的配送，配送中心农产品存货量为120 t，12个客户总需求量为52 t，生鲜农产品的单价P=10.2元，保鲜时间T=20 h，时间敏感因子η=3，单位时间惩罚费用M=50，车辆从配送中心出发的时间各个配送车辆型号相同。当前市场每台冷链配送车的月固定成本为3万元左右，即日均约1000元，取固定成本C1=100元，车辆平均车速v=60 km/s，最大载重量为Qmax=15 t，单位里程的运输成本元Ck=2.3 元/km。表2和表3分别为各个客户节点的需求量和时间窗约束以及节点之间的距离。

表2 各客户节点的需求量和时间窗

表3 各客户节点之间的距离

本研究的实验环境为台式机，运行内存8GB，64位Windows 7操作系统，算法采用MATLAB 7.0进行仿真实验，设定算法参数，仿真试验重复执行30次。整理汇总得到最终的配送情况如表4所示。从表4可以得出，完成全部客户节点的配送任务需要的车辆数k=4，4辆车有1辆达到满载，其余3辆的装载率也在80%以上，4辆车总共行驶距离为768 km，本次配送的总成本为C1+C2+C3+C4=6454.4元，比初始解节约3 733.7元，且惩罚成本为0，说明取得了良好的配送效果。

表4 优化后配送情况汇总

为验证算法改进的有效性，将算法改进前后的求解过程进行对比分析，结果见图2。从图2可以看出，传统人工蜂群算法求解目标函数值下降很快，但经过八轮迭代后算法就陷入局部最优值7 400左右，持续到40轮迭代算法陷入二次局部最优，直到40轮迭代后才开始逼近最优值，60轮左右收敛。而经过改进后的算法在10轮迭代后就逼近最优解，并在其附近振荡，迭代40轮算法收敛，最优解为6 454.4元。说明在传统人工蜂群算法中引入中位数选择策略来代替原有的轮盘赌选择策略后，有效解决了算法容易过早陷入局部最优的问题，且在解的更新阶段引入了禁忌表，加速了算法的收敛速度，因此改进后的人工蜂群算法具有更强的模型求解能力，能够解决生鲜农产品配送路径优化问题，有一定的实践指导意义。

图2 基于改进人工蜂群算法的求解过程

4 结语

本研究在构建生鲜农产品配送路径优化模型的基础上，考虑到鲜活农产品随时间推移产生的损耗成本，即时间价格成本，并结合配送产生的固定成本、运输成本和惩罚成本构建目标函数构建数学模型。本研究采用改进的人工蜂群算法对模型进行求解，算法引入基于中位数的选择策略替代轮盘赌选择策略，解决了算法容易过早陷入局部最优的问题，并且在解的更新阶段引入禁忌表加速了算法的收敛速度，通过算例仿真实验验证了模型和算法的有效性。路径优化问题是NP问题，本研究只考虑了单一配送中心的配送路径优化问题，且只考虑到单一农产品，如何解决多个配送中心同时配送多类产品的路径优化问题还有待进一步研究。