基于蚁群算法的农产品配送路径优化设计

周荣虎 （盐城工业职业技术学院，江苏 盐城 224005）

根据农产品时效性的特点，农产品配送中心路线规划时，除了要考虑常规物流配送一般影响因素外，还要考虑时间约束问题、客服水平问题、农产品保鲜度问题等，配送距离的长短决定了配送费用和效率，司机在选择派送路径的时候根据自己的习惯，随机或者盲目性的选择农产品配送路径，这一习惯往往造成绕路、重复路径等问题，无形中增加了运输成本、不能保证派送的时效性、降低了客户满意度，农产品配送路径的优化非常有必要，蚁群算法的出现为配送路径优化问题提供了有效的工具。

1 问题描述

20 世纪90 年代Marco Dorigo 在他的博士论文中提出蚂蚁算法，蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID 控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法是一种用来在图中寻找优化路径的概率型算法。它是通过人工模拟蚂蚁寻找食物的过程，即个体之间的信息交流和协作最终找到从蚁穴到食物源的最短路径。

1.1 蚁群算法特点

1.1.1 较强的鲁棒性

相对于其它算法，蚁群算法对初始线路要求不高，即蚁群算法的求解结果不依赖于初始线路的取舍，而且在搜索过程中不需要进行人工的调整。其次，蚁群算法的参数数目少，设置简单，易于蚁群算法应用到其他组合优化问题的求解。

1.1.2 是一种正反馈的算法

从真实蚂蚁的觅食过程中不难看出，蚂蚁能够最终找到最短路径，直接依赖于最短路径上信息激素的堆积，而信息激素的堆积却是一个正反馈的过程，正反馈是蚁群算法的重要特征，它使得算法演化过程得以进行。

1.2 问题描述

1.2.1 随机性选择派送路径问题

派送员在派送农产品的时候对路径的选择存在随机性问题，没有一套科学的方法去选择路径，大部分派送员的派送路径都是根据习惯或者随机的选择而定。

1.2.2 盲目性选择农产品配送路径问题

派送员在进行农产品派送的时候存在盲目性问题。派送员在农产品出仓后不按照规划好的路径排列农产品，而是随便装入车中。边走边按照运单上的客户地址进行派发农产品。绕路或者派送路径重复的情况频频出现，不仅浪费派送时间并且增加了派送成本。

2 模型建立与假设

2.1 蚁群算法原理

蚂蚁总能找到一条往返于食物源和巢穴之间的最优路径，这是因为蚂蚁在走过的路径上释放出一种特殊的信息素，路径越长，释放的信息素浓度越低。蚂蚁再次选择路径的时候，信息素浓度较高的路径被选中的概率相对较大，因此形成一个正反馈，最优路径上的信息素浓度越来越大，而其他的路径上信息素浓度却会随着时间增加而减少。最终整个蚁群会找出最短路径。具体情况如图1 所示:

设E 是蚂蚁巢穴，F 是食物源，BD 是一个障碍物。路径ABC 的距离是路径ADC 的2 倍。因为在E 到F 的直线距离中间有障碍物的存在。蚂蚁必须经过B 或D 往返于E,F 两点之间。设每个时间单位分别有30 只蚂蚁由E 到达A，由F 到达C。为方便说明，设蚂蚁走过后留下的信息素在路径上的停留时间为l。在初始时刻（如图1a），由于路径AB、CB、AD、CD 上都没有信息素，A 和C 两点所在的蚂蚁可以随机选择路径。从统计的角度可以认为它们以相同的概率选择AB、AD 或者CB、CD。因为信息素与路径的长短成反比，在经过一个时间单位后，路径ADC 上的信息素是路径ABC 上信息素的2 倍。在t=1 时刻（如图1b），将有20 只蚂蚁分别由A 和C到达D，有10 只蚂蚁分别由A 和C 到达B。随着时间的推移，蚂蚁选择路径ADC 的概率会越来越大，直到所有蚂蚁完全选择路径ADC，蚂蚁便找到了从蚁穴到食物源的最短路径。

图1 蚁群算法原理示意图

2.2 最短路径模型建立

农产品配送路径优化问题就是找到一条派送员以公司点部为起点，经过每一个有需求的客户且仅一次，最后返回到起点的最短路径。本节将蚁群算法的原理运用到进行农产品配送路径优化问题中。

2.2.1 提出假设

2.2.2 最短路径模型建立

2.2.3 基本蚁群算法模型

式（6） 中，Q3是常量，Lk表示第k 只蚂蚁在一次循环后路径的长度。即如果蚂蚁经过ij，则信息素增量为一个常量除以蚂蚁k 的一次循环路线长。这里信息素增量只与蚂蚁的循环路线和Q3有关系，而和具体的dij无关。

蚁量模型和蚁密模型利用的是局部信息，蚂蚁在完成一步（从一个客户到达另外一个客户） 便更新所有路径上的信息素。而蚁周模型利用的是整体信息，蚂蚁在一个循环（对所有n 个客户的访问） 以后，才更新所有路径上的信息素。因此在求解农产品配送路径优化问题时，蚁周模型比前面两种模型好。

当所有蚂蚁在一次循环结束后。所有m 只蚂蚁从同一点部M 出发随机的前往n 个客户处，重复上述步骤直到所有蚂蚁都选择一条相同路径的时候或者到达最大循环次数Nmax选出最短路径。蚁群算法的步骤为：将m 只蚂蚁随机放入n 个客户处，m只蚂蚁分别从n 个客户处出发，由式（2） 选择下一次经过的客户，Tabuk 为放入的已去过的客户，一次循环后，根据式（3）、式（6） 更新每条路径上的信息素，反复重复以上步骤，直到终止条件成立，求出目标函数最优值为止。

