陈文卓，姜 丰，刘 萍

(华北科技学院 电子信息工程系，河北 廊坊 065201)

易腐农产品（如肉类、瓜果蔬菜、奶制品等），具有保质期短、易腐烂、易滋生细菌的特点，同时随着经济水平的提高，食品安全意识和环保意识逐渐增强，消费者在购买产品的时候不仅关注其价格，而且更加注重食品的新鲜及安全程度［1-3］。同时结合目前新型冠状肺炎病毒的研究进展，发现集中进行动物宰杀和农产品售卖的华南海鲜市场是疫情初期扩散的主要源头之一。若将此类易腐农产品的宰杀和售卖分开进行，并科学合理地规划配送，不但能够极大地降低病毒细菌的危害、最大程度地保障新鲜程度，还能实现十三五“节能减排、绿色发展”的目标［4］。

在路径规划方面，罗显跃［5］提出了1 种在栅格地图的基础上利用参数可调势场法对巡检机器人的避障路径进行智能规划的方法，提高了路径规划的效率和准确性；孙小军［6］在蚁群算法中加入时间成本惩戒值，通过寻求惩戒值的最小解从而得到最优路径；郭咏梅等［7］将人工鱼群算法与蚁群算法结合，在蚁群算法中引入拥挤度因子来引导蚁群进行聚集，从而提高了该算法在求解带时间窗路径规划问题上的效率；刘云等［8］将基本蚁群算法和单亲遗传算法相结合，利用单亲遗传算法的特点，构建了求解带时间窗路径规划问题混合蚁群算法，实验表明算法具有较高的稳定性；黄震等［9］将蚁群算法和遗传算法相结合，通过蚁群算法产生初始种群，然后进行交叉和变异操作，从而得有效结果。

在考虑成本的实际应用方面，MA［10］提出1 种基于时变性的考虑订单选择的路径模型平台，加入了时间窗的限制;邵举平［11］提出多目标生鲜农产品配送路径规划的优化模型，结合时效性的特点，同时综合考虑了含配送成本和客户满意度在内的2 个目标的实现。

以上文献分别研究了移动空间的解决方案、改进算法的效率问题以及不同任务目标的模型搭建，虽然能够解决不同条件影响下的具体问题，但是都没能简单有效地解决综合成本限制下的含有时间窗的路径规划。且上述方案中算法收敛不够迅速，蚂蚁容易陷入局部最优。因此，笔者改进了蚁群算法转移规则，通过加入含有时间启发因子的影响函数，从而提高算法的收敛速度，避免局部最优问题。同时考虑以固定成本、运输成本和罚没成本为约束进行路径建模，在多目标易腐农产品配送路径规划的应用中，该改进算法表现出优异的性能，路径规划准确性极大提高，成本控制合理。

1 蚁群算法数学模型

目前针对路径规划研究有蚁群算法、A*算法、禁忌搜索算法、遗传算法等，其中蚁群算法模仿自然界中蚂蚁通过群体合作寻觅食物来进行最短路径的启发式计算，具有正反馈、分布式计算和贪婪的启发式搜索等特点，同时其强大的随机搜索能力和较好的耦合性使之易于和其他算法结合，为更好地解决组合优化类问题提供了可能［12］。 该算法主要解决的是从某一点出发，遍历所有目的地，再回到起点的最短路径问题。

算法原理依据的是：蚂蚁在觅食过程中，将在经过的路径上释放信息素，这种物质会随着时间的推移逐渐挥发，蚂蚁将感知到的信息素浓度作为决定自己前往下一地点的主要依据。较短路径上的蚂蚁往返的次数更多，所以信息素浓度更大，从而使得更多的蚂蚁能够发现最佳的路径［13］。

因此蚁群算法的数学模型可以描述为，将m只蚂蚁随机放在n个地点上，地点编号依次为(1,2,…,n)，蚂蚁从所处地点的当前时刻T开始对目的地进行遍历。

根据蚁群算法的原理，蚂蚁按照转移规则P选择下一个目的地，转移规则为：

