基于改进蚁群算法的冰鲜水产品配送路径优化方法研究

冰鲜水产品是指在对水产品进行活体宰杀后不将其冰冻，而是铺上一层冰使其温度保持在冰的溶点附近以保证品质的水产品。冰鲜相对于其他低温保鲜方式能确保水产品肉体细胞不发生变质，减少了其贮藏过程中的水分流失，最大限度地保留了海鲜的营养与口感。据海关数据统计，辽宁省2017年水产品对外贸易总量为212.14万 t，总额为51.18亿美元，同比2016年分别增长了19.2%和11.4%，位居全省大宗农产品出口首位。水产品对外贸易稳步增长的同时，对配送的要求也越来越高，而冰鲜保质期较短，为保证其产品质量，研究冰鲜水产品配送路径优化具有重要意义。

目前，在配送路径的优化方面，专家学者已对其求解算法做了一定研究，已经建立了较为成熟的体系模型。黄华芳等[1]对运输车辆路径进行再优化，通过改进蚁群算法解决了运输车辆在原有路径中不能及时送货的问题。陈迎欣[2]针对蚁群算法缺点，分别对信息素更新方式和启发因子的设定进行了改进。范小宁等[3]应用遗传算法解决了当前蚁群算法在解决VRP问题时收敛速度慢的问题，构建了解决该问题的新型蚁群算法模型。董凌艳等[4]提出了加入再励学习机制的改进型蚁群算法。周卫标等[5]改进了蚁群算法的参数设置，设置了约束条件，在提高全局搜索能力的同时避免了收敛过慢。而对冰鲜水产品配送路径优化尚未见报道，配送过程中仍存在物流路径规划不合理、配送时间长、新鲜程度低、产品供应不稳定等问题。现仅见对运输过程中水产品保鲜技术[6]和运输条件[7]进行过一些研究，针对辽宁省冷冻水产品行业特性，对冷冻水产品销售配送网络结构[8]、港口物流发展过程中存在的问题[9-10]也进行了一些研究。由于冰鲜水产品的运送流程中涉及环节众多，且行程需控制在十小时以内，与一般货运配送相比冰鲜水产品对运输的路径及时间要求更为严格。

在解决路径优化的方法中，传统方法如系统仿真法、人际互动法、避圈法等在优化过程中存在搜索时间长及得不到全局最优解，导致物流配送效率低等问题。而蚁群算法在解决路径优化、任务分配等方面表现出了良好的性能，但该算法也存在如收敛速度慢、易陷入局部最优解等问题缺陷。本研究中，结合冰鲜水产品配送需求特点，以防止陷入局部最优解、保持寻觅最优解能力和提高收敛速度为目标，结合2-opt法对蚁群算法的初始信息素、信息素更新方式和启发因子进行改进，最后在Matlab2014环境下进行了仿真实验并与传统避圈法结果进行对比，对冰鲜水产品的配送路径进行了优化，以期在实际运输过程中缩短配送路径和配送时间，提高冰鲜水产品的物流运输效率。

1 蚁群算法模型设计

1.1 问题描述

据2013—2014年重点农产品流通冷链运输统计，东三省地区冷链运输率为11%，冷藏储存率为14%，而农产品腐烂变质概率高达35%[11]。由此，冰鲜水产品的路径优化问题相对于传统多回路运输问题(Vehicle Routing Problem, VRP)，决策变量需要根据配送过程中路况做出相应调整。蚁群路径上残留的信息量存在挥发现象，用1-ρ表示信息消逝程度，ρ的取值是0～1的常数。

为使研究目标更加突出，本研究中做出如下假设：(1)冷藏车辆载重无限制，即配送车辆载重是无限的；(2)配送车辆离开配送中心后停留在最后的配送点；(3)忽略配送过程中冰鲜水产品的温度变化；(4)忽略司机的工时回收需求；(5)忽略水产品的变质损坏；(6)忽略配送时的规章制度；(7)路径的性质，本研究中为有向路径，即A点到B点的配送费用不等于B点到A点的配送费用，路径的好坏通过道路的权值来反映；(8)为突出路径优化，假设一个城市中有一个配送中心，一对多关系，并且配送中心之间相互独立。

1.2 目标函数