2.3 实例计算

为方便计算，本文选取苏州车坊镇SF 速运独墅湖点部M 中的收派员A 的区域B 中的10 个客户为例（以K0,K1,…,K9，命名）。运用蚁群算法对此10 个客户的农产品配送路径进行规划来说明蚁群算法在农产品配送路径优化问题中的实用性。

2.3.1 实例说明

（1） 某乡村的客观条件

采用10 个客户为研究对象，标记为1,…,10 分别代表K0,K1,…,K910 个客户。在派送农产品的时候不是取两地之间的直线距离，而是沿道路距离，通过测量建立点部到各个客户的距离以及客户与客户之间的距离表如表1 所示。

表1 点部到每个客户的距离以及客户之间的距离 单位：米

（2） 参数设置

为方便计算，提出以下假设条件：①10 个客户都需要有签收。②所有蚂蚁每次都由点部出发，走完所有客户后又回到点部。③每只蚂蚁在一次循环过程中经过每一个客户且仅一次。④每个客户到点部M 以及客户与客户之间的路径长度已知。

本文用100 000 次循环作为计算终止条件（这里一次循环是指所有蚂蚁完成一次遍历所有客户且仅一次后回到出发点部）。蚂蚁总数目设置为客户的总数目(m=n=1)0 。即10 只蚂蚁同时从点部M 出发开始循环，直到所有蚂蚁都返回点部则完成一次循环。具体参数设置如表2 所示。

在表2 中，Lk表示的是第k 只蚂蚁的一次循环路线的长度，如果第k 只蚂蚁经过的路线为：M→K0→K1→K7→K8→K2→K5→K4→K3→K6→K9→M。

表2 实例中所用参数设置

即第k 只蚂蚁本次循环的路径总长度为2 575 米。本文就是运用蚁群算法计算出一只蚂蚁从点部出发经过每个客户且只经过一次最后回到点部的最短路径。从而缩短农产品配送路径，节省运输成本。

2.3.2 运用蚁群算法对农产品配送路径进行编程计算

结合蚁群算法的原理，对农产品配送路径进行优化设计，并运用C++对设计好的最短路径模型进行编程计算。运用蚁群算法优化农产品配送路径的步骤为：10 只蚂蚁从同一点部M同时出发，将参数代入式（2） 选择下一次经过的客户，Tabuk 为放入的已去过的客户，一次循环后，将参数代入式（3）、式（6） 更新每条路径上的信息素，反复重复以上步骤，直到终止条件成立，求出式（1） 最短路径模型的最优值为止。按照上述步骤编辑好的程序如附录所示。附录在VC 上运行结果如图2 所示：

图2 附录在VC 上的运行结果

2.3.3 结果分析

由图2 可知蚂蚁从独墅湖点部M 出发经过10 个客户且每个客户只经过一次的排列顺序为：M 9 7 8 6 5 4 3 2 1 0 M。因此派送员A 在为10 个客户派送农产品的时候，从点部M 出发后，首先应去客户K9处，最后到达客户K0处。其走过的路径即为此次农产品配送过程中走过的最短路径。最短路径L 的排列顺序为：M→K9→K7→K8→K6→K5→K4→K3→K2→K1→K0→M。

即是派送员由独墅湖点部M出发，分别经过10 个客户且仅一次派送完农产品直接返回点部的最短路程为1 475 米。

如果第k 只蚂蚁的循环路径为：M→K1→K3→K6→K8→K9→K4→K0→K2→K5→K7→M。k

通过多次对10 个客户的排列顺序随机组合，没有找到路径Lk的长度比1 475 米更小的值。说明派送员A 为10 个客户派送农产品的最短路径为1 475 米。

在没有进行路径优化的时候，农产品员随机选择路径进行农产品配送，刚好选择到最短路径L 的几率非常小，但是在运用蚁群算法进行路径规划后，派送员每次都可以按照规划好的路径进行农产品配送。为每一个农产品派送员规划自己区域内的客户带来很大的方便，由此可见蚁群算法在农产品配送路径优化中具有非常大的实用性。

3 结束语

3.1 主要研究工作

本文首先针对农产品配送路径的现状进行分析，然后提出派送员选择农产品配送路径的时候，存在选择随机性问题和路径重复问题。最后针对这两个问题引入蚁群算法对农产品配送路径进行优化，寻找一条从农产品公司点部M 出发经过每一个需求点且仅一次最后回到点部M 的最短路径，实现节约农产品公司的配送成本、提高派送效率、增强客户满意度的目标。通过本文的研究说明蚁群算法在农产品配送路径优化问题中应用，有助于农产品公司降低运输成本，提高客户满意度。

3.2 进一步研究问题

本文虽取得了一些有意义的成果，但是还有许多需要进一步进行研究的方向。

（1） 在论文的实例中假设每个客户都有农产品需要签收，但实际派送过程中派送员负责的客户中有的客户在派送没有签收。改进蚁群算法突破局部最优的计算，把客户变动的因素设为变量的同时也能找到农产品配送的最短路径。

（2） 本文假设派送员在一次农产品配送过程中经过每一个客户且仅一次。没有考虑到突发状况和特殊快件的出现，例如实际生活中有的派送员因为一时大意而没有把同一客户处的农产品配送完毕，需要重复派送。或者有的农产品收件人需要提供优先派送服务，下一步可以通过进一步改进蚁群算法使其在加入突发状况后依然能找到最短路径。