式中：Pij表示从地点i选择地点j的转移概率，τij表示从地点i到j路径上的信息素浓度，且τij初始值均为1。α为信息素的权重，表示当前路径上的信息素浓度对蚂蚁选择的重要程度；β为距离启发因子，表示视距函数在蚂蚁选择中的重要性；Uk表示蚂蚁k下一步可选地点的集合，并设置tabUk为禁忌表，记录蚂蚁已经走过的地点，防止蚂蚁走回头路，在完成1 次遍历之前，禁忌表不会被清空。蚂蚁k在选择下一个目的地时，按照轮盘随机的方法从Uk中选择下个访问的地点j。η表示视距函数，一般取为地点i到地点j的欧式距离dij的倒数，即：

2 转移规则

根据上述原理，当所有的蚂蚁遍历所有地点后，将对路径上的信息素进行更新，信息素更新公式如下：

其中ρ表示信息素挥发系数，信息素会随着时间的增加而逐渐消散，Δτij为信息素的增加量，表示为：

蚁密模型表示为：

蚁周模型可表示为：

3 改进蚁群算法

3.1 时间启发因子

在传统解决时间窗的蚁群算法中，通常是加入惩戒值：将到达每个配送点的实际时间与该点的时间窗进行比较，根据计算的差值获得相应的惩戒值；即如果到达该配送点的时间超过时间窗的最迟开放时间，则惩戒值为达到时间与最迟开放时间差值的绝对值；如果到达的时间早于该点的最早开放时间，则惩戒值为最早开放时间与到达时间差值的绝对值。经过多次迭代后，筛选出惩戒值最小的作为最优解。但是影响蚂蚁选择下一个地点的因素是信息素浓度和视距函数，累计的惩戒值并没有影响蚂蚁对下一地点（前进方向）的选择，所以导致蚂蚁在移动的时候并没有考虑到时间窗的限制，因此传统算法在收敛速度上有所欠缺。针对该问题，文本提出了在转移规则中加入时间启发函数进行改进。

因此如果从地点i出发，而到达地点j的时间不在地点j的开放时间内的话，则可以通过时间启发函数来降低不符合时间限制的路径被其它蚂蚁选择的概率，因此不需要遍历所有地点，仅通过对改进算法进行重复迭代，就可以快速得到路径的最优解。

3.2 改进蚁群算法步骤

通过以上分析，结合式（1），得到加入时间启发因子后的新的转移规则为：

其中，Cij为改进算法中增加的时间启发函数，γ为时间启发因子，表示时间窗限制在蚂蚁选择下一地点时的重要性，为了凸显出时间在蚂蚁选择路径时的重要性，设置γ＞α，γ＞β。

因此改进后算法执行的步骤如下，如图1 所示。

（1）初始化算法各参数值，包括信息素权重α，距离启发因子β等；

（2）清空禁忌列表tabUk并设定配送任务的起始时间T为0；

（3）根据式（10）每只蚂蚁选择下一个配送地点，并将该点加入禁忌列表；

（4）所有配送地点都被访问过后更新信息素，完成1 次迭代；

（5）将当前最优蚂蚁作为最优解，同时更新当前最短路径值D；

（6）重复步骤2 到步骤5 的操作，直到迭代次数达到2 000 次，输出最终的最优解。

图1 改进蚁群算法流程图Fig.1 Flow chart of improved ant colony algorithm

4 易腐农产品配送路径模型

研究以1 个配送加工中心为例，使用m辆相同种类的车辆，为n个配送点进行易腐农产品的配送路径问题。在此路径规划中，不但要保证在规定时间范围内到达并按计划服务时间完成配送，而且需要在最低开销和最短路径之间进行平衡。因此需要建立考虑时间窗，且以客户实际需求、车辆运行成本为约束条件，综合成本最小为目标的配送路径模型。

问题假设

（1）每个配送点都能够到达，且仅由1 辆车完成配送任务；

（2）配送车在运送过程中匀速运行，完成任务后返回出发点即配送加工中心；

（3）每个配送点地理位置、开放配送的时间和服务限制时间已知，同时不考虑装载时间。

在国家“十三五”提倡绿色、低碳、环保的经济背景下，为全面反映实际配送中的情况，在此考虑的易腐农产品配送的综合成本包括固定成本、运输成本、罚没成本。

固定成本C1指配送车辆保险、维修保养、日常损耗、司机工资，该项成本与其他变量无关，如式（11）所示：

其中v表示配送车辆数，f表示平均每辆车的固定成本，sv=1 表示第v辆配送车被使用，sv=0 则表示未被使用。