蚂蚁总数m计算公式为

其中：m为蚂蚁总数目；n为配送中心客户数量；bi (t)为t时刻位于配送点i的蚂蚁个数。

t时刻蚂蚁k由位置i转移到j的概率公式为

其中：τij (t)表示第t周期内i到j的信息素；ηij (t)表示i到j的启发式信息；α为信息素启发因子，表示信息素的权重；β为期望启发因子，表示启发因子的权重。α、β∈正数。

i到j信息量的增量Δτij计算公式为

蚂蚁k本次循环中在i、j间留下的信息量计算公式为

其中：Q为信息素更新参数；Lk为每个蚂蚁经过的路径长度。

t时刻所能提供的某种启发式信息，也表示由配送点i转移到配送点j的期望程度ηij (t)，计算公式为

其中：dij为两个配送点i、j之间的几何距离。

最短路径公式则为

其中：cij为i到j的运输成本。

其中：式(7)约束了冷藏车辆的载重，gi为每个客户的货物需求量；式(8)保证了每个客户的运输任务仅由一辆车完成；式(9)和式(10)限制了到达和离开某一客户的冷藏车有且仅有一辆。

2 蚁群算法模型的改进

2.1 改进蚁群算法的数学模型设计

蚁群算法的决策是由该条路径上的信息素量Q决定的，蚂蚁选择信息素多的路径，较容易陷入局部最优解。本研究中对此进行优化。

2.1.1 初始化信息素的方向引导蚂蚁初始化信息素浓度公式为

其中：w为系统设定参数；dje为节点j与终点e的直线距离。若dje较小，则τij(0)较高，蚂蚁选择该路径的可能性就越大。此改进加快寻求最优解的速度，减少探测不必要路径的可能。

2.1.2 信息素更新的改进信息素的更新方法通常有两种：一是选择该次循环中路径最优的蚂蚁，这种方法优点在于不会陷入局部最优解，但收敛速度过慢;另一种更新信息素的方法是选择运算以来路径最优的蚂蚁，这种方法收敛速度相比另一种方法得到提升，但容易陷入局部最优解，限制蚁群发现更优解。

本研究中结合了以上两种方法的优点，提出一种信息素更新的改进方法。即在前10次算法循环中采用本次循环最优解，10次后再采用全局最优解更新信息素。这种方法首先将解集控制在较优解中，且在收敛速度较快的情况下不会局限解集，保持了继续寻觅最优解的能力。

改进后的信息素更新方法为

其中：Δτ=1/g，g表示局部最优解gib或全局最优解gob。信息素的限制为[τmin,τmax]，当τij(t)≥τmax时，则取τij(t)=τmax；当τij(t)≤τmin时，则取τij(t)=τmin。

信息素的改进：

(1) 信息素初始状态下采用下式确定其更新范围:

其中:L(sbest)为本次迭代或全局最优解;1/L(sbest)为每次路径上新的最大信息素。

(2) 信息素开始更新后，采用下式确定其更新范围:

2.1.3 启发因子的改进蚁群算法模型中启发函数一般取值为ηij(t)=1/dij，用以表示两配送点i、j之间距离关系。该函数只考虑了两节点之间的关系，无法体现全局性。本研究中将启发函数调整为ηij(t)=1/doj，用以表示从出发原点o到各节点i、j间的关系，保证了算法流程的全局性。

2.1.4 引入2-opt法局部优化 2-opt(2-optimal)法，也称2-exchange，即两元素间的优化。

定义1 称一个线路是2-opt局部最优解，是指不能通过2-交换将当前线路进一步缩短长度。

定义2 获取一个2-opt局部最优解的过程称为2-opt方法。2-opt方法反复采用2-交换对给定线路H进行改进，直到新线路不能再通过2-交换改进为止，此时的新线路记作2-opt(H)。

定义3 设有n个城市，则H的2-opt邻域定义为可以经过2-opt方法找到H的线路集合：

其中：H1为一个2-opt局部最优解；H为所有可能线路集合。

设H1=v1,v2,…,vn,v1是一条线路，对于两个顶点vi、vj，把(i,i+1)、(j,j+1)替换为(i,j)、(i+1,j+1)，变换后路径权值减小，即配送成本满足cij+ci+1,j+1<ci,i+1+cj,j+1时，变换后的路径如图1所示。

