多目标生鲜食用菌配送路径

罗 奇，周 煜

（1.武汉体育学院体育工程与信息技术学院，湖北 武汉 430079；2.武汉体育学院研究生院，湖北 武汉 430079）

蚁群算法是由Marco Dorigo[1]在1992年提出的一种群集智能算法，其核心内容还是利用了自然界蚂蚁通过信息素进行间接通讯，利用信息素信息和与问题相关的启发式信息逐步构造出问题的解。这种系统的组织是从一开始的无序状态逐渐转变为有序过程，即蚂蚁一开始是盲目觅食的，找到食物后会越来越有序地向食物所在地进发，形成一个有序的觅食过程。这种自组织性大大增强了蚁群算法的鲁棒性。通过将这一算法应用在生鲜食用菌物流配送路径上，希望能够为食用菌物流配送路径的优化提供科学依据。

1 食用菌生鲜物流配送问题

食用菌生鲜冷链物流面对的都是冷藏冷冻的生鲜食用菌类产品，从食用菌原材料入厂的那一刻起，在生产过程、装卸搬运、物流运输和仓库保存等全过程，应一直处于低温环境，用于保证生鲜食用菌的品质[2]。由于生鲜食用菌产品从出厂到物流运输，再经过配送最终到达消费者的手上需要较长的时间，而生鲜食用菌产品本身的品质保障时效较短，为了延长保鲜期限，人们采取了制冷冷藏技术，并将其应用于生鲜食用菌产品的物流配送全过程中，低温环境有效减少了生鲜食用菌的腐烂变质，保证了产品的质量。

冷链物流从本质上来说也属于物流，具备一般物流的所有特点[3]。但由于生鲜食用菌的特殊性，冷链物流除有低温贮藏的要求外，还都有一个时效性要求，即整个食用菌产品的物流配送流通时间要尽可能的短。

目前，压缩物流配送时间的方法主要是建立多级物流仓库，增加物流节点，以增加物流配送点到客户的距离，从而缩短配送时间。但这也带来新的问题，就是物流配送路线的合理性问题。即需要将货物一个个送到所有的物流节点，走一条什么样的路线能够不遗漏一个节点，而且所有的路线距离最短或用时最少，这就是所谓的路径优化问题，也是食用菌产品物流配送中首先需要解决的问题。如果对多配送目标进行规划是很复杂的工作，更有一些配送中心自身并不清楚需要什么样的目标，只是为了完成配送任务或者只是得到各方都可以接受的配送路径。因此，多种配送目标造成了生鲜食用菌配送路径规划的难题。

2 食用菌配送路径蚁群算法

2.1 蚁群算法基本原理

通过2只蚂蚁觅食过程来说明蚁群算法的基本原理[4]，详见图1。

如图1所示，X点为1个蚁穴，设定这时有2只蚂蚁出去觅食，蚂蚁a和蚂蚁b，Y点为食物所在位置，Z点只是中途需要经过的一个地点，即路径上的一点。假定XYZ围形成等边三角形，即XYZ三点间的距离相等，而且2只蚂蚁移动速度相同。

2只蚂蚁从W1时刻开始从蚁穴X点出发觅食，蚂蚁a和蚂蚁b分别选择了XY和XZ两条路径；当到W2时刻时，蚂蚁a已经走到了Z点，而蚂蚁b也走到了Y点，2只蚂蚁在其所走过的XY和XZ两条路径上都留下了信息素痕迹（用虚线来表示信息素的痕迹），这时两条路径上的信息素的浓度是一样的。随后蚂蚁b发现了食物并将食物通过原路径XZ搬回了蚁穴，没ZX又留下了自己的信息素痕迹，这时路径XZ上的信息素浓度会增加（因为蚂蚁b释放了2次信息素）；而蚂蚁a则继续前行从Z点向Y点进发。需要说明的是在觅食的初始阶段，环境中是没有信息素的。

等到W3时刻时，蚂蚁b已经到达了蚁穴X点，而蚂蚁a则到达了食物所在地Y点。这时蚂蚁b已经第二次离开蚁穴X点，它面临着两个选择，走XZ还是走XY路径，但蚂蚁的路径选择不是盲目的，它是根据一定的转移规则选择移动方向的，即每条可行的路径上残留的信息素浓度，它发现XY路径上的残留信息素浓度较高（释放了2次信息素），因此，蚂蚁b选择XY路径去寻找。

与此同时，蚂蚁a则在Y点找到了食物准备返回蚁穴X点。它也面临着2个选择，即XY路径和YZ路径，同样，它也发现XY路径上的残留信息素浓度较高（释放了2次信息素），因此它也选择XY了路径返回蚁穴而不是按原路返回。后来的大批蚂蚁会选择XY这条线路的概率会更大，经过的蚂蚁越多，由于蚂蚁群体中每个蚂蚁的信息素不断更新，XY路径上的信息素痕迹会不断被加强，如此往复从而形成正反馈机制，便利更多的蚂蚁有机会选择XY这条更短的路径来找到食物。