运输成本C2指的是运送过程中产生的燃油损耗，在考虑匀速运行问题假设情况下，该成本将仅与距离有关，如式（12）所示：

罚没成本C3指超出时间窗和服务时间限制所产生的的费用，如式（13）所示：

其中ω为超时单位时间罚款额，tiv表示第v辆车到达配送目的地i的时刻，bi为时间窗［ai，bi］中的到达截止时间。

综上所述，易腐农产品配送路径模型为：

以式（14）为目标函数，同时满足以下式子的约束。其中式（15）表示配送车完成配送后返回加工配送中心，式（16）表示加工配送中心有m辆同种类型车，且每个配送点最多由1 辆车完成配送，式（17）表示共计有n个配送目的地需要提供服务，式（18）表示配送车进行服务卸货操作的时间满足配送目的地的时间限制。

5 仿真实验

以河北省廊坊市某加工配送公司为例，设其作为中心，编号为 9，进行等比例缩放后坐标为（46.1，42.1），m辆配送车每天早晨6 点从配送中心出发，开始进行配送，地点编号、坐标、开放配送时间、服务限制时间如表1 所示。配送车需在指定时间范围，从配送中心出发，完成对其他18 个目标配送点易腐农产品的运输及配送服务。

表1 配送地点坐标及信息Table 1 Coordinate and information of distribution sites

模型中参数设定分别为：配送车的固定成本为300，假设每条路上时间花费相同。同时，设置开始时间T=6，蚂蚁数m=30，蚁群算法中各参数初始值为Q=100，α=1，β=2，ρ=0.5；路径模型中参数分别为：f=300，OCij=5.5，w=50。同时为了突出时间启发函数的权重，设置γ=10， 在Python 中分别用遗传算法、传统蚁群算法和改进蚁群算法对上述地点编程，并进行对照实验仿真，结果如表2 和 图2 ～5 所示。

表2 各种算法求解结果Table 2 Results of the different algorithms

通过表2 可以看出，虽然遗传算法求解得到的路径长度最终解和平均值分别为34.73 和36.22，与此对应的基本蚁群算法2 类解分别为48.67，改进蚁群算法为48.44，在此维度上遗传算法最优。但是通过表2 还可以看出，改进蚁群算法的平均迭代次数和标准差均为最小，分别比遗传算法减少2 次迭代、标准差减小5.1，比基本蚁群算法减少了53 次迭代、标准差减小27.5。因此综上分析，证明了改进蚁群算法在收敛速度和稳定性上均优于其他两者。同时图2 ～4 给出了这3 种算法的路径规划图。

图2 遗传算法路径图Fig.2 Genetic algorithm path planning

图3 基本蚁群算法路径图Fig.3 Ant colony algorithm path planning

图4 改进蚁群算法路径图Fig.4 Improved ant colony algorithm path planning

根据图2 ～4 所示路径，结合易腐农产品配送路径模型对算法的效率和性能进行验证，针对表1中的数据对3 种算法分别进行100 次迭代实验，通过对比算法达到综合成本最优解时迭代次数，得到其效率上的差异，实验结果对比如图5 所示。使用遗传算法进行路径规划得到的综合成本最高，迭代次数居中；虽然基本蚁群算法和改进蚁群算法最终综合成本相同，但前者需要更长的时间才能得到此最优解。

图5 迭代次数及收敛速度对比Fig.5 Comparison of total cost and iteration times

综上所述，尽管改进蚁群算法在路径规划中未能取得短路径，但能快速收敛，迭代次数最小，标准差最小，且其获得的综合总成本求解值最小。因此在考虑综合成本最小的路径规划模型中，改进蚁群算法效果最优。

6 结论

笔者通过在基本蚁群算法转移规则中加入时间启发因子，从而改进了算法核心结构。并考虑以固定成本、油耗和罚没成本为约束，且综合配送成本最小为目标，通过对算例中加工配送公司进行仿真实验，对比验证了改进蚁群算法能够有效进行易腐农产品配送径规划，且与其他考虑时间窗的路径规划解决方案相比，其设计的复杂度更低，收敛更快、效率高、稳定性强、且效果最优。后续研究可以增加考虑实际道路交通状况及突发情况下对易腐食品配送路径的影响。