该算法在给定一条可行路径的情况下，只要操作能缩短当前路径，算法便可在既定集合内重复操作至不产生更新为止，此时便可完成局部优化。改进蚁群算法与2-opt法结合可节省计算时间并提高搜索效率。

2.2 改进后的算法流程图

本研究中根据冰鲜水产品特点，主要针对蚁群算法收敛速度慢、易陷于局部最优解等不足进行改进，其改进后的算法流程如图2所示。

2.3 改进算法流程主要步骤

(1) 初始化参数Q、Nc、α、β、w，设Nc=0 (Nc为迭代次数)，随机将m只蚂蚁放在初始节点;

(2) 设置循环次数Nc=Nc+1;

(3) 设置蚂蚁禁忌表索引号k=1;

(4) 设置蚂蚁数目变化为k=k+1;

(5) 通过改进的启发因子函数计算蚁群选择下一段路径的概率，实现其路径移动;

(6)更新蚁群经过路径上的信息素，修改禁忌表;

(7) 执行(2)到(6)至每只蚂蚁都选择一条包含全部节点的路径;

(8) 在所有可行解中寻取本次迭代最优解;

(9) 判断循环次数，当Nc≤10时采用本次循环最优解更新信息素，当Nc>10时采用全局最优解更新信息素;

(10) 利用2-opt法进行局部优化;

(11) 对所有路径更新全局信息素;

(12) 循环执行(2)到(11)直到连续多次不出现更优解或达到Nc max，输出为最优解。

3 应用实例

本研究中以大连市某冰鲜水产品物流配送企业为例，该企业有21个配送点(A2～A22)和一个配送中心A1，并要求一辆配送车完成配送，配送点(客户)只能被选择一次，且在配送点规定的时间要求范围内到达。配送车辆自离开配送中心A1后经过所有的配送点(客户)，最后停在最末配送点。路径距离及配送点时间要求均已知，如图3所示。图中A9、A20两配送点之间为国道，其他均为主干道路。

3.1 仿真运行

实验在Matlab 2014环境下进行，在CPU类型为酷睿双核i处理器、CPU为I-U、内存4 GB、操作系统为Windows的系统配置环境中对路径优化进行仿真实验。该模型为从起始点确定求取最佳运输路径的过程。其中，A1、A15、A13、A16、A19、A18、A21、A22、A20、A17、A14配送点位于市区，而A12、A11、A9、A10、A7、A5、A4、A2、A3、A6、A8配送点位于城郊地区。各配送点的坐标(x，y)及时间要求如表1所示，路径优化的仿真结果如图4-(a)所示。其中，配送车辆在市区的车速设定为60 km/h，在城郊地区的车速设定为70 km/h，根据配送公司给定的最长时间t=5.4 h，在A9—A20的国道阶段配送车辆的车速可以设定为较高速度90 km/h。参数设置根据实际经验设为m=30、Nc max(最大循环次数)=300，α=1，β=1，Q(信息素强度)=10。

根据配送中心要求，通过蚁群算法得出配送车辆到达地点顺序是A1→A15→A17→A14→A13→A16→A19→A21→A18→A22→A20→A9→A11→A10→A8→A6→A3→A2→A5→A4→A7→A12(表2)，总路径276 816.3 m。图4-(b)中虚线表示最短距离，实线表示平均距离。取A4点进行验证，经过计算可得A1到达A2点的时间为3.56 h，则A1→A4的配送时间为3.56+0.36+0.04=3.96(h)>3.95 h，不符合要求(表1)。故当车辆走到A2后寻求新的配送点进行配送，即先到A4再到A5，A2→A4的配送时间为0.13 h，则优化后A1→A4的配送时间为3.56+0.13=3.69(h)<3.95 h，A1→A5的配送时间为3.56+0.13+0.02=3.71(h)<4.12 h，均符合要求。故通过改进蚁群算法得出优化后配送车辆到达地点顺序为A1→A15→A17→A14→A13→A16→A19→A21→A18→A22→A20→A9→A11→A10→A8→A6→A3→A2→A4→A5→A7→A12(表2)。

Tab.1 Dispensing point coordinates(x，y) and dispensing point time requirements