2.2 食用菌配送路径蚁群算法数学模型的建立

在对食用菌配送路径实际的蚁群进行建模的过程中，需要解决蚁群中整个蚁群的内部机制、蚂蚁个体的建模问题、信息素的更新机制等，根据蚁群算法解决问题的步骤[5]。采用蚁群算法对食用菌配送路径优化问题建立数学模型。

在物流中心所辐射的地区中有n个需要配送的节点，配送员需要不重复的一次经过所有的物流配送节点进行送货。建立模型的目的就是他按照怎样的路径送货，从才能使走过的距离最短。我们采用蚁群算法来求解这个配送路径的问题，将这个问题的算法描述如下。

假设物流配送节点i的坐标为：ci=（xi，yi），i=1，2，3，…，n，这里物流中心所辐射管理的所有物流配送节点总和为 C={c1，c1，c1，… cn}，物流配送节点i，j之间的距离（dij，cm） 计算公式为：

为每只蚂蚁设置1个记录表，用于记录其走过的物流配送节点，避免重复走过某个物流配送节点，记录表中第一条记录就是蚂蚁初始时刻所在的物流配送节点，也可以理解为配送中心的位置，当所有的物流配送节点都已经加入记录表的时候，表示蚂蚁已经走完了所有的物流配送节点，完成了配送全过程。令τij（t）为物流配送节点i，j之间的信息素的量，初始时刻其取值为τij（0）=c，其中c为常数。

假设在（t，t+n） 时刻所有蚂蚁完成一次周游，则在t+n时刻物流配送节点i，j之间的信息素。

信息素（τij，t）含量计算公式为：

式中：ρ表示时间段（t，t+n） 之间信息素的挥发系数，因此（1-ρ） 就表示信息素的剩余量；而挥发系数取值范围为 [0，1]；△τij表示在时间段（t，t+n）之间信息素的增加量，计算公式为：

式中：k表示蚂蚁的编号；m为蚂蚁的数量。

式中：ηi，j为启发式因子（启发函数），计算公式为ηi，j＝（di，j）-1，ηi，j表示了蚂蚁从物流配送节点i转移到物流配送节点j的期望程度；s表示蚂蚁k下一步选择的物流配送节点；Jk（i）表示在物流配送节点i处蚂蚁k可以选择走的物流配送节点的集合。m是信息启发式因子，而n为能见度启发式因子，n值的增加会降低路径搜索过程中的随机性，减弱算法的全局搜索性能。因此，m和n的大小决定了蚁群算法的收敛速度，过大的取值会降低蚁群算法搜索过程的随机性，过小则会影响算法的准确性和性能。因此这两个参数需要相互配合，以便调蚂蚁在路径寻找过程中的启发信息多少，使蚂蚁沿着正确的启发信息来选择下一个节点。

通过对式（4） 分析可知，物流配送节点i，j的信息素含量决定了蚂蚁的选择概率，τij反映了蚁群在这条路径上以前蚂蚁的经验值大小，即信息素的强度，是一个积累的信息量。如果物流配送节点i，j之间的距离比较短，信息启发式因子m和能见度启发式因子n的值会增加，以便蚂蚁选择这条相对比较短的路径；如果物流配送节点i，j之间的距离比较长，那两个启发式因子就变小，以增加蚂蚁选择其它路径的概率，从局部来看是增加了路径选择的随机性，减缓了收敛速度，但从全局来看避免了陷入局部最优解的问题，增加了路径优化的可能性。

3 结果与分析

设置参数后进行循环。根据蚁群（ant-cycle）模型，蚂蚁每进行一次路径的循环，就根据信息素更新公式和每条路径上的信息素痕迹含量，重新计算这个蚂蚁所走过的路径距离，如果比原来距离短（即比上次更优路径），就把这条路径保存下来并更新信息素，输出路径结果。经对参数的多次选值、调整和测试，得到最优配送路径距离及迭代次数。

随着信息启发式因子m值的增加，蚁群算法会快速收敛；当能见度启发式因子n值变小时，也会加快收敛速度，但n值小于0.1时，会导致局部收敛，很快达到局部最优解，即很少的迭代就可以得到“最优”路径，但这并不是全局最优路径，要适当调大信息素重要因子n值，虽然会带来路径距离的增加，但对全局最优解来说是值得的。而启发因子η在一定区间里面的浮动对最优距离影响不大。

通过20组试验参数的调整比较，得到本次试验的最佳参数为m=6，n=1，η=0.2。

4 结论

采用蚁群算法适用于食用菌配送路径中的多目标求解问题，可以有效减少配送时间，节约配送成本，将配送路线与途径的地点最大化优化。从本质上，蚁群算法是一种基于群体的启发式随机搜索算法，有很强的随机搜索性能，又可以快速收敛，很好地避免在多目标路径求解中陷入局部最优的问题，可以快速准确地得到路径规划的全局最优解。