图4 路径仿真结果和距离仿真结果图
Fig.4 Results of route simulation and distance simulation

为验证算法合理性，根据配送点时间要求以最大值验证。A1→A20配送时间2.17 h(表2)，从A9到A20为国道，距离为51.67 km，国道车速为90 km/h，则国道配送时间为51.67/90=0.57(h)，故A1→A9配送时间为2.17+0.57=2.74(h)<2.79 h,满足要求。计算得优化后配送总时间为4.17 h，小于配送中心给出的最长时间5.4 h。

Tab.2 Comparison table of distribution time differences before and after optimization

3.2 避圈法

计算最短配送时间，应用避圈法进行分析，具体见田晟[12]提出的基于最小生成树法的线路优化模型。本研究中运用避圈法在给定配送点分布图中寻找到最小部分树的步骤：

(1)从起始点v1点出发，使得v1∈V，避圈法中其他的点

(2)从V和

与之连线的线段中找到一条最小边，把这条边放入最小部分树中，将最小边[vi,vj]加粗，以更加明显的标记选定好的路线；

(4)重复上面流程，直至所有点均包括在V中为止。

根据上述避圈法步骤，得到最终配送路径图，如图5所示。根据表1中横纵坐标值计算得到配送距离为426 704 m，整个配送过程中假定车辆和车速(70 km/h)均不变。用避圈法计算得配送时间为426704/70=21995.05(s)=6.1 h。

对比避圈法、传统蚁群算法和改进蚁群算法的配送时间、配送距离(表3)可知，改进蚁群算法的配送效果最优。该方法与避圈法、蚁群算法相比，其时间分别缩短31.64%和8.15%，路径分别缩短21.89%和16.94%。其最短配送时间在提高冷链运作效率的同时有效减少冰鲜水产品腐烂变质现象的发生，保证了水产品的时效性和安全性。

4 结语

本研究中分析了冰鲜水产品对配送时间的特殊需求，结合2-opt法改进初始信息素、信息素更新方式和启发因子，仿真实验结果表明，改进蚁群算法相比传统避圈法配送时间缩短了1.93 h、配送距离缩短了149.887 km。本研究中改进蚁群算法模型能够显著提高算法全局性及收敛速度，对提升冰鲜水产品的物流运输效率和降低其配送成本均具有较明显的应用参考价值。

[1] 黄华芳,王以忠,李达,等.果蔬运输车辆路径再规划[J].农业机械学报,2012,43(4):113-118.

[2] 陈迎欣.基于改进蚁群算法的车辆路径优化问题研究[J].计算机应用研究,2012,29(6):2031-2034.

[3] 范小宁,徐格宁,杨瑞刚.车辆配送路径优化的新型蚁群算法[J].计算机工程与应用,2011,47(26):232-234,245.

[4] 董凌艳,徐红丽.基于改进型蚁群算法的AUV路径规划[J].自动化与仪表,2017,32(3):1-4.

[5] 周卫标,吴楚东,高敏.基于改进蚁群算法的配送路线优化分析[J].科技经济导刊,2018,26(15):10-11,19.

[6] 黎柳,谢晶.水产品冰鲜技术的研究进展[J].食品与机械,2014,30(1):259-262,266.

[7] 潘澜澜,张国琛,洪滨,等.不同单元化运输条件对活体虾夷扇贝存活率及主要营养成分的影响[J].大连海洋大学学报,2017,32(5):590-596.

[8] 霍红,崔琦,詹帅.辽宁省内冷冻水产品冷链配送网络规划[J].江苏农业科学,2016,44(8):535-539.

[9] 刘宏,高丽君.新时期辽宁省港口物流发展现状及对策[J].商业经济研究,2016(13):119-120.

[10] 沈秦伟,韩增林,郭建科.港口物流与城市经济增长的关系研究—以大连为例[J].地理与地理信息科学,2013,29(1):69-73.

[11] 金重威,袁雪妃.论食品行业冷链物流的发展—以辽宁雪莲牧业公司及辽宁菊花女食品有限公司为例[J].决策探索(下),2018(3):49-51.

[12] 田晟.基于最小生成树的物流结点选址和线路优化模型研究[J].交通运输研究,2009(5):135-138.